4
$\begingroup$

Fermat's Little Theorem: If $p$ is prime, then for every 1 ≤ a < p,

$a^{p-1} ≡ 1$ $(mod$ $p)$

Let $p$ be 9 (a composite number), and let $a$ be 2.
Let $S$ be the nonzero integers modulo $9$

$S = (1, 2, 3, 4, 5, 6, 7, 8)(mod$ $9)$

$2^8S$
$=2^8(1, 2, 3, 4, 5, 6, 7, 8)$
$= (1*2,2*2,3*2,4*2,5*2,6*2,7*2,8*2)$
$= (2, 4, 6,8,10,12,14,16)$
$ = (1,2,3,4,5,6,7,8)(mod$ $9$)

$8! = 2^8*8!$

Divide both sides by $8!$ and you arrive at: $2^8 ≡ 1$ $(mod$ $9)$

Doesn't Fermat's Little Theorem only apply when $p$ is a prime number? The above calculations showed when $p = 9$ (composite), $a = 2$ still fulfills the equation.

  • 0
    I may not understand your notation, but it looks to me like S≡0(mod 9)2012-04-16

2 Answers 2

9

It is perfectly possible for $a^{n-1}$ to be congruent to $1$ modulo $n$ for some $a$, even when $n$ is composite. It is even possible for $a^{n-1}$ to be congruent to $1$ modulo $n$ for all $a$ relatively prime to $n$. This happens when $n$ is a Carmichael number (the smallest Carmichael number is $561$; there are infinitely many others).

But let's go back to your calculation. You used an argument much like the one used in one of the standard proofs of Fermat's Theorem. You let $S$ be $\{1,2,3,\dots,8\}$. You then observed that as $x$ travels over $S$, the number $2x$ is congruent modulo $9$ to $1,2, \dots,8$ in some order.

So if $P_S$ is the product of the numbers in $S$, we fairly quickly conclude that $2^8P_S \equiv P_S \pmod 9.\tag{$\ast$}$ From this you concluded that $2^8 \equiv 1\pmod 9$. Even though $(\ast)$ is correct, the conclusion that $2^8\equiv 1\pmod 9$ does not follow, and is in fact not true, since $256\equiv 4\pmod 9$.

What went wrong? Note that $P_S\equiv 0 \pmod 9$. Division by $0$ is no more permissible in the integers modulo $9$ than it is in the integers. The correct cancellation law is that if $ax\equiv ay \pmod n$ and $a$ and $n$ are relatively prime, we can conclude that $x\equiv y \pmod n$. Somewhat more generally, if $ax\equiv ay \pmod {n}$ and $\gcd(a,n)=d$, then $x\equiv y \pmod{n/d}$.

However, your idea can be made to work nicely. Instead of using the numbers $1$ to $8$, use only $1,2,4,5,7,8$, the $6$ numbers in our list relatively prime to $9$. Let $Q$ be the product of these numbers. Using exactly your argument, we find that $2^6Q\equiv Q\pmod{9}$. Since $Q$ is relatively prime to $9$, we can cancel, and conclude that $2^6\equiv 1\pmod{9}$.

This idea is one way to prove Euler's Theorem. But we must only use the numbers from $1$ to $n-1$ which are relatively prime to $n$, so that the cancellation we want to make is justified. That's where the $\varphi(n)$ in Euler's Theorem comes from.

  • 0
    The simple one is that if $a$ and $n$ are relatively prime, we can cancel. The easy way to prove this is to note that in this case $a$ is invertible modulo $n$, so there is a $b$ such that $ab\equiv 1\pmod n$. Then multiply both sides of the congruence by $b$.2012-04-16
2

i) No see Fermat pseudoprime.

ii) $2^8=256$ and $2+5+6=13$ so that $2^8= 1+3 \pmod{9}$ (the other one is right)

$2^{340} = 1\pmod{341}$ and $341=11\cdot 31$

  • 0
    @FarhadYusufali: the article should be right even if I can't prove you that 341 is the smallest pseudoprime... The other problem is that you divide by 8! which is not valid as pointed by André since $8! = 0 \pmod{9}$ (corrected...)2012-04-16