4
$\begingroup$

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!

$\endgroup$
3
  • 2
    $\begingroup$ Yes, but you also get $(x+y)^p\equiv x+y \mod p$ straight from FLT without binomial theorem at all. $\endgroup$ – user281392 Oct 30 '15 at 21:24
  • 1
    $\begingroup$ Both are true. $(x+y)^p$ is congruent to $x^p + y^p$ modulo $p$. Now by Fermat's little theorem, $x^p$ is congruent to $x$ and $y^p$ is congruent to $y$ modulo $p$, and so $x^p + y^p$ is congruent to $x + y$ modulo $p$. $\endgroup$ – Dylan Oct 30 '15 at 21:24
  • $\begingroup$ @user281392. Very nice observation. +1 $\endgroup$ – Shailesh Oct 31 '15 at 2:56
2
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

Yes, good point. If $x$ and $y$ are integer, we can simply write $(x+y)^p = x + y \mod p$.

However, the formula $(x+y)^p \equiv x^p + y^p \mod p$ is also interesting because it applies not only to elements of $\mathbb{Z}/p\mathbb{Z}$, but also to any commutative algebra over $\mathbb{Z}/p\mathbb{Z}$ (for example, you may apply it to polynomials with coefficients in $\mathbb{Z}/p\mathbb{Z}$, or for field extensions of $\mathbb{Z}/p\mathbb{Z}$).

$\endgroup$
0
$\begingroup$

You have to show that $p \mid \binom{p}{k}$ when $1 < k < p$. We have: $k!(p-k)! \mid p!=p(p-1)!$ Using unique prime factorization we can write: $k!(p-k)! = a_1^{n_1}\cdot a_2^{n_2}\cdots a_m^{n_m}$ with the $a_i$'s are distinct primes smaller than $p$, and none of the factors divide $p$ since $a_i\nmid p$. Thus $a_i^{n_i} \mid (p-1)!$,and since these factors are pairwise coprime, we have $k!(p-k)! \mid (p-1)!$, this shows $p \mid \binom{p}{k}$, and the conclusion follows from this fact.

$\endgroup$

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.