A consequence of Fermat's Little Theorem
If $p$ is prime and $a \in \mathbb{Z}$ not divisible by $p$, $a^{p-1} \equiv_{p} 1 $
is
If $p$ is prime and $a \in \mathbb{Z}$ then $a^{p} \equiv_{p} a$ $\quad*\mathbb{\S}*$
The contrapositive of this statement can be used to test for primality:
I am having trouble accepting the statement above as the contrapositive, from a purely "mechanical" point of view - i.e the statement is logically true to me but the manipulation of quantifiers to obtain the contrapositive doesn't seem true.
My trouble most likely lies in the following distinction:
What is the difference between these two statements:
$\forall p \in \mathbb{N}$, $\forall a \in \mathbb{Z}$, if $p$ is prime, then $a^{p} \equiv a$ mod $p$.
$\forall p \in \mathbb{N}$, if $p$ is prime, then $\forall a \in \mathbb{Z}$ $a^{p} \equiv a$ mod $p$.(2)
I believe that the second is a correct, formal rendering of $\mathbb{\S}$. It also leads to the contrapositive. But why does the first not work?
If you take the contraposive of $\forall p, A(p) \implies B(p)$ inside the $\forall p$, you have $\forall p, \neg B(p) \implies \neg A(p) $
If you take $A$ : "p is prime"; $B$ : "$\forall a \in \mathbb{N}, a^p \equiv_p a $", you have $\neg B $: $\exists a \in \mathbb{N}, a^p \not\equiv_p a $ which implies "p is not prime"