Skip to main content.

Solution to puzzle 87: 2004

Evaluate 22004 (modulo 2004).


Note that 2004 = 22 × 501.
Since 2 is relatively prime to 501, by Euler's Totient Theorem, 2phi(501) congruent to 1 (mod 501).  (Where phi(n) is Euler's totient function.)
The prime factorization of 501 is 3 × 167, so we calculate phi(501) = (3 − 1)(167 − 1) = 332.
Hence 21992 = (2332)6 congruent to 16 congruent to 1 (mod 501).

Then clearly 21992 = (22)996 congruent to 0 (mod 4).
We now combine these two results to calculate 21992 (mod 2004).

If x congruent to 1 (mod 501), then x = 1 + 501t, for some integer t.
Hence 1 + 501t congruent to 1 + t congruent to 0 (mod 4), so that t congruent to 3 (mod 4).
So 1 + 501t = 1 + 501(3 + 4s) = 1504 + 2004s for some integer s.
That is, 21992 congruent to 1504 (mod 2004).
(The Chinese Remainder Theorem assures us that this solution is unique, mod 2004.) 

Now, working modulo 2004,  22004  = 21992 × 212
  congruent to 1504 × 212
  = (1504 × 22) × 210
  congruent to 4 × 1024
  congruent to 88.

Source: Inspired by Remainder, on flooble :: perplexus

Back to top