Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 4 / 1G (Number Theory)

Since $a=kp\ge 2$, we have $a^p\equiv 1(\mathrm{mod}{a}^p-1)$ and $\gcd (a,a^p-1)=1$. Its multiplicative order therefore divides the prime number $p$. It cannot be one, because $0<a-1<a^p-1$. Thus the order is exactly $p$.

To find the desired prime divisor, use the cyclotomic polynomialChoose a prime factor $q$ of this integer. Since $p\mid a$, we have ${\Phi }_p(a)\equiv 1(\mathrm{mod}p)$, so $q\ne p$. Also $q\nmid a$. If $a\equiv 1(\mathrm{mod}q)$, then ${\Phi }_p(a)\equiv p(\mathrm{mod}q)$, contradicting $q\ne p$. Consequently $a$ has multiplicative order $p$ in the multiplicative group of a finite field ${\mathbb{F}}_q^{\times }$. Lagrange theorem givesThis $q$ divides $a^p-1$ as required. Notice that order $p$ modulo a composite integer alone would not justify selecting an arbitrary prime divisor; the cyclotomic polynomial selects a suitable one.

If there were only finitely many such primes $q_1,\dots ,q_r$, choose $k=q_1\cdots q_r$, with the empty product interpreted as one. Each $q_i$ divides $a=kp$ and hence does not divide $a^p-1$. The preceding argument supplies a further prime $q\equiv 1(\mathrm{mod}p)$ dividing that integer, a contradiction. There are infinitely many primes in this residue class.