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/