Subscribe via feed.

## Prime problem

Posted by Chris on July 22, 2012 – 1:33 pm

If p and q are distinct primes, show that p^q + q^p = p + q (mod pq)

This post is under “MathsChallenge” and has 2 respond so far.

### 2 Responds so far- Add one»

1. 1. AnonymousCam Said：

p,q are prime

from fermat’s little theorem

we know
p^(q-1) mod q = 1
so that means there exists an integer k such that
p^(q-1) = kq+1
multiply both sides by p
p^q = kpq+ p
which reveals that
p^q mod pq = p

by the same logic q^p mod pq = q

and since (p+q)mod pq = ( p mod pq + q mod pq) mod pq
we can just add the two terms on the left to give us

p+q mod pq = p+q mod pq

thus p^q + q^p = p+q mod pq

or something like that

2. 2. Chris Said：

Hi Cam. Yep, nicely done. That’s also how it was done on the source site. I can’t think of another approach, but no doubt there is one!

I posted it because I thought it looked sweet, and it went in a slightly different direction to the usual modulo arithmetic problems.

I’ll add that FLT can only be used when p and q are distinct. If q = p, then we’d have 2p^p = 2p^2 * p^(p-2) = 0 * p^(p-2) = 0 (mod p^2) as p ≥ 2

The source site owner, Kali Prasad Tripathy, had posted a link to the problem. I’ve supressed his post (for now). He also posted a response to the 2222^5555 + 5555^2222 problem (the source site was Kali’s also). Kali found me/ToM because I posted him a thank you for his proof of Bezout’s Identity.