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