# Homework Help: Binomial Theorem and Modular Arithmetic Proof Check

1. Oct 21, 2009

### Hotsuma

1. The problem statement, all variables and given/known data

$$\mbox{Prove or give a counterexample: If p is a prime integer, then for all integers x and y, } (x+p)^p \equiv_p x^p+y^p$$.

2. Relevant equations

$$\equiv_p \mbox{just means (mod p). Can you please check and see if this proof is well-formed?}$$

3. The attempt at a solution

$$\mbox{Pf: Assume p is prime. Then} (x+y)^p= \left(\begin{array}{l c} p\\ 0\\ \end{array}\right) x^p+ \left(\begin{array}{l c} p\\ 1\\ \end{array}\right) x^{p-1}y+ \left(\begin{array}{l c} p\\ 2\\ \end{array}\right) x^{p-2}y^2+ ... + \left(\begin{array}{c c} p\\ p-1\\ \end{array}\right) xy^{p-1}+ \left(\begin{array}{l c} p\\ p\\ \end{array}\right) y^p = x^p + \sum^{p-1}_{k=1}x^ky^{p-k}+y^p.$$

$$\mbox{Notice that} \sum^{p-1}_{k=1}x^ky^{p-k} = \frac{p!}{k!(p-k)!}\mbox{, which, by a previously proven theorem, we know that } p\left| \frac{p!}{k!(p-k)!} \right..$$

$$\mbox{ So, by the definition of (mod p) we know that} \sum^{p-1}_{k=1}x^ky^{p-k}+y^p \equiv_p 0 \mbox{ and therefore }(x+p)^p \equiv_p x^p+y^p ~~~~\hspace{1.0cm}_\blacksquare$$

2. Oct 21, 2009

### Dick

It's not well formed. $$\sum^{p-1}_{k=1}x^ky^{p-k} = \frac{p!}{k!(p-k)!}$$ is completely false. You are summing over k. There can't be a k in the answer. The point is that each individual binomial coefficient C(p,k) is divisible by p for 1<=k<=p-1.

3. Oct 21, 2009

### Hotsuma

I discovered my error. Give me a minute.

4. Oct 21, 2009

### Hotsuma

$$\mbox{Pf: Assume p is prime. Then} (x+y)^p= \left(\begin{array}{l c} p\\ 0\\ \end{array}\right) x^p+ \left(\begin{array}{l c} p\\ 1\\ \end{array}\right) x^{p-1}y+ \left(\begin{array}{l c} p\\ 2\\ \end{array}\right) x^{p-2}y^2+ ... + \left(\begin{array}{c c} p\\ p-1\\ \end{array}\right) xy^{p-1}+ \left(\begin{array}{l c} p\\ p\\ \end{array}\right) y^p$$
$$= x^p + \sum^{p-1}_{k=1}\left(\begin{array}{l c} p\\ k\\ \end{array}\right)x^ky^{p-k}+y^p.$$

$$\mbox{Notice that} \sum^{p-1}_{k=1}\left(\begin{array}{l c} p\\ k\\ \end{array}\right)x^ky^{p-k} = \sum^{p-1}_{k=1}\left[\left(\frac{p!}{k!(p-k)!}\right) x^ky^{p-k}\right]\mbox{, which, by a previously proven theorem, we know that } p\left| \frac{p!}{k!(p-k)!} \right..$$

$$\mbox{ So, by the definition of (mod p) we know that} \sum^{p-1}_{k=1}\left(\begin{array}{l c} p\\ k\\ \end{array}\right)x^ky^{p-k}+y^p \equiv_p 0 \mbox{ and therefore }(x+y)^p \equiv_p x^p+y^p ~~~~\hspace{1.0cm}_\blacksquare$$

Last edited: Oct 21, 2009
5. Oct 21, 2009

### Hotsuma

Alright. How does that look?

6. Oct 21, 2009

### Dick

The third line is still completely garbled. The second line would say you can ignore the k=1 to k=p-1 terms because they are all divisible by p. Say the the previous theorem you are citing is for 1<=k<=p-1. On the last line (x+p)^p? Come on.