Associated Topics || Dr. Math Home || Search Dr. Math

### 2^99 Divided by 99

Date: 08/27/2001 at 01:40:12
From: sanjeev
Subject: Number system

What is the remainder when you divide 2(to the power 99) by 99?

That is:          99
2
-----
99

Date: 08/27/2001 at 14:25:28
From: Doctor Greenie
Subject: Re: Number system

Hello, Sanjeev -

We can't directly find an answer to this question, even using a
calculator or most computers, because the number 2^99 is going to be
represented approximately. But we can find the answer using just a
little mental arithmetic.

The idea behind the method of solution for this problem is that, for
each successive power of 2, the actual value of 2^n is not important
to us; the only important part is the remainder when that power of 2
is divided by 99.

Suppose we know that 2^n leaves remainder r when divided by 99. Then
we know that

2^n = 99a + r for some integer a

Now consider the next power of 2, which is 2^(n+1).  We have

2^(n+1) = 2*(2^n) = 2*(99a + r) = (2*99)a + 2r

The (2*99)a is clearly divisible by 99, so the remainder when 2^(n+1)
is divided by 99 is the remainder when 2r is divided by 99. We have
two possible cases:

(1) if 2r < 99, then the remainder when 2^(n+1) is divided by 99
is 2r

(2) if 2r > 99, then the remainder when 2^(n+1) is divided by 99
is 2r-99

Now let's consider that we know the remainders when 2^m and 2^n are
divided by 99 are r1 and r2, respectively:

2^m = 99a + p
2^n = 99b + q

Then what is the remainder when 2^(m+n) is divided by 99?  We have

2^(m+n) = (2^m)(2^n)
= (99a+p)(99b+q)
= (99^2)ab+(99)aq+(99)bp+pq

Clearly, the remainder when this number is divided by 99 is pq; or, if
pq > 99, the remainder is (pq minus some multiple of 99).

So, to find the remainder when 2^99 is divided by 99, we want to write
2^99 as a product

2^99 = (2^a)(2^a)...(2^a) * (2^b)

where we know that the remainder is equal to 1 when 2^a is divided by
99 - because then the remainder when 2^99 is divided by 99 is the same
as the remainder when 2^b is divided by 99.

So we start finding the remainders when successive powers of 2 are
divided by 99:

power of 2   remainder
------------ -----------
1            2
2            4
3            8
4           16
5           32
6           64
7          128 = 29
8           58
9          116 = 17
10           34
11           68
12          136 = 37
13           74
14          148 = 49
15           98
16          196 = 97
17          194 = 95
18          190 = 91
...          ...

I could continue this table until I find a power of 2 for which the
remainder when divided by 99 is equal to 1. However, having worked a
number of similar problems, I know a shortcut to finding that power.
I have actually continued this table farther than I needed to; here is
why.

I found that the remainder when 2^15 is divided by 99 is 98:

2^15 = 99n + 98

I can write this also as

2^15 = 99(n+1) - 1

so the remainder 98" can be considered as a remainder of -1.

But then I know that when I multiply 2^15 times 2^15, the remainder
will be (-1) times (-1), which is 1.

So I know that

(2^15)(2^15) = 2^30

has a remainder 1 when divided by 99.

Again, I could have continued my table to find this remainder of 1 for
when 2^30 is divided by 99; however, I used my experience to stop when
I found the remainder of "-1" for 2^15.

And now we have

2^99 = (2^30)(2^30)(2^30)(2^9)

and, since the remainder when 2^30 is divided by 99 is 1, the
remainder when 2^99 is divided by 99 is the same as the remainder when
2^9 is divided by 99 - and we found in our table that this remainder
is 17.

I hope this response helps. Please write back if you have any further
questions.

- Doctor Greenie, The Math Forum
http://mathforum.org/dr.math/

Associated Topics:
High School Exponents

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search