# Prove that $a^{n-1} \equiv 1 \pmod n$ implies $n$ is prime

Let $a$ and $n\ge3$ be integers. Suppose that $a^{n-1} \equiv 1 \pmod n$, while $a^{(n-1)/p} \not\equiv 1 \pmod n$ for every prime $p$ dividing $n-1$, and I want to show that $n$ is prime.

First of all, we know that $(a,n) = 1$ because if $(a,n) = g > 1$, then $g \mid n$ which means $a^{n-1} \equiv 1 \pmod g$, but this is impossible since $g \mid a \implies g \mid a^{n-1}$. Since $a^{n-1} \equiv 1 = a^0 \pmod n$, it follows that $n-1 \equiv 0 \pmod{\phi(n)}$ (this is the part I am having trouble proving, I know that the converse always holds, and I want to show that in this case the statement also holds), which means $n - 1 = k \cdot\phi(n)$, and now we just need to show $k = 1$. But we have that $(n-1)/p \not \equiv 0 \pmod {\phi(n)}$ which means $\phi(n) \nmid (n-1)/p$ for all $p$ dividing $n-1$. Thus, $\phi(n) = n-1$.

Is it possible to prove the statement preceding the text in bold? Otherwise, what is the right approach to take for this problem?

• Well there are some numbers called pseudo primes ( a special type of pseudo primes are called Carmichael numbers where(a,n)=1).These numbers are composite and yet follow fermat's little theorem.Hence, converse of Fermat's little theorem is not always true. – user369582 Sep 29 '16 at 19:37
• @Avi Sorry, the title may be a bit misleading, but actually the problem has a stronger hypothesis than the title states (I didn't want to include too much in the title). Can you please have a look at the problem statement itself? Thanks! – b_pcakes Sep 29 '16 at 19:42

First of all, we know that $(a,n) = 1$ because if $(a,n) = g > 1$, then $g \mid n$ which means $a^{n-1} \equiv 1 \pmod g$, but this is impossible since $g \mid a \implies g \mid a^{n-1}$. Since $a^{n-1} \equiv 1 = a^0 \pmod n$, it follows that $n-1 \equiv 0 \pmod{h}$, where $h$ is the order of $a\pmod n$, which means $n - 1 = k \cdot h$, and now we just need to show $k = 1$. But we have that $(n-1)/p \not \equiv 0 \pmod {h}$ which means $h \nmid (n-1)/p$ for all $p$ dividing $n-1$. Thus, $h = n-1$. But $\phi(n) \leq n-1$ and $h \mid \phi(n)$ so $\phi(n) = n - 1$.