If p and q are distinct primes, show that p^q + q^p = p + q (mod pq)
p,q are prime
from fermat’s little theorem
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
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.