Ages ago (last Spring), Sharp Brains offered this puzzle: What is the remainder when $100^{100}$ is divided by 11?

So I worked it into my day-before-vacation algebra lesson, and duplicated it for an algebra class I covered (but only started for the last algebra class of the day, since we had to leave for the holiday talent show)

First we played my “little bit of math magic” (write down a number, square it, save the last digit, square that, save the last digit, multiply by your original number. What do you have? Your answer was…). Only I told them in advance that they could use calculators, if they had them, but they didn’t need them, only without calculators they wouldn’t be able to stump me…. I did a round with each class, then a second round where I restricted them to 10 – 40 or something like that, and suggested they write down all the numbers and answers, and challenged them over break to figure out what was going on…

Second we worked on the really big number. Here’s roughly what I said:

What’s the remainder when 20 is divided by 3? [2]. When 100 is divided by 7? [2] Did you have to do remainder math in middle school? [no] Here’s one way to look at remainder math: What’s the remainder when 100 is divided by 11? [1]. Instead, we can write this as 11n + 1. It doesn’t much matter what n is (but what is it? [9]) since we are only interested in what’s left over.

continues below the fold —>

Even though remainders look pretty elementary-school to you, remainder math is a big deal, it opens up a whole branch of abstract algebra to us, ultimately algebra without numbers, which is way cool. Now the guy who really broke ground on this, he was French (write Evariste Galois on the board, debate with self, but out loud, whether the accent aigu should be written on the capital E. Apparently it doesn’t matter, as the E in Evariste is unaccented). When Galois was my age, he’d been dead for 20 years.

I continue to a bowdlerized version of Galois’ life, implying that Cauchy sabotaged his contest entries, talking about politics, including the difference between early 19th century French Republicanism and modern American Republicanism, dueling, prison, a girl, and concluding that he really was pretty stupid. At least one class saw it coming, and guessed the duel. I was impressed.

Anyhow, we go on to find the remainder when 10,000 is divided by 11 by rewriting as $(100)^2$, substituting $(11n + 1)^2$, expanding as $121n^2 + 22n + 1$, and semi-factoring as $11(11n^2 + 2n) + 1$, and rewriting as 11k + 1 (but in one class we rewrote as 11L + 1, since the kid whose name starts with L was sitting in front, and he complained that we don’t use his initial, and in one of the covered classes we used 11(@) where I used a hyeroglyphic for a sea monster in place of the “@”). No matter how we slice it, 11k + 1 is one more than a multiple of 11. Time for the challenge.

What is the remainder when 100 is divided by 11? (out loud, and on board) [1, 1, 1, the whole class is answering]. Oh, oh, oh, ohohohoh… I forgot the exponent. (Writes $100^{100}$). So there you go. Convince your partner. When you agree, convince the pair in front of you or in back of you. And when you have 4 together, you can present to the class. And when we are done, everyone can play Set (Set is a great game, and a great motivator).

And so it went. And in the two classes where we had a full period, we had kids go to the front and answer and explain. Did I give it away in advance? Sure. But they had to understand the explanation, and fill in their own details, they had to arrive at at least semi-standard notation, and they needed to be clear enough to convince a room full of 9th graders.

The best was when two kids on the opposite side of the room went a bit off track. K. decided that it was important that as you multiplied 10 by 10 and by 10 again, and so on, the remainder when divided by 11 alternated between 1 and 10. As a result, we could not just conclude that 1 followed by a bunch of 0s would have a remainder of 1. S. answered him by pointing out that there was no issue with powers of 100, only (and he left out details that I am supplying) with odd powers of 10.

And then everyone played.

What better way to send them off on vacation? A puzzle, some math history, a little bit of abstract algebra, and a pattern recognition game.

1. December 23, 2007 am31 11:30 am 11:30 am

Another way to see that the remainder is 1 when you divide 100^100 by 11 is by the binomial theorem expansion of (99+1)^100.

(99+1)^100 = (100C0)99^100 + (100C1)99^99 + (100C2)99^98 + (100C3)99^97 + … + (100C99)99^1 + (100C100)99^0

where (aCb) is the binomial coefficient, or (a!/(b!)(a-b)!).

In the expansion above you can factor out 99 (which is 11×9) from each term except for the final term. So, the remainder when you divide 100^100 by 11 is the final term of the binomial expansion which is (100C100)x99^0 = 1×1 = 1.

2. December 23, 2007 am31 11:36 am 11:36 am

Isn’t that neat? I love this stuff.

Yesterday was with freshman who have just been multiplying and factoring polynomials of low degree… binomial expansion was not likely from them. But there’s no reason not to see this again, later. Maybe, if I get a few minutes in January, I will throw this one at my combinatorics class. They know from expansion…

Thanks for the comment.