Prove that $p^q+q^p\equiv p+q \mod pq$

Question

I can prove $p^{q-1}+q^{p-1}$ is congruent to 1 mod $pq$ very easily, but with the $p+q$ it doesn't fit a theorem I can find. The only ones I find say if they are congruent to $b$. I get one is congruent to $p$ and the other is $q$, these are obviously different numbers.

Answer 1

Show $p^q+q^p$ and $p+q$ have the same residues mod $p$ and mod $q$.

Answer 2

I think you need to assume that $p$ and $q$ are different primes.

Hint: modulo $q$, $$p^q\equiv p^{q-1}p\equiv p\quad\hbox{and}\quad q^p\equiv0^p\equiv0\equiv q\ .$$

Answer 3

Take $\pmod p$. Then (by F(little)T), $p^q+q^p \equiv q \pmod p$. Similarly, $p^q+q^p \equiv p \pmod q$. Now let $n$ be the expression. Then $n = pr_1+q = qr_2+p$. Take this equation $\pmod p$ to arrive at $q \equiv qr_2 \pmod p \implies r_2 \equiv 1 \pmod p$. Therefore, $r_2 = r_3p+1$.

Then $n = qr_2+p = q(r_3q+1)+p = pqr_3+p+q$ as desired.

Answer 4

If you want to use your theorem, note that

$$p+q\equiv(p+q)(p^{q-1}+q^{p-1})=p^q+q^p+pq^{p-1}+qp^{q-1}\equiv p^q+q^p\ \ (\text{mod pq)}$$

Answer 5

Hint $\ ap\mid a^p-a\ $ if prime $\,p\nmid a.\,$ Let $\,a=q\,$ prime, and symmetrize.