5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – fkraiem May 10 '14 at 20:49
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas May 10 '14 at 21:18
  • $\begingroup$ 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. $\endgroup$ – Anant May 25 '14 at 14:43
3
+50
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.