1
$\begingroup$

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}$?

$\endgroup$
6
  • $\begingroup$ Do you know group theory ? $\endgroup$ – Maman Mar 31 '17 at 20:18
  • $\begingroup$ No...$1^2\equiv 1 \pmod 5$, for instance. $\endgroup$ – lulu Mar 31 '17 at 20:19
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Misha Lavrov Mar 31 '17 at 20:20
  • 1
    $\begingroup$ What about $a=13$? Will you edit this, too? $\endgroup$ – Dietrich Burde Mar 31 '17 at 20:22
  • 1
    $\begingroup$ $2^3\equiv 1 \pmod 7$. $\endgroup$ – lulu Mar 31 '17 at 20:22
1
$\begingroup$

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$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.