Exercise 2.8.38* (Pocklington's Theorem)

Proof. Here $m>1$. Let $p$ be any prime factor of $m$. Let $h$ be the order of $a$ modulo $p$. This makes sense because $a^{m-1}\equiv 1(\mathit{mod}m)$ shows that $a\wedge m=1$, and $p\mid m$, so $p\wedge a=1$.

By Fermat’s Theorem, $a^{p-1}\equiv 1(\mathit{mod}p)$, thus $h\mid p-1$.

By hypothesis, $a^{m-1}\equiv 1(\mathit{mod}m)$. A fortiori, $a^{m-1}\equiv 1(\mathit{mod}p)$, because $p\mid m$. Hence $h\mid m-1$.

Moreover, from $(a^{(m-1)∕q}-1,m)=1$, we deduce that $p\nmid a^{(m-1)∕q}-1$, so $a^{(m-1)∕q}\not\equiv 1(\mathit{mod}p)$, which implies that $h\nmid (m-1)∕q$.

Since $q^{\alpha }\mid \mid (m-1),\alpha >0$, we may write $m-1=q^{\alpha }{q}_2^{{\alpha }_2}\cdots q_l^{{\alpha }_l}({\alpha }_i>0)$ the decomposition of $m-1$ in prime factors. Since $h\mid m-1$, $h=q^{\beta }{q}_2^{{\beta }_2}\cdots q_l^{{\beta }_l},0\le {\beta }_i\le {\alpha }_i$, and $0\le \beta \le \alpha$, so ${\nu }_q(h)=\beta \le \alpha$.

From $h\nmid (m-1)∕q=q^{\alpha -1}{q}_2^{{\alpha }_2}\cdots q_l^{{\alpha }_l}$, we deduce that ${\nu }_q(h)=\beta >\alpha -1$ (otherwise $h\mid (m-1)∕q$). Hence $\beta =\alpha$, so that $q^{\alpha }\mid \mid h$.

Thus $q^{\alpha }\mid h$, and $h\mid p-1$, so $q^{\alpha }\mid p-1$. We may conclude, for every prime divisor $p$ of $m$, that

□