# Corollary of Fermat's Little Theorem to $a^x \equiv 1 \pmod{p} \implies x \equiv 0 \pmod{p-1}$

I'm not sure what to call this proposition in relation to Fermat's Little Theorem (it is not the converse, though it seems related), but I am interested to know if the following holds:

$$a^x \equiv 1 \pmod{p} \implies x \equiv 0 \pmod{p-1}$$ for $p$ prime and $a \neq 1$.

If this does hold, what is the proof? If not, are there any conditions on $x$ required in order to have $a^x \equiv 1 \pmod{p}$?

• Do you know group theory ? – Maman Mar 31 '17 at 20:18
• No...$1^2\equiv 1 \pmod 5$, for instance. – lulu Mar 31 '17 at 20:19
• We need this to be true for all $a$ (or at least for carefully chosen $a$) to get the conclusion. Otherwise, not only is $a=1$ a counterexample, but so are more subtle cases like $13^4 \equiv 1 \pmod {17}$. – Misha Lavrov Mar 31 '17 at 20:20
• What about $a=13$? Will you edit this, too? – Dietrich Burde Mar 31 '17 at 20:22
• $2^3\equiv 1 \pmod 7$. – lulu Mar 31 '17 at 20:22

For each prime $p$, there exists a primitive root $r$ which has the property you want: $$r^x \equiv 1 \pmod{p} \implies x \equiv 0 \pmod{p-1}.$$ For example, if we work modulo $7$, $3$ is a primitive root, because \begin{align} 3^0 &\equiv 1 \pmod 7 \\ 3^1 &\equiv 3 \pmod 7 \\ 3^2 &\equiv 2 \pmod 7 \\ 3^3 &\equiv 6 \pmod 7 \\ 3^4 &\equiv 4 \pmod 7 \\ 3^5 &\equiv 5 \pmod 7 \\ 3^6 &\equiv 1 \pmod 7 \\ \end{align} so the powers of $3$ have a period of exactly $6$. It follows that $2$ will not work mod $7$, because $$2^3 \equiv (3^2)^3 \equiv 3^6 \equiv 1 \pmod 7.$$
This MSE post gives a short proof of the existence of primitive roots modulo any prime $p$.