Division of Large NumbersDate: 04/28/98 at 02:54:32 From: Luis Salazar Subject: Division of large numbers What is the remainder when 7^100 is divided by 13? Give a general strategy with explanation for this type of problem. Date: 06/24/98 at 16:07:36 From: Doctor Hauke Subject: Re: Division of large numbers Hi Luis, Your problem refers to "computing modulo n," a very effective way to handle large numbers. a mod n means the remainder that a leaves when divided by n. So, for example, 20 mod 13 = -19 mod 13 = 7 (20 and -19 differ by a multiple of 13, namely 39 = 3*13. 7 and -19 differ by 2*13, and so on. Can you give another number x with x mod 13 = 7 ?), or another example: 4 mod 3 = -2 mod 3 = 998 mod 3 = 1? You say "4 is congruent to 1 modulo 3." When adding and multiplying modulo n, you can always replace a number x by another number y as long as x is congruent to y modulo n: (x*y) mod n = (x mod n) * (y mod n). Example: Compute 11^2 mod 13. First look at a smaller number. 11 mod 13 = -2 mod 13, because 11-(-2) = 1*13. Now replace 11 with -2 everywhere: 11^2 mod 13 = (-2)^2 mod 13 = 4 mod 13 = 4. Thus we conclude that 11^2 mod 13 = 4. Check: 11^2 = 121 = 4+9*13, so indeed 11^2 and 4 differ by a multiple of 13. For powers, you use "Fermat's little theorem": n always divides a^n-a, or a^n mod n = a mod n. (Check some examples! The proof of this is easy with a bit of higher math, but I think it is over your head now.) Now back to your problem: 7^100 mod 13 = ? First we know that 13 divides 7^13-7 = 7*(7^12-1) as above. 13 of course doesn't divide 7, so it divides 7^12-1. So 7^12 mod 13 = 1 mod 13. Thus 7^24 mod 13 = (7^12*7^12) mod 13 = (7^12 mod 13)^2 = (1 mod 13)^2 = 1 And 7^36 mod 13 = (7^24*7^12) mod 13 = ... = 1 Can you complete the steps alone? You see this property will hold for ANY multiple of 12. 7^96 mod 13 = 7^(8*12) mod 13 = 1. We are almost there. So 7^100 mod 13 = 7^96 mod 13 * 7^4 mod 13 = 49^2 mod 13 = ... (you can surely continue from here alone, hint: 52 = 4*13). Just make sure that the number at the end lies between 0 and 12. That number is your solution. This was a rather long explanation (and thus took a bit for me to write up), so write back if you still have questions. -Doctor Hauke, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/