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 29
8 58
9 17
10 34
11 68
12 37
13 74
14 49
15 98
16 97
17 95
18 91
... ...
The remainder when 2^15 is divided by 99 is 98, so:
2^15 = 99n + 98 or
2^15 = 99(n+1) - 1
thus the remainder 98 can be considered as a remainder of -1.
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.
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 the table above that this remainder is 17.
|
