Mod 7

What is the remainder when 3 ²⁰⁰¹ 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.

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 ²⁰⁰¹ 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 ⁿ (mod 7) = 3 x [3 ^n-1 (mod 7)]

so

3 ¹ = 3(mod 7) = 3
3 ² = 3 x 3(mod 7) = 2
3 ³ = 3 x 2(mod 7) = 6
3 ⁴ = 3 x 6(mod 7) = 4
3 ⁵ = 3 x 4(mod 7) =5
3 ⁶ = 3 x 5(mod 7) = 1

Now we have 3 ⁶ = 1 mod 7 and it follows that 3 ¹⁹⁹⁸ = (3 ⁶ ) ³³³ = 1 ³³³ (mod 7) = 1

But 3 ²⁰⁰¹ = 3 ¹⁹⁹⁸ x 3 ³ = 1 x 3 ³ (mod 7) = 6
therefore the remainder is 6 when 3 ²⁰⁰¹ is divided by 7.