[Math] Binomial formula modulo a prime.

Question

Let $p$ be a prime. I see that modulo $p$, the binomial formula reduces to
$$(x+y)^p\equiv x^p+y^p \pmod p$$ because $p \choose k$ is a multiple of $k$ whenever $k=1..p-1$, but don't we have by Fermat's little theorem
that $a^p\equiv a \pmod p$ for any integer $a$ and so this is true for $a=x+y$
hence the binomial formula reduces to
$(x+y)^p\equiv x+y \pmod p$. Thanks for your help!

Answer 1

Adding on to my comment:

Yes, everything that you have written is true. It is the case that $$(x+y)^p \equiv x^p+y^p \mod p$$ using the Binomial Theorem, and it is also true that $$(x+y)^p \equiv x+y \mod p$$ by Fermat's Little Theorem.

There is not contradiction here because by Fermat's Little Theorem, we have that $$x^p \equiv x \mod p \quad\text{ and }\quad y^p \equiv y \mod p$$ and so $$x^p+y^p\equiv x+y \mod p$$ as we expect.

Your observation that $$(x+y)^p \equiv x^p+y^p \mod p$$ by the Binomial Theorem is sometimes used to prove Fermat's Little Theorem by induction. The (complete) proof is as follows:

First we show, as noted by you, that $p \mid \binom{p}{k}$ for $1 \leq k < p$. We can prove this either by considering the factors of $p$ in the numerator and denominator of $\binom{p}{k}$, or by noticing that $$ \binom{p}{k} = \frac{p}{k}\binom{p-1}{k-1}$$ Thus $$ k \mid p\binom{p-1}{k-1}$$ and since $k$ and $p$ are relatively prime, we get that $$ k \mid \binom{p-1}{k-1}$$ showing that $$ \frac{1}{k}\binom{p-1}{k-1}$$ is an integer, and so $$ \binom{p}{k} = p \cdot \frac{1}{k}\binom{p-1}{k-1}$$ is an integer divisible by $p$.

As you noted in your question, $$(x+y)^p = \sum_{k=0}^p \binom{p}{k} x^k y^{p-k} = x^p + y^p + \sum_{k=1}^{p-1} \binom{p}{k} x^k y^{p-k} $$ Since every term in the final sum is divisble by $p$, we get that $$(x+y)^p \equiv x^p + y^p \mod p$$ and this holds for all integers $x$ and $y$.

We can now prove by induction that $$x^p \equiv x \mod p$$ for all integers $x$. The base case of $x=0$ is straightforward since $0^p=0$. Now suppose that $x^p \equiv x \mod p$ for some $x$. Then we have that $$ (x+1)^p \equiv x^p + 1^p \equiv x+1$$ using our observation above, and the inductive hypothesis.

Thus the claim holds for $x+1$ as well, and hence for all natural numbers by induction. For the negative integers, we can note that if $x$ is a positive integer then $$ (-x)^p = (-1)^p x^p \equiv -x \mod p$$ Here, we use that $x^p \equiv x \mod p$, and also that $(-1)^p \equiv -1 \mod p$, since if $p$ is odd then $(-1)^p = -1$, and if $p=2$ then $(-1)^p = 1 \equiv -1 \mod 2$.