Little Fermat equivalence $\!\bmod p\!:\, a^p\equiv a\!\iff \!a^{p-1}\equiv 1\,$ for $\,a\not\equiv 0$ In various texts, I have seen Fermat's Little Theorem presented as: $\forall a\in\mathbb Z, a\not\equiv 0\pmod{p}$ and prime $p$, $a^{p-1}\equiv1\pmod{p}$. On the other hand, in a reputable text, I recently encountered FLT as: $p\mid n^p-n,\forall n\in\mathbb Z$  I don't see why these are the same, it seems that the first definition is stronger. From the first definition, we can derive the second as follows, $n^{p-1} = 1+kp$ for some $k$, so $n^p - n = knp$ and so the RHS is clearly $0\pmod{p}$. On the other hand, I don't see how the other direction follows, if $n^p-n = kp$ for some $k$, then $n^{p-1} = 1+\frac{k}{n}p$, and it is not obvious to me why $k/n$ must be an integer. Can someone please explain?
 A: The $2$ are actually basically equivalent. For $a \not\equiv 0 \pmod p$, then
$$a^{p-1} \equiv 1 \pmod p \implies a^{p} \equiv a \pmod p \implies p \mid a^p - a \tag{1}\label{eq1A}$$
If $a \equiv 0 \pmod p$, then $a^p \equiv a \pmod p \implies p \mid a^p - a$ as well.
On the other hand, from $p \mid n^p - n$, if $\gcd(n,p) = 0$, then $n$ has a multiplicative inverse modulo $p$, so
$$n^p \equiv n \pmod p \implies n^{p-1} \equiv 1 \pmod p \tag{2}\label{eq2A}$$
which is the same as \eqref{eq1A} where $n = a$.
Of course, if $p \mid n$, then $n^{p-1} \equiv 0 \not\equiv 1 \pmod p$, which is why $a \not\equiv 0 \pmod p$ is required for \eqref{eq1A}.
A: [Note: I found this question $1$ week after it exited the Network Hot List, but I'll add an answer anyhow since it's a common question that deserves a conceptual answer].
This equivalence is a special case of the equivalence in $\rm\color{#0a0}{Euclid's\ Lemma}$, i.e.  a prime $\,p\,$ divides a product $\iff p\,$ divides some factor: $\,p\mid a_1\cdots a_n\iff p\mid a_1\,$ or $\,\cdots\,$ or $\,p\mid a_n.\,$ Thus
$$\begin{align} &\ \ a^{\large p}\,\equiv\ a\!\pmod{\!p}\\[.2em]
\iff\ \ \qquad \color{#c00}{p\mid a}\ \,&\!(a^{\large p-1}-1)\\[.2em]
\iff\ \color{#c00}{p\mid a}\,\ {\rm or}\,\ p\:\mid &\,a^{\large p-1}-1,\ \ \text{by $\rm\color{#0a0}{Euclid's\ Lemma}$}\\[.2em]
\iff\ \color{#c00}{a\equiv 0}\ \ \ {\rm or}\ \ \ &a^{\large p-1}\equiv 1\!\pmod{\!p}\\[.2em]
\iff\ \color{#c00}{a\not\equiv 0}\ \, \Rightarrow\, \ &a^{\large p-1}\equiv 1\!\pmod{\!p}
\end{align}\qquad$$
Remark $ $ The essence is clearer if we translate the above divisibility relations into much more intuitive operational language of field-theory. Like rings $\,\Bbb Q,\Bbb R,\Bbb C,\,$ recall $\,\Bbb Z_p = $ integers $\!\bmod p\,$ is also a field, hence $\,ab=0\iff a=0\,$ or $\,b=0,\,$ holds for all elements $\,a,b.\,$ This immediately yields the following fundamental result, which shows that the roots of a product of polynomials is the union of roots of the factors
$$\begin{align}f(r)g(r) = 0\ \iff&\ f(r)=0\ \ {\rm or}\ \ g(r) = 0\\[.2em]
\iff&\ f(r)\neq 0\,\Rightarrow\, g(r)= 0\end{align}\qquad$$ 
The OP is special case $\,f(x) = x,\ g(x) = x^{p-1}-1\,$ over the field $\,\Bbb Z_p = $ integers $\!\bmod p$
This result may fail in rings that are not fields, e.g. over the ring $\Bbb Z_8 = $ integers $\bmod 8\,$ the polynomial $\,(x-1)(x+1)\,$ has roots $\,\pm3\,$ as well as $\pm 1.\,$ For further discussion see here.
A: The thing is.  If $a\equiv 0\pmod p$ then $a \equiv 0 \equiv 0^k \equiv 0^p \equiv a^p \pmod m$.  Always.  That's trivial and always true and does really need to be stated.
So if $a^{p-1}\equiv 1\pmod p$ whenever $a\not \equiv 0\pmod  p$ then the following is true:  if $a\not \equiv 0\pmod p$ then $a^{p-1}\equiv 1\pmod p$ so $a^p=a^{p-1}a \equiv 1*a \equiv a \pmod p$.  And if $a\equiv 0 \pmod p$ then $a^p \equiv 0^p \equiv 0 \equiv a\pmod p$.  So $a^p \equiv a \pmod p$ no matter what.  So

$a^{p-1}\equiv 1 \pmod p$ whenever $a\not \equiv 0\pmod  p\implies a^p \equiv a\pmod p$ always.

And if if $a^p \equiv a \pmod p$ for all $a$ then if $a\not \equiv 0\pmod  p$ we have $a^p \equiv a\pmod p$.  As $p$ is prime, there is a $a^{-1}$ so that $a*a^{-1}\equiv 1 \pmod p$.  So $a^p*a^{-1} \equiv a*a^{-1} \pmod p$ so $a^{p-1}\equiv a\pmod p$.
So 

$a^p\equiv a \pmod p$ for all $a \implies a^{p-1}\equiv 1 \pmod p$ for all $a\not \equiv 0\pmod p$.

