Excel Interactive Resource: Remainder

Challenge Level:

This month I'm revisiting an NRICH problem called Remainder which appeared in October 2002. As always, I've picked a problem where using a spreadsheet adds something powerful to the problem-solving process.

What is the remainder when 2²⁰⁰² is divided by 7?
What happens with different powers of 2?
Try to explain the mathematics behind what you discover.

The spreadsheet quickly produces a line of results, and leaves my brain free to think about the pattern I observe.

X	2^^x	remainder when divided by 7
1	2	2
2	4	4
3	8	1
4	16	2
5	32	4
6	64	1
7	128	2
8	256	4
9	512	1
10	1024	2

Download the Excel file Remains_of_Powers.xls (Right-click on the link, "Save Target As", and select where you want the file to be saved.)

Click on the cell C3 to see the formula =2^B3 in the formula bar. Remember the ^ sign makes Excel do powers.

Click on D3 to see the formula =MOD(C3,7) in the formula bar. The MOD function will calculate the remainder when the number in C3 is divided by 7.

Next these formulae are copied down for several rows to produce results for increasing powers of 2.

The remainders make a simple pattern : 2 4 1 2 4 1 2 4 1 . . .

Key Question:

Why does this pattern occur?

An explanation might go something like this:

Going to the next power of 2 doubles the previous answer, and therefore doubles the remainder. The remainder starts at 2 ( 2 divided by 7 has a remainder of 2). The next remainder is twice that(4), followed by another remainder, which is twice that (8). However when we divide we are taking out whole sevens, so the actual remainder this time is not 8 but 1 . Double that 1, to make the next remainder, 2 , which was the first remainder we calculated, so we are in a loop, and the pattern will continue endlessly.

That didn't take very long. Using the spreadsheet to generate the initial results got us through the calculation stage quickly, so we have plenty of time to consider a more general problem.

What about division by any number, not just 7?

And what about powers of numbers other than 2?

Here's an Excel sheet I created to explore these questions. Remains_of_Powers_2.xls (Right-click on the file name link, and "Save Target As", as usual). You'll see there are Spinners to control the new variables.

Have fun. And remember, it's accounting for the pattern that's the real solution.