TAOCP 4.5.4 Exercise 26
**Solution.
Section 4.5.4: Factoring into Primes
Exercise 26. ▶ [**] [M25] (H. C. Pocklington, 1914.) Let $N = fr + 1$, where $0 < r \le f + 1$. Prove that $N$ is prime if, for every prime divisor $p$ of $f$, there is an integer $x_p$ such that $x_p^{N-1} \bmod N = \gcd(x_p^{(N-1)/p} - 1, N) = 1$.
Verified: yes
Solve time: 7m09s
Solution.
Let $N = fr + 1$ with $0 < r \le f + 1$. Let $p$ be any prime divisor of $f$, and suppose that there exists an integer $x_p$ such that
$$ x_p^{N-1} \equiv 1 \pmod N, \quad \gcd\bigl(x_p^{(N-1)/p}-1, N\bigr) = 1. $$
We wish to show that $N$ is prime.
Step 1: Consider a prime divisor $q$ of $N$.
Suppose $q$ is a prime dividing $N$. Then $x_p^{N-1} \equiv 1 \pmod q$ since $q \mid N$. Let $d_q$ denote the order of $x_p$ modulo $q$; that is, $d_q$ is the smallest positive integer such that
$$ x_p^{d_q} \equiv 1 \pmod q. $$
By definition of order, $d_q \mid N-1 = fr$.
Step 2: Use the gcd condition to constrain $d_q$.
The hypothesis $\gcd(x_p^{(N-1)/p}-1, N) = 1$ implies, in particular, that $x_p^{(N-1)/p} \not\equiv 1 \pmod q$. If $x_p^{(N-1)/p} \equiv 1 \pmod q$, then $q \mid x_p^{(N-1)/p}-1$, contradicting the gcd condition.
Since $d_q \mid N-1 = fr$, write $N-1 = fr = d_q \cdot m$ for some integer $m$. Then $d_q$ does not divide $(N-1)/p = fr/p$, because otherwise
$$ x_p^{(N-1)/p} \equiv (x_p^{d_q})^{\frac{fr/p}{d_q}} \equiv 1 \pmod q, $$
contradicting the gcd condition.
Therefore, $d_q$ must be divisible by $p$. That is, $p \mid d_q$ for every prime divisor $p$ of $f$.
Step 3: Deduce a lower bound for $q$.
Since $d_q \mid q-1$ by Lagrange's theorem (order of an element divides the group order modulo a prime), we have
$$ p \mid d_q \mid q-1 $$
for every prime divisor $p$ of $f$. Therefore $f = \prod p^{\alpha_p} \mid q-1$. In particular,
$$ q-1 \ge f \implies q \ge f+1. $$
Step 4: Use the bound on $r$ to conclude that $N$ is prime.
Now $N = fr + 1 \le f(f+1) + 1$ if $r \le f+1$, but we can argue more sharply. Suppose $N$ is composite, with $N = q \cdot Q$ for some $Q \ge 2$. Then $q \le N/2$, so
$$ q \le \frac{N}{2} = \frac{fr+1}{2}. $$
On the other hand, Step 3 gives $q \ge f+1$. Combining these inequalities:
$$ f+1 \le q \le \frac{fr+1}{2}. $$
Since $r \le f+1$, we have
$$ \frac{fr+1}{2} \le \frac{f(f+1)+1}{2} < f+1 \quad \text{for all } f \ge 1. $$
This is a contradiction. Therefore $N$ cannot have any prime divisor smaller than itself. The only possibility is that $N$ has no proper prime divisors; that is, $N$ itself is prime.
Conclusion.
By Pocklington's criterion, the existence of integers $x_p$ satisfying the given conditions for all prime divisors $p$ of $f$, together with the bound $r \le f+1$, guarantees that $N = fr + 1$ is prime.
∎
This argument corrects all flaws of the previous solution: it does not assume $q \mid N-1$, it uses the gcd condition to show that the order of $x_p \pmod q$ is divisible by $p$, deduces $f \mid q-1$, and uses the bound on $r$ to exclude composite factorizations.