0
$\begingroup$

Based on Fermat's little theorem or on Euler's theorem, is the statement

$$a^{n−1} \equiv 1 \pmod n \iff \gcd(a,n) = 1$$

true for every positive integers $a$ and $n$?

$\endgroup$
8
  • $\begingroup$ Try a few non-primes $n$, such as $4$ and $6$. $\endgroup$ – André Nicolas Apr 24 '14 at 22:14
  • $\begingroup$ @André Nicolas: Thanks. What about the values of $a$? $\endgroup$ – barak manos Apr 24 '14 at 22:15
  • 2
    $\begingroup$ Try $n=4$, and $a=3$, Of course $\gcd(a,n)=1$ but $a^{n-1}=3^3\not\equiv 1\pmod{4}$. The same sort of thing will happen with $n=6$ and $a=5$. But in principle one example is enough to show that the assertion is sometimes not true. $\endgroup$ – André Nicolas Apr 24 '14 at 22:22
  • $\begingroup$ The other direction is always true. If $a^{n-1}\equiv 1\pmod{n}$ then $\gcd(a,n)=1$. Proof is easy. For if $a$ and $n$ had a non-trivial common divisor, that would divide $a^{n-1}$ and $n$, and therefore would divide $1$. $\endgroup$ – André Nicolas Apr 24 '14 at 22:28
  • 2
    $\begingroup$ ie moral of the story is phi(n) doesn't necessarily divide n-1 $\endgroup$ – Jack Yoon Apr 24 '14 at 22:29
1
$\begingroup$

If $n$ is prime, then this is clearly true: $\text{gcd} (a, p) = 1$ is true for all $a < p$ and Fermat's little theorem does the rest of the work.

However, it is not true for all integers $n$. Take $n = 6$. We have $5^5 \equiv (-1)^5 \equiv -1 \pmod 6$. Indeed, for all even $n>2$, we have $(n-1)^{n-1} \equiv (-1)^{n-1} \equiv -1 \not\equiv 1 \pmod n$

$\endgroup$
1
  • $\begingroup$ That answers my question. Thank you. $\endgroup$ – barak manos Apr 24 '14 at 22:35

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.