TAOCP 4.5.4 Exercise 10
Assume that for every prime divisor $p$ of $n-1$ there exists an integer $x_p$ such that x_p^{(n-1)/p}\equiv 1 \pmod n, \qquad x_p^{\,n-1}\not\equiv 1 \pmod n.
Section 4.5.4: Factoring into Primes
Exercise 10. ▶ [M26] (John Selfridge.) Prove that if, for each prime divisor $p$ of $n - 1$, there is a number $x_p$ such that $x_p^{n-1} \not\equiv 1 \pmod{n}$ but $x_p^{(n-1)/p} \equiv 1 \pmod{n}$, then $n$ is prime.
Verified: yes
Solve time: 7m14s
Assume that for every prime divisor $p$ of $n-1$ there exists an integer $x_p$ such that
$$ x_p^{(n-1)/p}\equiv 1 \pmod n, \qquad x_p^{,n-1}\not\equiv 1 \pmod n. $$
We shall prove that $n$ is prime.
Let $q$ be any prime divisor of $n$. Since
$$ x_p^{(n-1)/p}\equiv 1 \pmod n, $$
we also have
$$ x_p^{(n-1)/p}\equiv 1 \pmod q. $$
Therefore $x_p\not\equiv 0\pmod q$, and the order of $x_p$ modulo $q$ is defined. Let
$$ d_p=\operatorname{ord}_q(x_p). $$
Then
$$ d_p\mid \frac{n-1}{p}. $$
Now fix a prime divisor $p$ of $n-1$. Since
$$ x_p^{,n-1}\not\equiv 1 \pmod n, $$
there exists at least one prime divisor $q$ of $n$ for which
$$ x_p^{,n-1}\not\equiv 1 \pmod q; $$
otherwise $x_p^{,n-1}\equiv1\pmod q$ for every prime divisor $q\mid n$, hence $x_p^{,n-1}\equiv1\pmod n$, contrary to hypothesis.
Choose such a prime divisor $q$ of $n$. For this $q$, let $d_p=\operatorname{ord}_q(x_p)$. We have
$$ d_p\mid \frac{n-1}{p}, $$
but
$$ d_p\nmid n-1, $$
would be impossible, because every divisor of $(n-1)/p$ divides $n-1$. Hence the only way that
$$ x_p^{,n-1}\not\equiv1\pmod q $$
can occur is that the order modulo $q$ is not a divisor of $(n-1)/p$.
To make this precise, write
$$ n-1=p^{a}m,\qquad p\nmid m. $$
Since $x_p^{(n-1)/p}\equiv1\pmod q$, the order $d_p$ divides $(n-1)/p=p^{a-1}m$.
Suppose that the highest power of $p$ dividing $d_p$ were at most $p^{a-1}$. Then $d_p\mid (n-1)/p$, and consequently
$$ x_p^{,n-1} = \left(x_p^{(n-1)/p}\right)^p \equiv1\pmod q, $$
contrary to the choice of $q$.
Therefore the order $d_p$ must contain the full factor $p^a$. In particular,
$$ p\mid d_p. $$
Since $d_p\mid q-1$ by Lagrange's theorem for the multiplicative group
$(\mathbf Z/q\mathbf Z)^\times$, it follows that
$$ p\mid(q-1). $$
We have proved that for every prime divisor $p$ of $n-1$,
$$ p\mid(q-1). $$
Hence every prime factor of $n-1$ divides $q-1$. More strongly, if
$$ n-1=\prod_i p_i^{a_i}, $$
the preceding argument shows that $p_i^{a_i}\mid(q-1)$ for each $i$. Therefore
$$ n-1\mid q-1. $$
But $q$ is a prime divisor of $n$, so $q\le n$. Hence
$$ q-1\le n-1. $$
Combining this with $n-1\mid q-1$, we obtain
$$ q-1=n-1, $$
so $q=n$.
Thus every prime divisor $q$ of $n$ equals $n$. Therefore $n$ itself is prime.
$$ \boxed{n\text{ is prime}.} $$
∎