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.

  • $\begingroup$ If $p\,|\,n$ then the congruence is obvious, no? $p$ divides both sides. $\endgroup$ – lulu Apr 29 '18 at 16:02
  • $\begingroup$ 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. $\endgroup$ – Peter Apr 29 '18 at 16:09
  • $\begingroup$ @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. $\endgroup$ – 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.$$

  • $\begingroup$ How $n$ be equivalent to both $n \mod p$ and $0 \mod p$ ? $\endgroup$ – Jake Xuereb Apr 29 '18 at 16:26
  • $\begingroup$ @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$. $\endgroup$ – Ning Wang Apr 29 '18 at 16:30
  • $\begingroup$ Perhaps you are correct and I'm just getting muddled up in the notation. $\endgroup$ – Jake Xuereb Apr 29 '18 at 16:30
  • $\begingroup$ @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$. $\endgroup$ – Ning Wang Apr 29 '18 at 16:32
  • $\begingroup$ So personally I prefer to use $a\equiv b\ (\textrm{mod}\ p)$ than yours. $\endgroup$ – Ning Wang Apr 29 '18 at 16:34

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

  • $\begingroup$ With reference to which line ? $\endgroup$ – Jake Xuereb Apr 29 '18 at 16:03
  • $\begingroup$ Your last congruence. $\endgroup$ – J.G. Apr 29 '18 at 16:04
  • $\begingroup$ If $n$ is 0 mod $p$, then so is $n$ to any power $\endgroup$ – Ashwin Iyengar Apr 29 '18 at 16:04
  • $\begingroup$ @AshwinIyengar then why not have $n^p = 0 \mod p$ ? $\endgroup$ – Jake Xuereb Apr 29 '18 at 16:08
  • $\begingroup$ @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$ $\endgroup$ – Peter Apr 29 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.