This has been bugging me for quite a few minutes now, and I don't see where my thinking fails. In the inductive proof of this theorem, while proving the claim, the following lemma is used in order to reach the final point.

For any nonnegative integers $x, y$ and prime $p$ we have:

$$(x+ y)^p \equiv x^p +y ^p (\text{mod } p)$$

My question is, wouldn't this equivalence hold regardless of the primality of $p$, hence proving Fermat's little theorem valid for numbers that aren't primes as well? What am I missing?


Notice that $$(x+y)^p \equiv x^p+y^p \pmod p$$

is true when $$p\text{ }\bigg| \binom{p}{n} \text{ where } 0<n<p$$

This is true when $p$ is prime.

To see why, look at the following expression: $$\binom{p}{n}=\frac{p!}{n!(p-n)!}$$

First, let's consider when $p$ is prime. We already know that the numerator of the fraction is divisible by $p$. The only way that $\binom{p}{n}$ would not be divisible by $p$ is if $n!(p-n)!$ was divisible by some factor of $p$ (or $p$ itself). This is not true since both $n$ and $n-p$ are less than $p$, and also $p$ has no factors.

When $p$ is not prime,the statement is not necessarily true, since the same argument does not apply.

  • $\begingroup$ The thing I don't get, and sorry for being dense here, why does this only hold when $p$ is prime ? $\endgroup$ – maxeitzer Aug 22 '16 at 21:31
  • $\begingroup$ The "middle" coefficients given by the binomial theorem only vanish if they are all divisible by $n$. A prime $p$ divides $p!/((p-k)!k!)$ (which is an integer) because the factor $p$ does not belong to the denominator, so $p$ does not cancel $\endgroup$ – David Peterson Aug 22 '16 at 21:37
  • $\begingroup$ @maxeitzer I've made an edit, so hopefully my answer is a little bit more clear (also, no need to apologize) $\endgroup$ – Hrhm Aug 22 '16 at 21:47
  • $\begingroup$ Thank you, it makes perfect sense now. $\endgroup$ – maxeitzer Aug 22 '16 at 22:26

The equivalence does not hold in general for composite $n$. For instance $$ (x+y)^4=x^4+4x^3y+6x^2y^2+4xy^3+y^4\equiv x^4+2x^2y^2+y^4\mod 4$$ hence $(x+y)^4$ is not equivalent to $x^4+y^4$ mod $4$ if $x$ and $y$ are odd.

  • $\begingroup$ Thank you, carmichael561 :) $\endgroup$ – maxeitzer Aug 22 '16 at 22:26

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.