Use Fermat’s little theorem to show that $8, 9, 10$ are not prime numbers 
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?
 A: 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.$$
A: 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}$.
A: 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}
$$
