Use Fermat’s little theorem to show that $8, 9, 10$ are not prime numbers

Question

Use Fermat’s little theorem to show that $8, 9, 10$ are not prime numbers.

I know that the theorem states: for all $a$ in $\mathbb Z$, if $p$ is prime and $p$ does not divide $a$ then $a^p = a$ mod $p$, which means that $a^{p-1} = 1$ mod $p$

How do I prove that $8,910$ are not prime using the above? Can I choose any counterexample, or does it have to be a general proof?

Answer 1

Fermat's little theorem states: "if $p$ is prime then 'for all $a$, if $p$ does not divide $a$ then $a^{p-1}\equiv 1\mod p$."

The contrapositive is "if there exists $a$ such that $p$ does not divide $a$ but $a^{p-1}\equiv 1\mod p$, then $p$ is not a prime."

So for each of $p=8,9,10$, you have to find $a$ which is not divisible by $p$ such that $a^{p-1}\not\equiv 1\mod p$.

For example, for $p=8$, take $a=2$, Since $|a|<8$ then $a$ is not a multiple of $8$, but $$a^{p-1}=2^7=128\equiv 0\mod 8.$$

Answer 2

One way out of many is to show none of them are Fermat pseudoprimes to base $7$. I personally would prefer to use $666$, mwahahahahaha! But $7$ is coprime to each of $8$, $9$ and $10$. Indeed:

• $7^7 = 823543 \equiv 7$ not $1 \pmod 8$,
• $7^8 = 5764801 \equiv 4$ not $1 \pmod 9$ and
• $7^9 = 40353607 \equiv 7$ not $1 \pmod {10}$.

However, $7^{10} = 282475249 \equiv 1 \pmod {11}$. And indeed $11$ is prime.

Just for the hell of it, try proving $703$ is prime (it's not) with Fermat's theorem. Modulo $703$, you should get the sequence $7, 49, 343, 292, 638, 248, 330, 201, 1$ repeating over and over until you land on $1$ at position $702$. However, with base $8$ instead, you should get $8^{702} \equiv 628 \pmod {703}$.

Answer 3

Fermat's Little Theorem actually says that $a^p\equiv a\pmod{p}$ if $p$ is prime, whether $(a,p)=1$ or not. $$ 2^8\equiv0\pmod8 $$ $$ 3^9\equiv0\pmod9 $$ $$ 2^{10}\equiv4\pmod{10} $$