May 17, 2007

## #22 Brain Teaser: The Really, Really, Really Big Number

By: Caroline Latham

Here is new brain teaser written by puzzle master Wes Carroll.

**The Really, Really, Really Big Number**

**Difficulty:** HARD

**Type:** MATH (Numerical/Abstract)

**Intimidation Factor:** HIGH — but don’t be scared!

**Question:**

When you divide 12 by 5, the *remainder* is 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: 4x4x4x4x4, which equals 1,024.

What is the remainder when you divide 100^{100} by 11?

—

**Solution:
**1

**Explanation:
**This one is so sneaky.

First, consider 100 divided by 11. The remainder here is 1. Now consider the remainder when 100x100 is divided by 11. Don’t do it on your calculator or on paper. Rather, consider that you have one hundred hundreds, and each of them has a remainder of 1 when divided by 11. So, go through each of your hundred hundreds and divide it by 11, leaving remainder 1. Then collect up your remainders into a single hundred, and divide it by 11, leaving a remainder of 1. This process can be extended to dividing 100x100x100 by 11, and indeed, to dividing any power of 100 by 11.

**Next brain teaser in SharpBrains’ top 25 series:**

- 23. Please consider Linda’s job prospects

This was easy for me, but it still was quite delightful. I think that some people will think of this as impossible. *I’m so super * 🙂

BTW, why do you post the solution as documents? That’s slow.

Good for you! I think it sounds scary, but yes, it’s not that bad once you start working on it!

I post the answers as a separate document to avoid the temptation of just reading the answer before at least trying to solve it! I’m open to trying other means of hiding the answer if you have ideas.

I’m glad I came across this sight. Seems over time a person loses the ability to solve simple Math. I’ve been accused of being stupid but now don’t feel as such. Thanks!

Welcome Lizzy! Keep coming back for practice, and you’ll get better and faster at the teasers!

Very nice. I’m going to make the number a little smaller (small enough to lure some poor souls into doing hand calculations, but still way too big for a calculator) and give it to my high school students.

Btw, you may enjoy this trick (not really a puzzle) I share with my students.

Nice site (found it through the Carnival of Mathematics)

Let us know how it goes! I’m going to work on that trick!

Wonderful problem, Caroline!

It’s very hard for me not to use Remainder Theory, better known as Congruence Theorems in Number Theory.

10^2 is congruent to 1 modulo 11. Raise both sides to the 100th power and the result follows directly. However, your solution is far more instructive for students. Note that 10^1 leaves a remainder of 10 when divided by 11. Number theorists would write:

10 is congruent to -1 mod 11.

Therefore, 10^3 is also congruent to -1 mod 11. This translates to 1001 being divisible by 11, which it is, since 1001 = 7x11x13. Thus every odd power of 10 leaves a remainder of 10 when divided by 11. That’s why the problem you posed used a base of 100 — it guaranteed an even exponent so the remainder would be 1. Sorry for the technical stuff — number theory has always been my passion and my knowledge represents an infinitesimal part of what the pros know…

I hope you’ll visit my site — there are occasionally puzzles like this, although my primary goal is to provide enrichment lesson plans for math educators in grades 7–12. Good luck!

Dave Marain

Thanks for the analysis Dave- it’s great to hear other solutions and theories. I’ll definitely check out your site and please keep coming back here! And PS- the credit for the problem goes to Wes Carroll who is writing puzzles for us. You can follow the links to him at the top of the post.

There is much easier way to solve this. We are all aware that 99 is 9*11. We can easily derive, that all numbers 99…99 where the amount of nines is even, are a product of “some constant number” and 9*11. 100^n has always even number of zeros so there is an equivalent 99..99. No math needed to understand that the difference is 1.

Ok. The remainder is 1.

What is the solution?

The generic solution for all positive exponents is:

9*100^0+9*100^1+9*100^2+…+9*100^(n-1)

For this particular problem just substitute n=100.

So, I finally used the puzzle in class, though perhaps not exactly as you intended. It was with 2 9th grade, pre-vacation algebra classes, and the results are here.

Hello Jonathan, thanks for sharing that experience! We are very glad your students enjoyed the teaser, very impressive 🙂

Happy holidays

The number 100^100 may be written as,

(99 + 1)^(99 + 1). By the exponent law, a^m * a^n = a^(m + n),

we can rewrite to this,

(99 + 1)(99 + 1)^99

and futher,

(99 + 1)(99 + 1)(99 + 1)^98

and so on, down the line. Let a = (9)(11). We get,

(a^2 + 2a + 1)(a + 1)^98 =

(a^3 + 3a^2 + 3a + 1)(a + 1)^97 =

(a^4 + 4a^3 + 6a^2 + 4a + 1)(a + 1)^96 = .. = a^99 + [98 terms] + 1

We find that every term is divisible by 11 (a is divisible) except the very last one, 1.

The remainder is 1.

Here’s another quick one, which is learned from the above.

Using only 9s, express 100^100.

Well, it’s no trick at all. 9/9 = 1.

Ans. (99 + 9/9)^(99 + 9/9)

or (99 + 9/9)(99 + 9/9)^99

I think it’s one, I don’t have any crazy solution it’s just my gut instinct =P

My solution was a bit different.

10^0 mod 11 = 1

10^1 mod 11 = 10

10^2 mod 11 = 1

10^3 mod 11 = 10

Thus

10^n mod 11 = 1, if n is even, and

10^n mod 11 = 10, if n is odd!

Raising 100 to the 100 power is really not relevant. When you divide 100 by 11 the remainder is 1. In this case, no matter how many zeros will be in the “big number”, you will still come out with a remainder of 1.

I used an invariant property of multiples of 11:

n=k*11 in n the sum of odd position digits is equal to the sum of even position digits.

Thus, 100^n=10^2n has 2n+1 digits, and the previous multiple of 11 must have 2n digits.

so it can only be a number like 999…999, and the remainder must be 1

answer is one

100 is of the form to 11k+1 .

now (11k+1)*(11k+1)=11p+1

hence you raise 100 to any power it will always give remainder 1 on being divided by 11

childs play got the answer immediately

1

We can also prove this by the Method of Induction:

Problem: (100)^n / 11 gives remainder 1

To prove that any power of 100 gives Remainder 1.

(100)^1 / 11 gives remainder 1 (after dividing to 99) .… 1

(100)^2 / 11 gives remainder 1 (after dividing to 9999)

Thus (100)^n / 11 gives remainder 1 (our Hypothesis from the above statements)

Now, (100)^(n+1) = 100 * (100)^n

Dividing the above by 11 we see that (100)^n already gives remainder 1, and the other 100 also gives remainder 1 (as per statement .… 1).

Thus, all powers of 100 shall give remainder 1 when divided by 11. (Proved)

I also liked the solution given by: Anthuan

I did this the same way Dave did it, by instinct.

10 mod 11 === -1 mod 11, so

10^100 mod 11 === (-1)^100 mod 11 === 1 mod 11