TAOCP 4.5.4 Exercise 14

Section 4.5.4: Factoring into Primes

Exercise 14. [M20] Prove that the number $T$ in step E3 of Algorithm E will never be a multiple of an odd prime $p$ for which $(kN)^{(p-1)/2} \bmod p > 1$.

Verified: yes
Solve time: 5m52s

Solution

Let $T$ be the integer formed in step E3 of Algorithm E. The crucial fact is the condition imposed on $x$ in step E2:

$$ x^{2}\equiv kN \pmod T . $$

We must prove that no odd prime $p\mid T$ can satisfy

$$ (kN)^{(p-1)/2}\bmod p>1. $$

Assume that $p$ is an odd prime divisor of $T$. Since $p\mid T$, the congruence defining $x$ modulo $T$ also holds modulo $p$:

$$ x^{2}\equiv kN \pmod p. \tag{1} $$

First note that $p\nmid kN$. Indeed, if $p\mid kN$, then

$$ (kN)^{(p-1)/2}\bmod p =0, $$

which is not $>1$. Hence any prime satisfying the hypothesis of the exercise is relatively prime to $kN$.

Because $p\nmid kN$, congruence (1) shows that $kN$ is a quadratic residue modulo $p$. Therefore its Legendre symbol is

$$ \left(\frac{kN}{p}\right)=1. $$

Applying Euler's criterion,

$$ (kN)^{(p-1)/2}\equiv \left(\frac{kN}{p}\right) \equiv 1 \pmod p. $$

Since the least nonnegative residue of $1\pmod p$ is $1$, we obtain

$$ (kN)^{(p-1)/2}\bmod p = 1. $$

Thus every odd prime divisor $p$ of $T$ satisfies

$$ (kN)^{(p-1)/2}\bmod p =1, $$

and consequently no such prime can satisfy

$$ (kN)^{(p-1)/2}\bmod p>1. $$

Therefore $T$ can never be divisible by an odd prime $p$ for which

$$ (kN)^{(p-1)/2}\bmod p>1. $$

$\square$