Using Modular Arithemtic to Find a RemainderDate: 08/06/2008 at 04:57:28 From: Irene Subject: remainder of modulus 13 Could you devise a simple rule to find the remainder of a number when it's divided by 13? Date: 08/08/2008 at 13:10:14 From: Doctor Ali Subject: Re: remainder of modulus 13 Hi Irene! Thanks for writing to Dr. Math. If you are looking for a very fast method that can be applied such as when we want to find the remainder for division by 3 or 9, I would say that unfortunately such a method doesn't exist. But don't worry. There are still some things that you can do to rev up the process. We know that each number N can be written as the sum of each of its digits times a power of 10. For example, 267 can be written as: 2*100 + 6*10 + 7*1, or 2*10^2 + 6*10^1 + 7*10^0 Writing that a little more formally using sigma notation: n --- N = ) 10^i d_(i+1) = 10^0*d_1 + 10^1*d_2 + ... + 10^n*d_(n+1) --- i=0 where d_(i+1)'s are the digits of N. For example if we have, N = 267 Then, d_1 = 7 d_2 = 6 d_3 = 2 So, it is enough to find the remainder of the powers of ten when divided by 13. I've done this for the first few powers. See below: n | 10^n | 10^n mod 13 -----+----------------------------+------------- 0 | 1 | 1 1 | 10 | 10 2 | 100 | 9 3 | 1000 | 12 4 | 10000 | 3 5 | 100000 | 4 6 | 1000000 | 1 7 | 10000000 | 10 8 | 100000000 | 9 9 | 1000000000 | 12 10 | 10000000000 | 3 11 | 100000000000 | 4 12 | 1000000000000 | 1 13 | 10000000000000 | 10 14 | 100000000000000 | 9 15 | 1000000000000000 | 12 16 | 10000000000000000 | 3 17 | 100000000000000000 | 4 18 | 1000000000000000000 | 1 19 | 10000000000000000000 | 10 20 | 100000000000000000000 | 9 21 | 1000000000000000000000 | 12 22 | 10000000000000000000000 | 3 23 | 100000000000000000000000 | 4 24 | 1000000000000000000000000 | 1 25 | 10000000000000000000000000 | 10 Can you see the pattern? The subsequence {1, 10, 9, 12, 3, 4} repeats. So, we got to something interesting. It means that if, n --- N = ) 10^i d_(i+1) --- i=0 Then, N = d_1 + 10 x d_2 + 9 x d_3 + 12 x d_4 + 3 x d_5 + 4 x d_6 + d_7 + 10 x d_8 + 9 x d_9 + 12 x d_10 + 3 x d_11 + 4 x d_12 + .... (mod 13) To reduce the numbers, you may note that, 10 = -3 (mod 13) 9 = -4 (mod 13) 12 = -1 (mod 13) So we can write the formula as, N = d_1 - 3 x d_2 - 4 x d_3 - d_4 + 3 x d_5 + 4 x d_6 + d_7 - 3 x d_8 - 4 x d_9 - d_10 + 3 x d_11 + 4 x d_12 + .... (mod 13) In other words, the subsequence that repeats is, {1, -3, -4, -1, 3, 4} Let's use the formula in an example. Assume we want to find the remainder of 4180456452 when divided by 13. As you see, I'm using a big number so that you can feel the difference and power! Remember those numbers, {1, -3, -4, -1, 3, 4}. So, instead of finding the remainder of that big number, we can find the remainder of the one below. I'm using the subsequence of numbers above times the digits of the big number, starting from the ones digit and moving up through the digits: ( 1x2 - 3x5 - 4x4 - 1x6 + 3x5 + 4x4 ) + ( 1x0 - 3x8 - 4x1 - 1x4 ) = 2 - 15 - 16 - 6 + 15 + 16 - 24 - 4 - 4 = -36 So, N = -36 (mod 13) = 3 (mod 13) Does that make sense? Please write back if you still have any difficulties. - Doctor Ali, 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/