Tuesday, April 19, 2016

A number theory problem

Today I came across the following number theory problem:

Prove that if $x^p + y^p \equiv 0 (mod\ p)$, and $p$ is a prime number larger than $2$, then $x^p + y^p \equiv 0 (mod\ p^2)$.

The problem seemed innocuous enough at first glance, but proved to be quite challenging for me, as I could only solve the problem through arguably tedious means.

In any case, I thought I'd present my solution here; also for anyone who has stumbled onto this blog and has another solution, please don't hesitate to provide a sketch or full solution in the comments! 

Solution - 

By Fermat's little theorem, note that $x^p + y^p \equiv x+y \equiv 0 (mod\ p)$

Consider the following identity, where $a,b$ are integers, and $n$ is any natural number:

$\displaystyle a^n - b^n = (a-b)( \sum_{i=0}^{n-1} a^{i}b^{(n-1)-i})$

Lets attempt to use the above identity with $a=x$,$b=-y$ and $n=p$. 

Thus, we have:

$\displaystyle x^p - (-y)^p = x^p + y^p =(x+y)( \sum_{i=0}^{p-1} x^{i}(-y)^{(p-1)-i}) = (x+y)(\sum_{i=0}^{p-1} x^{i}y^{(p-1)-i}(-1)^i)$

Where $x^p - (-y)^p = x^p + y^p$ and $\displaystyle \sum_{i=0}^{p-1} x^{i}(-y)^{(p-1)-i} = \sum_{i=0}^{p-1} x^{i}y^{(p-1)-i}(-1)^i$ because $p>2$, so $p$ is an odd positive integer.

Now we note that since $x \equiv -y (mod\ p)$ by Fermat's little theorem,

$\displaystyle \sum_{i=0}^{p-1} x^{i}y^{(p-1)-i}(-1)^i \equiv \sum_{i=0}^{p-1} (-y)^{i}y^{(p-1)-i}(-1)^i = \sum_{i=0}^{p-1} (y)^{p-1} = py^{p-1} (mod\ p)$

and $py^{p-1} \equiv 0 (mod\ p)$

Thus we have shown that $p$ appears as a factor of $x^p + y^p$ twice, and thus $x^p + y^p \equiv 0 (mod\ p^2)$

No comments:

Post a Comment