# Why doesn't Fermat's Little theorem work for 4 and 9?

4 and 9 are relatively prime, but $4^8$ = 65536, which is not $1 \mod 9$. I can't figure out why because I've been told that $a^{p-1}$ is equivalent to $1 \mod p$ if $p$ and $a$ are relatively prime...so...what am I missing?

• Yes, I know, Fermat – Nethesis Aug 3 '14 at 21:10
• $\varphi(9)$ is not $8$ but is $6.$ – coffeemath Aug 3 '14 at 21:14
• You do need $\gcd(a, p) = 1$ but you also need for $p$ to be either prime OR a pseudoprime to base $a$. As it happens, 4 is a pseudoprime to base 9: verify that $9^3 \equiv 1 \mod 4$. – Robert Soupe Aug 4 '14 at 5:33

You can't apply Fermat's theorem: $$a^{p-1} \equiv 1 \pmod p$$

because $9$ is not a prime. However,you can use Euler's theorem:

$$a^{\phi(m)} \equiv 1 \pmod m$$

$$a=4$$

$$m=9$$

$$(a,m)=1$$

$$\phi(9)=\phi(3^2)=3^2 \left (1-\frac{1}{3} \right )=9 \frac{2}{3}=6$$

Therefore:

$$4^6 \equiv 1 \pmod 9$$

• Ok then, I guess the textbook is wrong, it says it applies if p is prime or a and p are coprime – Nethesis Aug 3 '14 at 21:17
• @Nethesis That should be and a and $p$ are coprime. Must be a typo – Mathmo123 Aug 3 '14 at 21:19
• I'm sorry, I don't understand the difference between a and $a$... – Nethesis Aug 3 '14 at 21:20
• @Nethesis You can only apply the Ferma'ts theorem if $p$ is a prime AND $(a,p)=1$. – evinda Aug 3 '14 at 21:23
• Ohh, thank you, the book did not phrase it in that way at all, thank you – Nethesis Aug 3 '14 at 21:24

Fermat's Little Theorem is true only if $p$ is prime - the statement is $$a^p \equiv a \mod p$$ for $p$ prime. When $(a,p) = 1$, this is equivalent to the usual formulation of the theorem (we can divide by $a$): $$a^{p-1} \equiv 1 \mod p$$ if $p$ is prime and $(a,p) = 1$. In this case, $9$ is not prime, so the theorem will fail.

There is however a generalisation that works for all integers, usually called the Fermat-Euler Theorem: we define $\phi(n)$ to be the number of integers less than $n$ that are coprime to $n$. Then if $(a,n)=1$, $$a^{\phi(n)} \equiv 1 \mod n$$

We have $\phi(9) = 6$ and indeed, $4^6 \equiv 1 \mod 9$.

• And $9$ is not prime, which is why the theorem fails in this case. – spin Aug 3 '14 at 21:15
• Fermat's Theorem holds in any finite field-even ones of non-prime order. So in any finite field of order $q$, we have $a^q=a$. This does not mean that $a^q\equiv a\mod q$ for each prime power $q$. This is because multiplication in $\Bbb F_q$ is different from multiplication in $\Bbb Z/q\Bbb Z$. – Robert Wolfe Aug 3 '14 at 22:20
• I've never heard that general theorem called Fermat's theorem - I had always thought of Fermat as specifically referring to $\mathbb Z / p\mathbb Z$. Although both follow simply from Lagrange's theorem for finite groups – Mathmo123 Aug 3 '14 at 22:24