Solution to puzzle 87: 2004

Evaluate 2²⁰⁰⁴ (modulo 2004).

---

Note that 2004 = 2² × 501.
Since 2 is relatively prime to 501, by Euler's Totient Theorem, 2^phi(501) 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 2¹⁹⁹² = (2³³²)⁶ 1⁶ 1 (mod 501).

Then clearly 2¹⁹⁹² = (2²)⁹⁹⁶ 0 (mod 4).
We now combine these two results to calculate 2¹⁹⁹² (mod 2004).

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

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

Source: Inspired by Remainder, on flooble :: perplexus

Back to top