Show that the remainder when 2^1990 (2 to the power of 1990) is divided by 1990 equals 1024.

Note that the prime factorization of 1990 is 2 × 5 × 199.
Then consider x = 2¹⁹⁸⁰ (mod 1990).

By Fermat's Little Theorem, 2¹⁹⁸ = 1 (mod 199).
Hence 2¹⁹⁸⁰ = (2¹⁹⁸)¹⁰ = 1 (mod 199).

Also, 2¹⁹⁸⁰ = (2⁴)⁴⁹⁵ = 1⁴⁹⁵ = 1 (mod 5).

Therefore 2¹⁹⁸⁰ = 1 (mod 995).
(Consider x = 1 + 199t, for some integer t.
Then x = 1 + 199t = 1 (mod 5).
Hence 199t = -t = 0 (mod 5), and so t = 0 (mod 5).
Letting t = 5s, we obtain x = 1 + 995s, for some integer s.
Ref.: Chinese Remainder Theorem.)

Equivalently, 2¹⁹⁸⁰ = 1 or 996 (mod 1990).
But 2¹⁹⁸⁰ = 0 (mod 2), and so 2¹⁹⁸⁰ = 996 (mod 1990).

Therefore 2¹⁹⁹⁰ = 2¹⁹⁸⁰ × 2¹⁰ = 996 × 2¹⁰ = (996 × 2) × 2⁹ = 2 × 2⁹ = 2¹⁰ = 1024 (mod 1990).

Posted by Nick Hobson on 2004-07-06 14:16:40