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

### 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/
```
Associated Topics:
High School Exponents
High School Number Theory

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