Finding 13^99

Date: 11/21/2001 at 02:20:47
From: B. Potter
Subject: Finding power of number

What is the units digit of 13 to the 99th power? How do you figure it 
out?

Date: 11/21/2001 at 05:43:47
From: Doctor Pete
Subject: Re: Finding power of number

Hi,

You can use a bit of algebra to figure it out. First, notice that this 
is the same as finding the remainder of 13^99 when divided by 10.  
Second, since

     13 = 10 + 3,

you can see that 13^99 has the same remainder when divided by 10 as 
the remainder when 3^99 is divided by 10. A similar example with 
smaller numbers is

     12 = 10 + 2,
so
     1728 = 12^3 = (10+2)^3 = 10^3 + 3(10^2)(2) + 3(10)(2^2) + 2^3
          = 10(100+60+12) + 2^3
          = 10(172) + 2^3,

and you'll notice that both 1728 and 8 have the same remainder when 
divided by 10.

Next, notice that

     3^99 = 3^(98 + 1) = 3((3^2)^49) = 3(9^49),

and in a similar manner as before, we note that

     9 = 10 - 1,

so the remainder when 9^49 is divided by 10 is the same as when 
(-1)^49 is divided by 10, which will be -1. If a remainder of -1 
sounds strange, then just think of it as a remainder of 9, because we 
can either say

     249 = 240 + 9 = 10(24) + 9,
or
     249 = 250 - 1 = 10(25) - 1.

So if the remainder when 9^49 is divided by 10 is 9, then the 
remainder of three times this number is the same as the remainder of 
3(9) = 27, which is 7. So the last digit is 7.

This question really depends on a thorough understanding of quotients 
and remainders. In particular, it depends on the fact that if we 
divide two numbers a and b by a third number, say m, then the sum of 
the remainders of a and b is equal to the remainder of the sum, and 
the product of the remainders is equal to the remainder of the 
product. For example, if

     a = 25, b = 36, m = 7,

then a/m leaves a remainder of 4, and b/m leaves a remainder of 1. 
Then

     a+b = 61

leaves a remainder of 4+1 = 5, and

     ab = 900

leaves a remainder of 4(1) = 4. These properties are very powerful, 
because it allows us to calculate remainders of large numbers without 
having to divide the number explicitly, as we saw with this particular 
example. If we use the language of congruences, then we write

     a == b (mod m)

to represent the fact that the difference a-b is divisible by m (no 
remainder). We say, "a is congruent to b modulo m."  If you think 
about it a bit, this also represents the fact that a and b have the 
same remainder when divided by m.

Then the two properties imply that if

     a == a' (mod m),
     b == b' (mod m),
then
     a+b == a+b (mod m),
     ab == a'b' (mod m).

If a = b, we find in particular

     a^2 == (a')^2 (mod m),

and by repeating this rule as many times as we wish, we obtain the 
more general result

     a^p == (a')^p (mod m).

So, to apply this rule to the original problem, we let a = 13, p = 99, 
m = 10. It follows that

     13 == 3 (mod 10),

since 13-3 = 10 which is divisible by 10. Therefore,

     13^99 == 3^99 (mod 10).

Then we used a bit of algebra to rewrite 3^99 in a way which will help 
us, namely

     3^99 = 3(9^49),

since

     9^49 == (-1)^49 (mod 10).

Then applying the rule again, we find

     3(9^49) == 3(-1)^49 (mod 10).

But (-1)^49 = -1, so 3(-1)^49 = -3, and

     -3 == 7 (mod 10).

So, to put it all into one big chain of reasoning, we have

     13^99 == 3^99 = 3(9^49) == 3(-1)^49 = -3 == 7 (mod 10).

Note that I used the symbol == to denote congruence, and the symbol = 
to denote equality.

Now you can see quite clearly how powerful congruences are, and how 
a few ideas about remainders can really save a lot of computation. 
I invite you to prove the formulas I stated above (hint: represent 
a = Qm + R, b = Sm + T, where Q, S are the quotients, and R, T are the 
remainders of a and b when divided by m).

Finally, if you're interested in the exact value of 13^99, it is

1907180854589209641162363757488357797106749590673031653701683922620122
07679844273858329666379998629245551661077.

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