Associated Topics || Dr. Math Home || Search Dr. Math

### Chinese Remainder Theorem and Modular Arithmetic

```
Date: 07/25/2001 at 13:34:55
From: Donald
Subject: Chinese Remainder Theorem

I was wondering if there is any way to solve this using the Chinese
Remainder Theorem rather than just trial and error.

Professor Carroll tries to divide his class into three equal groups,
but two students do not have a group. When he tries to divide them
into five groups, three people are left. Finally, a configuration of
seven equal groups leaves two people hanging. What is the smallest
possible number of students in Professor Caroll's class?

```

```
Date: 07/25/2001 at 16:32:12
From: Doctor Jubal
Subject: Re: Chinese Remainder Theorem

Hi Donald,

Thank you for writing to Dr. Math.

Yes, this is the sort of problem the Chinese Remainder Theorem

Throughout this explanation, I'll be using a notation from modular
arithmetic.

a mod m = b

This is a way of saying that when you divide a by m, you get b as the
remainder. If you feel you need a more thorough explanation of modular
notation, feel free to write back.

The Chinese Remainder Theorem deals with finding an unknown number
when you know that number's remainder when it is divided by several
different divisors (also called moduli). It says that a system of
equations like

n mod m_1 = r_1
n mod m_2 = r_2
...
n mod m_k = r_k

has exactly one solution n between 1 and m inclusive, where m is the
product of all the moduli, m = (m_1)(m_2)...(m_k), if all of the
moduli are relatively prime (some of them can be composite, but no two
of them can share any factor except 1).

n mod 3 = 2
n mod 5 = 3
n mod 7 = 2

3, 5, and 7 have no common factors besides 1, so the Chinese Remainder
Theorem tells us there is exactly one number between 1 and 3x5x7 = 105
that meets all these criteria.

I'll show you a couple of ways of actually finding this number. Both
methods rely of finding numbers M_1, M_2, ... M_k such that

M_i mod m_i = 1
M_i mod m_j = 0,  j =/= i

This means that for each of the moduli (m_1, m_2, ... m_k), we need to
find a number M_i that leaves 1 as the remainder when divided by m_i,
but is divisible by all the other moduli.

Once we find these numbers M_i we can write

n = (M_1*r_1 + M_2*r_2 + ... + M_k*r_k) mod m

which meets all our criteria for n.  This is because if we check our
work by taking n mod m_i we get

n mod m_i =
((M_1*r_1 mod m_i) + (M_2*r_2 mod m_i) + ... + (M_k*r_k mod m_i))
mod m

But remember that all the M_i's obey these equations

M_i mod m_i = 1
M_j mod m_i = 0,  j =/= i

so the expression for n mod m_i simplfies to

n mod m_i = (0*r_1 + 0*r_2 + ... + 1*r_i + ... + 0*r_k) mod m = r_i

which is what the original system of equations said. You might have
noticed that I pretty much ignored the "mod m" in the above equation
while simplifying it. I could do that only because m is divisible by
m_i.

Because M_i has to be divisible by all the moduli except m_i, it has
to be of the form

M_i = A(m / m_i)

Because M_i must leave a remainder of 1 when divided by m_i, it must
also be of the form

M_i = 1 - B(m_i)

Setting these two forms equal to each other, we get

A(m / m_i)          = 1 - B(m_i)

A(m / m_i) + B(m_i) = 1

The Extended Euclidean Algorithm lets us find values for A and B that
satisfy this equation.  You can find a very thorough description of
the Extended Euclidean Algorithm in the Dr. Math archives at

Integer Solutions to AX + BY = C
http://mathforum.org/dr.math/problems/prufrock.4.25.00.html

This answer relates to the more general equation AX + BY = C. In Dr.
Rob's second response, he shows how to reduce this equation to one of
the form we're dealing with (AX + BY = 1) and then explains in great
detail how the Extended Eudclidean Algorithm can solve that equation.

For example, in your problem involving Professor Carroll's class,
m_1 = 3, and m = 105, so m / m_1 = 35.  We can find M_1 by solving

35 A + 3 B = 1

and the Extended Euclidean algorithm will give us A = -1, B = 12. So
M_1 = -1(35) = -35. If you don't want to work with a negative number,
remember that the final calculation of n

n = (M_1*r_1 + M_2*r_2 + ... + M_k*r_k) mod m

is done modulo m, that is, it's the remainder when something is
divided by m. So, we can add any multiple of m to our value of M_1
without changing anything, and M_1 = -35 + 105 = 70 would work just as
well.

The Extended Euclidean Algorithm can require a lot of calculations.
Euler's theorem provides another way to find the M_i values. It
involves relatively few calculations, but forces you to work with some
very large numbers. If a and b are relatively prime, then

a^(phi(b)) mod b = 1            (Euler's theorem)

where phi(n) is the number of integers less than n that are relatively
prime to n.  1 is counted as being relatively prime to every number.
For example, phi(12) = 4 because 1, 5, 7, and 11 are relatively prime
to 12. (2, 3, 4, 6, 8, 9, and 10 all share at least one common factor
with 12). For prime numbers phi(p) = p-1 because every number less
than p is relatively prime to it.

Now, (m / m_i) is divisible by all the moduli except m_i, and so any
power of it will be, too. Also, all the moduli are relatively prime,
so m_i is relatively prime to (m / m_i). So, by Euler's theorem

M_i = (m / m_i) ^ phi(m_i)

satisfies all the criteria we set forth for M_i.

In the problem you gave, m_1 = 3, and m = 105.  3 is prime, so
phi(3) = 2. So,

M_1 = (105 / 3) ^ 2 = 35^2 = 1225

As before, we can add or subtract any multiple of m from M_1 without
changing anything, so M_1 = 1225 - 11*105 = 70 is a more manageable
number that will also work for M_1. This is just to demonstrate that
the two methods I've shown for finding M_i (the Extended Euclidean
Algorithm and Euler's Theorem) do give equivalent values.

I'll leave it to you to find M_2 and M_3 using either of these methods
and solve your problem using them.

or if you have any other questions.

- Doctor Jubal, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School 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
Math Forum Home || Math Library || Quick Reference || Math Forum Search