Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Using Modular Arithemtic to Find a Remainder

Date: 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/ 
Associated Topics:
College 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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/