Problem 9 Number Theory

Problem 9: Number Theory

Art of Problem Solving

Problem: Find the remainder when 20062007 is divided by 2008. Solution: We want to find 20062007 (mod 2008). Note that: x ≡ 20062007 ≡ (−2)2007

(mod 2008)

Also note that 2008 = 251 · 8, so we can break this down into two cases that are easy to calculate: x ≡ (−2)2007 ≡ 0

(mod 8)

x ≡ (−2)2007 ≡ −128 ≡ 123

(mod 251)

From the first equivalence, we see that x is of the form 8k for some integer k. We can substitute this into the second equivalence and solve: 8k ≡ 123

(mod 251)

k ≡ 235

(mod 251)

We found x to be of the form 8k, so x = 8(235) = 1880 .

Solution was written by Sean Soni and compiled from Art of Problem Solving Forums.