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$
1
  • $\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$ Commented Sep 27, 2018 at 2:58

3 Answers 3

5
$\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$
5
  • $\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$ Commented Sep 28, 2018 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
    Commented Sep 28, 2018 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.
    Commented Sep 28, 2018 at 22:44
  • $\begingroup$ @N.S. :-) ............. $\endgroup$
    – egreg
    Commented Sep 28, 2018 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.
    Commented Sep 28, 2018 at 22:54
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$
1
  • $\begingroup$ Oh, okay, that's actually really helpful. Thanks! $\endgroup$ Commented Sep 27, 2018 at 3:07
4
$\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}$ 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$
1
  • $\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$
    – M A Pelto
    Commented Sep 27, 2018 at 4:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .