The Exercise

One classical step of Shor’s factoring algorithm starts from a number $x$ whose square is $1$ modulo $N$ , the number to be factored, while $x$ itself is neither $1$ nor $-1$ modulo $N$ . Theorem 5.2 of the book says that such an $x$ yields a factor of $N$ other than $1$ and $N$ : the greatest common divisor of $N$ with $x-1$ , or the one with $x+1$ .

Nontrivial Factors

A nontrivial factor $d$ of a natural number $n$ is a divisor of $n$ that lies strictly between $1$ and $n$ : $d \mid n, \qquad 1 < d < n.$ (1)^✦

The Claim

Theorem 1. Let $N$ and $x$ be natural numbers with $N > 0$ and $x \ge 1$ , such that $x^2 \equiv 1 \pmod N$ , $x \not\equiv 1 \pmod N$ and $x + 1 \not\equiv 0 \pmod N$ . Then at least one of the two numbers $\gcd(x-1, N), \qquad \gcd(x+1, N)$ (2)^✦ is a nontrivial factor of $N$ .

With $x + 1 \not\equiv 0$ read as $x \not\equiv -1 \pmod N$ , this is the exercise.

What Is Checked

The claim is stated over the natural numbers $N$ and $x$ , the greatest common divisor, congruence modulo $N$ , and the nontrivial factor of (1). What the library proves about these constructions is the claim (2) itself, for all $N$ and $x$ that meet its hypotheses.