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/