## Wednesday, September 16, 2009

### Finding the last digits of 7 to the 9999th power

Now here is a question. Suppose you took 7 to the 9999th power. That would be a number with 8450 digits. In 12 point type, that is a number about 70 feet long. What are the last three digits of that number? Why would we ask such a question? No reason, that’s just what we do.

One problem solving strategy is to create an organized list and look for patterns. Using Excel, here are the first 10 powers of 7 (formulas are listed in column C).

 A B 1 7 7 2 49 =A1*7 3 343 =A2*7 4 2401 =A3*7 5 16807 =A4*7 6 117649 =A5*7 7 823543 =A6*7 8 5764801 =A7*7 9 40353607 =A8*7 10 282475249 =A9*7

No obvious patterns seem to jump out and the numbers are already getting pretty big. Is there a better way? Asking for the last three digits is the same as asking for the remainder when you divide by 1000. Excel has a modulo function we can use to find the last three digits of the powers of 7. We only need to multiply these values by 7 to find the last the last three digits of the next power of 7 and the mod function returns only the last three digits.

As a shot in the dark, what is the value of the first 25 values for the powers of 7 mod 1000? It would be very cool is some relatively small power of 7 ended in 001 (or written in mod notation: 7x mod 1000 ≡ 1) since powers of that number would also end in 001.

 A B C 1 7 2 49 =MOD(B1*7,1000) 3 343 =MOD(B2*7,1000) 4 401 =MOD(B3*7,1000) 5 807 =MOD(B4*7,1000) 6 649 =MOD(B5*7,1000) 7 543 =MOD(B6*7,1000) 8 801 =MOD(B7*7,1000) 9 607 =MOD(B8*7,1000) 10 249 =MOD(B9*7,1000) 11 743 =MOD(B10*7,1000) 12 201 =MOD(B11*7,1000) 13 407 =MOD(B12*7,1000) 14 849 =MOD(B13*7,1000) 15 943 =MOD(B14*7,1000) 16 601 =MOD(B15*7,1000) 17 207 =MOD(B16*7,1000) 18 449 =MOD(B17*7,1000) 19 143 =MOD(B18*7,1000) 20 1 =MOD(B19*7,1000) 21 7 =MOD(B20*7,1000) 22 49 =MOD(B21*7,1000) 23 343 =MOD(B22*7,1000) 24 401 =MOD(B23*7,1000) 25 807 =MOD(B24*7,1000)

Holy Math Smack! 720 ends in 001 or 720 ≡ 1 mod 1000, then the pattern begins to repeat. That means that 720 ≡ (720 )n ≡ 1 mod 1000. So, think of 79999 as 720 x720 x720…719 . so 79999 ends on the 19th step of a repeating 20 step cycle. That value, according to the Excel sheet, is 143. QED. (that is Latin abbreviation you put at the end of a proof. I think it means “Thank God its over” but you should google it to be sure).

So even though 79999 is impossibly large on the scale of 8th grade math, we can make some statements about it, such as the last three digits have to be 143. Now, can you find the first three digits?

Clock Arithmetic

The problem above makes use of a repeating pattern in the last three digits of the powers of 7.

Repeating patterns such at this come up often enough to be interesting. Here is a simple case that would be accessible to 4th or 4th graders.

My friend, Mary O’Dell works in a candy shop. Part of her job is to bag the candy when a fresh batch comes out of the kitchen. As one of the benefits of working at the shop, she gets to keep any candies left over after bagging – that is, if there are some candies left but not enough to fill a whole bag, she gets to keep them. Today she is bagging candies 9 to a bag and the cooks made 665 in this batch. How many candies does Mary get to keep? What are some numbers that would leave Mary several candies? What are some numbers that would leave her with no leftovers at all?

Clock arithmetic is a common example. If it is 8:00 am now, what time will it be 133 hours later?

A mathematician would ask, “what are the patterns in these kinds of problems?” The first thing we’d need is a notation – a way of writing these ideas down. In this case us a mod notation. If we want to look at Mary O’Dell bagging 9 candies per bag then we can start with the number of candies which was 665 in the example above, then designate the number is a bag (or the number in any group) by using the notation “mod 9”. The notation would be 665 mod 9. We use a congruence notation rather than an equal sign because we are trying to say these are numbers with the same remainder when divided by 9 and these numbers are not equal, their remainder is when they are divided by 9. We use the notation ≡ and we read it as “is congruent to” so we would write 665 mod 9 ≡ 8 and we read it as “666 mod 9 is congruent to 8”

#### 1 comment:

1. Great pattern Steve, and I loved "Holy Math Smack". Gazooks. It's Mathman. Where is Robin?

I think the clock arithmetic explanation is nice and clear. Hope others agree.