Flickr

• www.flickr.com
 More of Abiola_Lapite's photos

May 21, 2007

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

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

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.

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.

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

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.

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.

The comments to this entry are closed.