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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.