Exercise 2.8.39* (Primality test for $m$ without a complete factorization of $m-1$)

Proof. Here $m>1$. By hypothesis $a^{m-1}\equiv 1(\mathit{mod}m)$, and $m-1=\mathit{st}$, where $s=q_1^{{\alpha }_1}{q}_2^{{\alpha }_2}\cdots q_k^{{\alpha }_k}$ and $t\wedge s=1$, so that $q_i^{{\alpha }_i}\mid \mid (m-1)$, and

By problem 38, every prime factor $p$ of $m$ satisfies $p\equiv 1(\mathit{mod}{q}_i^{{\alpha }_i})$ for $1\le i\le k$. Since the $q_i$ are distinct, $p\equiv 1(\mathit{mod}{q}_1^{{\alpha }_1}{q}_2^{{\alpha }_2}\cdots q_k^{{\alpha }_k})$, so

This implies that $p>s>m^{1∕2}$. Therefore $m$ has no prime factor $p\le m^{1∕2}$. If $m$ was composite, such a prime factor would exist. Therefore $m$ is prime. □