Trick of Mind

2 Responds so far- Add one»

1. 1. AnonymousCam Said：
   July 25th, 2012 at 12:21 am

   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：
   July 25th, 2012 at 2:04 am

   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.

Post a reply