It's been ages since I last posted any math problems on here, mostly because the response to previous attempts was almost always poor, but this time I've got a nice little challenge which is simple enough for almost anyone to get with just a little bit of thought. Here it goes:

When you divide 12 by 5, theIt's not a trick question, but the solution is as straightforward as it gets if you go about it correctly.remainderis 2; it's what's left over after you have removed all the 5s from the 12. When you raise 4 to the fifth power (that is, 4^5), you multiply four by itself five times: 4×4x4×4x4, which equals 1,024.What is the remainder when you divide 100^100 by 11?

hello abiola,

the answer seems obviously 1. correct me if i am wrong.

Posted by: Beedaman | May 22, 2007 at 01:51 PM

You are indeed correct. Of course, for most people the big challenge is recognizing precisely why this is "obvious" ...

Posted by: Abiola | May 22, 2007 at 10:41 PM

Going by thought alone (for the sake of illustration i have written it here), one could realize that:

[(100^100)/11] x 1 = [(100^100)/11] x (100/100) = [(100^100)/100] x (100/11) = [big even integer] x [(99/11)+(1/11)] = [ big even integer] x [(an odd integer, 9) + (1/11)]. I'm a Biologist not a Mathematician, but this is the best way i can explain how I arrived at the answer 1.

Posted by: Jubril | May 23, 2007 at 09:40 PM

Or you could guess and check, knowing initially that the answer had to be between 1 and 10 (inclusive). 100^100 is basically 1 with quite a lot of zeros, subtract one from that and you get an all 9 integer (999999...), which is clearly a multiple of 11.

Posted by: Jubril | May 23, 2007 at 10:09 PM

Correction, second explanation = invalid, the first one is the best i could come up with.

Posted by: Jubril | May 23, 2007 at 10:15 PM

I think the second explanation is close - you could explain it that any power of 100 is 1 followed by an even number of zeroes, and any number that is an even number of 9s (99, 9999, 999999, etc) will be exactly divisible by 11. Since any power of 100 is exactly 1 more than an exact multiple of 11 (100 = 99+1, 10000 = 9999+1), the remainder of 100^100 / 11 is 1.

Posted by: Andrew | May 24, 2007 at 12:51 AM

You, sir, have it exactly right. A conceptually clearer (and more general) explanation is as follows.

100 modulo 11 = 1, and since a*b mod p = (a mod p) * (b mod p), we have that 100^100 mod 11 = (100 mod 11)^100 = (1 mod 11)^100 = 1 mod 11.

Posted by: Abiola | May 24, 2007 at 01:00 AM