Trouble Understanding Fermat's Little Theorem for Non-Coprime Case

For the case where some integer, $n$ is coprime to a prime modulus, $p$, I have proven and understood Fermat's Little Theorem as it is nothing more than Euler's Theorem applied to a prime modulus.

For the case where some integer $n$ is not coprime to $p$ $$\gcd(n,p) \neq 1 \implies p | n$$ This would mean that $$n \equiv 0\mod p.$$ So far so good. But how does one then go from here to $$0 \equiv n^p \equiv n \mod p$$ as is done by Herstein on page 44 of topics in algebra.

Any help or way-pointing is more than appreciated.

• If $p\,|\,n$ then the congruence is obvious, no? $p$ divides both sides. – lulu Apr 29 '18 at 16:02
• It is more common to start with Fermat's little theorem and consider Euler's theorem as a generalization. In fact, the case $p|n$ is trivial. – Peter Apr 29 '18 at 16:09
• @Peter, it is the order in which Herstein presented them. Perhaps it is because Herstein is an introductory group theory text and not a number theory book. I understand your point that starting with Fermat makes more sense and will try to think of them in this light. – Jake Xuereb Apr 29 '18 at 16:12

If \begin{align}{a\equiv b\mod p,\\c\equiv d\mod p,}\end{align}

then $$ac\equiv bd\mod p,$$

since $n\equiv n\mod p$ so in your case $$n*n*n*\dots\equiv0*n*n*\dots\mod p,$$

given $n\equiv0\mod p$, so $$n^p\equiv0\equiv n\mod p.$$

• How $n$ be equivalent to both $n \mod p$ and $0 \mod p$ ? – Jake Xuereb Apr 29 '18 at 16:26
• @JakeXuereb: Sorry I don't understand what's your confusion part. You should stick to the definition: $a\equiv b\mod p$ means $(a-b) = p*k$, which $k$ is an integer. So clearly $(n-n) = p*0$. – Ning Wang Apr 29 '18 at 16:30
• Perhaps you are correct and I'm just getting muddled up in the notation. – Jake Xuereb Apr 29 '18 at 16:30
• @JakeXuereb: Take a break may help. $a\ \mathbf{mod}\ p$ is different from $a\equiv b\mod p$, you should be careful about this part. The former is the remainder of $a$ divided by $p$, while the latter is the relationship between $a$ and $b$. – Ning Wang Apr 29 '18 at 16:32
• So personally I prefer to use $a\equiv b\ (\textrm{mod}\ p)$ than yours. – Ning Wang Apr 29 '18 at 16:34

Both sides are then divisible by $p$, so their difference is too.

• With reference to which line ? – Jake Xuereb Apr 29 '18 at 16:03
• Your last congruence. – J.G. Apr 29 '18 at 16:04
• If $n$ is 0 mod $p$, then so is $n$ to any power – Ashwin Iyengar Apr 29 '18 at 16:04
• @AshwinIyengar then why not have $n^p = 0 \mod p$ ? – Jake Xuereb Apr 29 '18 at 16:08
• @JakeXuereb The equation $$n^p\equiv n\mod p$$ holds for every $n$, therfore this equation is what Fermat's little theorem actually means. If $p|n$, then we of course have $n^p\equiv 0\mod p$ and if $p$ does not divide $n$, we can reduce to $n^{p-1}\equiv 1\mod p$ – Peter Apr 29 '18 at 16:11