#### You may also like ### Purr-fection

What is the smallest perfect square that ends with the four digits 9009? ### Old Nuts

In turn 4 people throw away three nuts from a pile and hide a quarter of the remainder finally leaving a multiple of 4 nuts. How many nuts were at the start? ### Prime AP

What can you say about the common difference of an AP where every term is prime?

# Mod 7

##### Age 16 to 18Challenge Level

What is the remainder when 3 2001 is divided by 7?

Zi Heng Lim and Hagar El Bishlawi found a pattern when they raised 3 to a power, divided it by seven and found the remainder.

 3 1 = 3 3 2 = 9 3 3 = 27 3 4 = 81 3 5 = 243 3 6 = 729 --Pattern Found-- 3/7=0 R3 9/7=1 R2 27/7=3 R6 81/7=11 R4 243/7=34 R5 729/7=104 R1 3 7 = 2187 3 8 = 6561 3 9 = 19683 3 10 = 59049 3 11 = 177147 3 12 = 531441 2187/7=312 R3 6561/7=937 R2 19683/7=2811 R6 59049/7=8435 R4 177147/7=25306 R5 531441/7=75920 R1

When you divide the exponent 2001 by the number 6, the answer will be 333 R3. The third number in the remainder pattern is 6, therefore 3 2001 divided by 7 has a remainder of 6, assuming that the pattern keeps repeating itself every six powers.

Can you prove that this pattern will keep repeating itself?

Pierce Geoghegan and Etienne Chan solved this problem using modulus arithmetic. This is Pierce's solution:

Initially we use the fact that 3 n (mod 7) = 3 x [3 n-1 (mod 7)]

so

3 1 = 3(mod 7) = 3
3 2 = 3 x 3(mod 7) = 2
3 3 = 3 x 2(mod 7) = 6
3 4 = 3 x 6(mod 7) = 4
3 5 = 3 x 4(mod 7) =5
3 6 = 3 x 5(mod 7) = 1

Now we have 3 6 = 1 mod 7 and it follows that 3 1998 = (3 6 ) 333 = 1 333 (mod 7) = 1

But 3 2001 = 3 1998 x 3 3 = 1 x 3 3 (mod 7) = 6
therefore the remainder is 6 when 3 2001 is divided by 7.