Challenge Level

$2^{2002} \div 7$ has what remainder?

An excellent explanation of a solution to this problem was offered by Hannah (The Mount School York), which is listed below (with a minor piece of editing at the end). Other excellent solutions were received from Mary (Birchwood Community School), Matthew (Queen Mary's Grammar School), Jong (Coleridge Community College), Clement and Stephanie.

Here is Hannah's solution:

To work out the remainder of 2 (to the power of 2002) I decided to work out 2 (to the power of smaller numbers) first to find a pattern.

2 (to the power of 5) = 32.

Divided by 7 = 4 Remainder 4

2 (to the power of 6) = 64.

Divided by 7 = 9 Remainder 1

2 (to the power of 7) = 128

Divided by 7 = 18 Remainder 2

2 (to the power of 8) = 256

Divided by 7 = 36 Remainder 4

2 (to the power of 9) = 512

Divided by 7 = 73 Remainder 1

2 (to the power of 10) = 1024

Divided by 7 = 146 Remainder 2

Now I have worked out a pattern that goes "1, 2, 4, 1, 2, 4...etc"
as the power goes up by one each time. I also noted that:

when the powers were divisible by 3 ( 6, 9...) - division by 7 gave a remainder of 1.

when the powers left a remainder of 1 when divided by 3 (7, 10...) the division by 7 gave an overall remainder of 2.

when the powers left a remainder of 2 when divided by 3 (the powers of 5, 8...) the division by 7 gave an overall remainder of 4.

I then worked out whether 2002 was in the 3 times table.

2002 divided by 3 = 667 with 1 remainder.

2002 was in the 3 times table +1 (it can be written in the form 3n
+ 1).

Therefore $2^{2002}$ has a remainder of 2 when divided by 7.