Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I know Fermat's Little Theorem = Fermat-Euler's Totient Theorem when $n$ is prime.

Elementary Number Theory, Jones, p83 writes

if we simply replace p with a composite integer n, then the resulting congruence $ a^{n-1} \equiv 1 \; (mod \, n) $ is not generally true. If gcd(a, n) > 1, then any positive power of a is divisible by d, so it cannot be congruent to 1 mod (n).

Can someone please amplify these 2 sentences? Is there intuition? I tried to prove this -

n composite means $gcd(a,n) > 1$. Dub $gcd(a,n) = g$. By definition of g, $g|a$ and $g|n$.
Thence $g|a \implies g|a^k $ for all $k \ge 1$. Then?

share|improve this question
    
Same idea as the reverse direction of Wilson's theorem you asked about earlier. If $d$ divides both $a$ and $n$, then it divides $a\bmod n$. And if $d > 1$, then it means that $a\bmod n$ can't be $1$ (or $-1$, for Wilson's theorem). –  fkraiem May 10 at 20:49
1  
More interestingly, for most composite $n$, there exist $a$ with $\gcd(a,n)=1$ such that $a^{n-1}\not\equiv 1\pmod{n}$. This is an important fact for primality testing of huge numbers. But there are exceptions, please see Carmichael Numbers. –  André Nicolas May 10 at 21:18
    
After your "Then?": $a^k + t\cdot n =$ a multiple of $g$ $\implies a^k \equiv g\cdot s \mod{n}$ but $g\cdot s = 0, g, 2g, \cdots$ never 1. –  Anant May 25 at 14:43

2 Answers 2

If $d | n$ then there is an $r \in \mathbb{Z}$ such that $dr \equiv 0 \mod n$ and $n$ does not divide $r$.

Suppose, by contradiction, there was any integer $a$ such that $ad = 1$. Then $1*r \equiv adr \equiv a*0 \equiv 0 \mod n$ so that $n|r$.

This shows that $d$ cannot have a multiplicative inverse modulo $n$. Thus $d^{n-1} \equiv 1 \mod n$ is impossible since this would imply that $d^{n-2}$ is a multiplicative inverse of $d$ modulo $n$.

The point is that zero divisors cannot have inverses.

Semi-related to your question is this interesting phenomenon.

share|improve this answer

To fill in your 'then': "Then: $g|a^k$, and in particular $g|a^{n-1}$. Also, we have $g|n$ (by definition), so $g$ divides any linear combination of $a^{n-1}$ and $n$. Since $a^{n-1}\pmod n$ is such a linear combination (it's $1\cdot a^{n-1}-b\cdot n$, where $b=\lfloor \frac{a^n-1}{n}\rfloor$), then $g|a^{n-1}\pmod n$."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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