2^99 Divided by 99Date: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/