3
$\begingroup$

I'm currently studying for an exam and on the practice test given to us (with solutions), there is a problem that states the following:

Notice that for all $x,y \in \Bbb Z$,

$(x+y)^2 = x^2 + 2xy + y^2 \equiv x^2 + y^2$ mod $2$

$(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3 \equiv x^3 + y^3$ mod $3$

$(x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + y^5 \equiv x^5+y^5$ mod $5$

Prove that if $p$ is any prime number then for all $x,y \in \Bbb Z$ we have $(x+y)^p \equiv x^p + y^p$ mod $p$.

Here is the proof that was provided to us in the solutions:

Let $p$ be a prime number. If $k$ is an integer satisfying $1 \leq k \leq p-1$, then $k! = 1\cdot2\cdot3\cdot\cdot\cdot k$ is a product of positive integeres smaller than $p$, and therefore $k!$ is not divisible by $p$. For the same reason, if $1 \leq k \leq p-1$ then $(p-k)! = 1\cdot2\cdot3\cdot\cdot\cdot (p-k)$ is not divisible by $p$. Since $p!$ obviously is divisible by $p$, we infer that

$\binom{p}{k} = \frac{p!}{k!(p-k)!} \equiv 0$ mod $p$ whenever $1 \leq k \leq p-1$.

Therefore

$(x + y)^p = x^p + y^p +\sum_{k=1}^{p-1} \binom{p}{k}x^k y^{p-k} \equiv x^p +y^p$ mod $p$.

Q.E.D.

I'm having trouble understanding a few things about this theorem and proof.

First, I'm not quite seeing the congruence (if that makes any sense). Like, I'm not seeing how $(x+y)^2 = x^2 + 2xy + y^2 \equiv x^2 + y^2$ mod $2$, or rather just in general for any power $p$, not just $2$.

I recall that we say $a \mid b$ if there exists some $c$ such that $ac = b$, and that we say if $a,b \in \Bbb Z$ and $n \in \Bbb N$, $a$ is congruent to $b$ modulo $n$ if and only if $n\mid (b-a)$. This is written as $a \equiv b$ (mod $n$) where $n$ is called the modulus, and from this we get residue classes $r$ that are all the sets of numbers of the form $a = bn + r$ where $r \in \{0,1,2,\cdot\cdot\cdot, n-1\}$. I'm not quite sure how to phrase that but I can picture what it's supposed to be in my head.

I saw that in an answer listed here Proving $(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$ for prime $p$ that someone says "because nothing in the denominator divides $n$. So all of the middle terms in the expansion of $(a+b)^p$ vanish modulo $p$, and you're left with the two ends: $a^p+b^p$." But it still isn't making sense to me. How is it that because the denominator doesn't divide the numerator, all the messy middle terms disappear?

The next question I have is why go about proving it this way? What is the motivation for the techniques used to prove this statement? When I first saw this problem, admittedly I didn't know where to start. Part of me thought about induction but that was quickly ruled out based on the fact we're only considering prime powers. I did however immediately recognize that we're using binomial expansion and pascal's triangle, but that's about it.

I apologize for the long winded post and lots of questions, but this problem currently isn't making a lot of sense to me, so I would be incredibly grateful if somebody could explain this proof and its ideas to me. Thank you!

$\endgroup$
  • $\begingroup$ One preliminary observation is that $(a+b) \bmod{p} = ((a \bmod p) + (b \bmod p)) \bmod p$. This lets you remove the $2ab$ term from $a^2 + 2ab + b^2$. $\endgroup$ – Fabio Somenzi Sep 27 '18 at 2:58
4
$\begingroup$

The key here is to know that $(x+y)^n$ can be computed using the binomial expansion formula which explicit shows how the coefficients behave. Then it’s just a matter of seeing that each of those coefficients are divisible by $p$.

$\endgroup$
  • $\begingroup$ Oh, okay, that's actually really helpful. Thanks! $\endgroup$ – Matthew Graham Sep 27 '18 at 3:07
3
$\begingroup$

By the binomial formula (and as the solution mentions), $(x + y)^p=x^p +y^p + \sum_{k=1}^{p-1} \binom{p}{k}x^k y^{p-k}$, and so $x^p +y^p-(x + y)^p = -\sum_{k=1}^{p-1} \binom{p}{k}x^k y^{p-k}$. Now we just need to show that there exists an integer $c$ such that $pc = -\sum_{k=1}^{p-1} \binom{p}{k}x^k y^{p-k}$. You should know that $\binom{p}{k}=\frac{p!}{k!(p-k)!}$ is an integer. Since $p$ is a prime, and as the solution mentions; if $1 \leq k \leq p-1$, then $pd \neq k!$ and $pd \neq (p-k)!$ for all integers $d$. So $p$ remains as a factor of $\binom{p}{k}$ (*informally, it cannot be "cancelled out" by $k!(p-k)!$). Hence $c=-\sum_{k=1}^{p-1} \frac{1}{p}\binom{p}{k}x^k y^{p-k}$ is an integer. Therefore, $(x+y)^p$ is congruent to $x^p+y^p$ modulo $p$.

*It would be helpful to investigate why the same argument does not apply in cases where $p$ is not a prime number, such as $p=4$ or $p=6$.

$\endgroup$
  • $\begingroup$ In case something I said in my answer sounds dubious, I will note that $\neg \exists d \text{P}(d) \land \neg \exists d \text{Q}(d)$ is logically equivalent to $\forall d\left (\neg \text{P}(d) \land \neg \text{Q}(d)\right)$. $\endgroup$ – Matt A Pelto Sep 27 '18 at 4:41
2
$\begingroup$

If you are familiar with it, this problem follows immediately from Fermat Little Theorem. Indeed, by FLT you have $$(x+y)^p \equiv x+y \pmod{p} \\x^p \equiv x \pmod{p} \\y^p \equiv y \pmod{p}$$

therefore $$(x+y)^p \equiv x+y \equiv x^p+y^p \pmod{p}$$

$\endgroup$
  • $\begingroup$ Oh that's nice! We haven't reached that theorem yet in my abstract algebra class, I'm sure we'll touch upon it soon, but I have seen that before in another class. Totally forgot though. Didn't think to use it. Thanks for the response! $\endgroup$ – Matthew Graham Sep 28 '18 at 22:32
  • $\begingroup$ +1, but the general proof presented by the OP can be extended to computations in fields of nonzero characteristic, whereas this one cannot. $\endgroup$ – egreg Sep 28 '18 at 22:34
  • $\begingroup$ @egreg Setting $z=xy^{-1}$ you need to show that $$(z+1)^p=z^p+1$$ this is a polynomial of degree at most $p-1$ which, by FLT, has all $p$ elements of the prime fields as roots. Therefore, it is the zero polynomial... How is that for an extension ;) $\endgroup$ – N. S. Sep 28 '18 at 22:44
  • $\begingroup$ @N.S. :-) ............. $\endgroup$ – egreg Sep 28 '18 at 22:51
  • $\begingroup$ @egreg Of course $(z+1)^p=z^p+1$ is equivalent to all middle coefficients being $0$, and this can also be used to prove the FLT.. So in some sense the Frobenius map being a morphism and FLT are equivalent :) $\endgroup$ – N. S. Sep 28 '18 at 22:54

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.