Prove Polynomial Congruence $(x+y)^n \equiv x^n + y^n$ (mod $p$)

[lfdahl]

Given a prime number $p$, prove that the polynomial congruence
$(x + y)^n \equiv x^n + y^n$ (mod $p$) is true if and only if $n$ is a power of $p$.

 

[lfdahl]

Hint:

Spoiler

Define the polynomial: $$P(x,y) = (x+y)^n-x^n-y^n = \sum_{k=1}^{n-1}{ n\choose k }x^ky^{n-k}$$

Consider the two cases:

(i). $n = p^a$

(ii). $n$ is not a power of $p$.

 

[lfdahl]

Suggested solution:

Spoiler

Let \[P(x,y) = (x+y)^n-x^n-y^n = \sum_{k=1}^{n-1}\binom{n}{k}x^{k}y^{n-k}.\]

(a). If $n = p^a$, then all the coefficients of $P$ are divisible by $p$.
Proof: For $1 \leq j \leq p^a-1$, $\binom{p^a}{j}=\frac{p^a}{j}\binom{p^a-1}{j-1}.$
If $j = rp^b$, where $gcd(r,p)=1$, then $\frac{p^a}{j}=\frac{p^{a-b}}{r}$, where $a-b \geq 1$ (since $j < p^a$). Thus $r$ must divide $\binom{p^a-1}{j-1}$ (since $\binom{p^a}{j}$ is an integer), and $\binom{p^a}{j}$ is divisible by $p^{a-b}$.

(b). If $n$ is not a power of $p$, then not all $\binom{n}{j}$ are divisible by $p$.
Proof: For $p^a < n < p^{a+1}$, let $c = n – p^a$ so $0 < c < p^a(p-1)$. Then $\binom{n}{c} = \binom{p^a+c}{c} = \prod_{j=1}^{c}\frac{p^a+j}{j}$. If $j = rp^b$, where $gcd(r,p) = 1$ and $b<a$, then $\frac{p^a+j}{j} = \frac{p^{a-b}+r}{r}$. From this $\binom{n}{c}$ equals a product of fractions none of whose numerators is a multiple of $p$.