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?

Thank you for your help.

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 
addresses.

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).

The problem you asked about could be expressed

  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.

Does this help? Write back if you'd like to talk about this some more, 
or if you have any other questions.

- Doctor Jubal, The Math Forum
  http://mathforum.org/dr.math/