# Modular Power equation

I have an interesting problem I solved a while ago, and I was wondering if anyone had a different solution.

Let p and q be twin prime integers. Prove that $p^p+q^q\equiv 0 \pmod{p+q}$

I came up with:

Proof.

First, we are given that we want to prove $p^p+q^q\equiv 0 \pmod{p+q}$ We also know that p and q are twin primes and both odd. We know that an odd multiplied by an odd is odd, so $p^p$ and $q^q \equiv 1 \pmod 2$

We see that $(1+1 \bmod 2)\equiv 0 \pmod 2$

In order to prove that $p^p+q^q\equiv 0 \pmod{p+q}$, we need to prove $p^p\equiv p \pmod {p+q}$ and $q^q \equiv q \pmod {p+q}$

Using Fermat's Theorem where $a=p$, $$(p^{p-1} \bmod (p+q))\cdot(p \bmod (p+q)) \equiv p \pmod {p+q}$$

We do a similar procedure with $q$ to get $p^p+q^q\equiv 0 \pmod {p+q}$. Q.E.D

Thanks

-
Can't really use Fermat's Theorem, since $p+q$ is not prime. Hint: Let $m$ be the number in the middle. –  André Nicolas Mar 19 '12 at 21:54
Make sure to use $q=p+2$. –  lhf Mar 19 '12 at 22:03

It really has to do with "twin odd numbers", not just primes. When $n \in \mathbb N$ is odd, as polynomials we have $t^n-t = (t-1)(t^{n-1}+\ldots+t)$ and $t^n-t = (t+1)(t^{n-1}-t^{n-2}+\ldots-t)$, where the second factors have $n-1$ terms. So for any odd integer $x$, $x^n - x$ is divisible by $2(x-1)$ and by $2(x+1)$. In particular if $y = x+2$, $x^n + y^m \equiv x + y \equiv 0$ mod $x+y=2(x+1)=2(y-1)$ for any positive odd integers $m$ and $n$.

-

Hint $\rm\ mod\ p+1\!:\:\ p\:\equiv\:\! {-}\!1\ \Rightarrow\ p^m + (p+2)^n\equiv\: (-1)^m + 1^n\equiv\: 0\:$ when $\rm\:m\:$ is odd

Alternatively let $\rm\:p = 2k-1,\ q = 2k+1.\:$ If $\rm\:m,n\:$ are odd then by the binomial theorem

$$\begin{eqnarray}\rm p^m + q^n &=&\rm\: (2k-1)^m + (2k+1)^n \\ &=&\rm\: (-1)^m + (-1)^{m-1} 2mk + 4k^2(\cdots)\: +\: 1 + 2nk + 4k^2(\cdots) \\ &=&\:\rm 2\:(m+n)\:k\ +\ 4k^2(\cdots) \end{eqnarray}$$

which is divisible by $\rm\:p+q = 4k\:$ since $\rm\:m+n\:$ is even.

-

Let our numbers be $p$ and $q$, where $q=p+2$. Then $p\equiv -q \pmod {p+q}$, and therefore $$p^p+q^q \equiv (-q)^p +q^q=q^p((-1)^p +q^2)=q^p(q^2-1)\pmod{p+q}.$$ So it is enough to show that $p+q$ divides $q^2-1$. But $p+q=2q-2$, and $q^2-1=(q-1)(q+1)$, so since $q+1$ is even the result follows.

-