Fallacy in Fermat's Little Theorem?

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.

-
Fermat theorem doesn't imply that $a^{n-1}\equiv 1 (mod n)$ fails for all $n$ composite. – azarel Apr 16 '12 at 21:36
When you divide by the product of the numbers in $S$, you are dividing by something which is congruent to $0$ modulo $9$. That is no more permissible in the integers modulo $9$ than it is in the integers. – André Nicolas Apr 16 '12 at 21:36
Your $S$ is a set. How do you divide by a set?? – Tara B Apr 16 '12 at 21:37
@Farhad mod $9$ the congruence $8!\equiv 2^8\:8!\:$ is simply $0\equiv 2^8\cdot 0$ since $9\ |\ 3\cdot 6\ |\ 8!\:$ so $\rm\:8!\equiv 0.$ So you are inferring $\rm\ 0\cdot n\equiv 0\:\Rightarrow\: 1\equiv n,\:$ which is false. – Bill Dubuque Apr 16 '12 at 21:56
@Farhad: And still the same error: Fermat's Little Theorem does not say "if $1\leq a\lt n$ then $a^{n-1}\equiv 1\pmod{n}$ if and only if $n$ is prime." It says "if $n$ is prime, then $a^{n-1}\equiv 1\pmod{n}$." And you still cannot "divide both sides" by $8!$", because $8!\equiv 0\pmod{9}$. – Arturo Magidin Apr 16 '12 at 21:56

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.

-
Thank You. Do you mind expanding on the correct cancellation law please? I do not understand it fully. – user26649 Apr 16 '12 at 22:12
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$. – André Nicolas Apr 16 '12 at 22:15

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$

-
Thank You. Sorry for the second question- stupid calculation mistake. The article however says the smallest pseudoprime for base 2 is 341. Is it wrong? – user26649 Apr 16 '12 at 21:55
@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...) – Raymond Manzoni Apr 16 '12 at 22:34