Number Theory 101
#3 (Chinese Remainder Theorem)
#3 (Answers)

math_class: Number Theory 101 (Chinese Remainder Theorem)

Disclaimers and Apologies

I said, in the last lesson, that we would get into factoring during this lesson. I had forgotten, at the time, that I wanted to hit on the Chinese Remainder Theorem. So, factoring will have to wait until next class.

In other news, I entirely blew creating a class for two weeks ago. And, last week, I was sick to the point of inertness for 80% of the week. My apologies for blowing the class two weeks ago. I hope the content is interesting enough to bring y'all back after this unscheduled hiatus.

Greatest Common Divisor (Continued)

One more interesting thing to note about the Greatest Common Divisor of two numbers (at least one of which is non-zero). The Greatest Common Divisor of two numbers is the smallest positive number which can be written as a linear combination of the two numbers.

It shouldn't come as a surprise to you that the proof of this takes advantage of the Well-Ordering Principle. Just about any mathematical statement containing "smallest number" requires the Well-Ordering Principle.

The proof creates a set of all positive numbers a * u + b * v where u and v are integers. It shows that the set is non-empty (one way to do this is to let u = a and v = b). Then, it takes the smallest member of that set, say d = a * x + b * y. Next, the proof uses the Division Algorithm to obtain integers q and r such that a = q * d + r where r is greater than or equal to zero and less than d. It goes on to show that the last expression there for a can be solved for r and the d can be replaced with a * x + b * y. The result is that r = a * (1 - q * x) + b * (-q * y). This shows that r has to be zero. If r were greater than zero and less than d then d was not the smallest element of the set. We can do the same for b.

That all shows that d divides both a and b. If c is some arbitrary divisor of a and b, then it also a divisor of a * x + b * y = d. Thus, c is less than or equal to d. We already showed that it can't be less-than, so it must be equal to.

That completes the sketch of the proof.

What good is this? Well, it turns out to be useful in lots of things to know that the Greatest Common Divisor of two numbers is one. It is useful to know that the only factor they have in common is one. In many situations, it is easier to demonstrate that the one can find an x and y such that a * x + b  y = 1 than it is to perform the whole Euclidean Algorithm on a and b.

However, one can also use the Euclidean Algorithm to find the linear combination. It gets somewhat ugly, but it's doable. We'll do an example with 1776 and 1492. First, we'll find the Greatest Common Divisor:

  • 1776 = 1492 * 1 + 284
  • 1492 = 284 * 5 + 72
  • 284 = 72 * 3 + 68
  • 72 = 68 * 1 + 4
  • 68 = 4 * 17 + 0

So, gcd(1776,1492) = 4. Now, we're going to substitute in backwards. We know, from the second to last equation that 72 - 68 * 1 = 4. From the equation above that, we know that 68 = 284 - 72 * 3. Substituting that information into the previous equation, we see that 72 - (284 - 72 * 3) * 1 = 4. We can go the whole way up the chain this way.

  • 68 = 284 - 72 * 3
  • 72 - (284 - 72 * 3) * 1= 4
  • 72 * 4 - 284 * 1 = 4
  • 72 = 1492 - 284 * 5
  • (1492 - 284 * 5) * 4 - 284 * 1 = 4
  • 1492 * 4 - 284 * 21 = 4
  • 284 = 1776 - 1492 * 1
  • 1492 * 4 - (1776 - 1492) * 21 = 4
  • 1492 * 25 - 1776 * 21  = 4

Whew... that was messy. If you want a real scare, look at the HTML for that sequence. Oi. You should try one of these for yourself to really get the feel of it. I'm sorry that I don't know of any way to explain it any better. The key is to keep trucking backwards, solving for the remainders and collecting like terms. It's just full-on algebraic manipulation.

Relatively Prime Numbers

You've probably heard of prime numbers. I hope so at least. I brushed by them a little bit in the first lesson. An integer is a prime number if it has no positive divisors except for one and itself.

There's another concept which is important in many instances in number theory. That is the concept of being relatively prime. Two numbers a and b are relatively prime if they don't have any of the same divisors except for one. Another way to say that is that their greatest common divisor is one. And, another way still to say it is that there exist integers x and y such that a * x + b * y = 1. One sometimes says "a is relatively prime to b" instead of saying that "a and b are relatively prime". It means the same thing. If a is relatively prime to b, then b is relatively prime to a.

It turns out that that last property will come in handy in many proofs later on in the course. For the moment, I just wanted to introduce the term because it will come in handy in the next two sections.

One thing to mention before we go on though---the number one is relatively prime to every integer.

Linear Congruences

We've done modular arithmetic in the previous two lessons. What comes after arithmetic? Algebra. It's time to delve into a little bit of modular algebra.

The first thing one attacks in algebra is solving linear equations. If I told you that 3 * x + 1 = 25, you could probably quickly tell me that x = 8. In addition, there is one and only one value for x which will work. A natural question after that is, could I have done the same thing if this had been 3 * x + 1 == 25  (mod n)?

Before you say "yes", think about what modular arithmetic we have done already. We have added and subtracted and multiplied and exponentiated. We skipped right over dividing, though. We need to divide by three if we're going to solve this equation. We can easily subtract one from both sides to get 3 * x == 24  (mod n).

But, how do we divide modulo n? In general, we don't. However, we can divide both sides by the same number if both sides are evenly divisible by the number and n is also evenly divisible by the number. When either b or n or both are not evenly divisible by a, then we have to find some c which we can multiply to both a and b so that the c * a becomes congruent to one modulo n. We'll get back to that in a bit.

First, a little theorem that will help us with these problems. The linear congruence a * x == b  (mod n) has d unique (as unique as one can be with modulo arithmetic, meaning unique equivalence classes from the modulo) solutions where d = gcd(a,n) if b is divisible by d and no solutions if b is not divisble by d. This means that the congruence will have one and only one solution if gcd(a,n) = 1.

Note: The parenthetical section of the last paragraph basically means that 5 and 26 are considered the same solution if the problem is modulo 3 since 5 == 26  (mod 3).

Let's do an example. Suppose we were trying to solve the congruence 10 * x == 15  (mod 25). Since gcd(10,25) = 5 and 5 divides into 15, we know that the equation is solvable and that there will be five different answers. The fact that all three are divisible by 5 also suggests that we can simplify the problem by getting rid of the threes for a bit.

If we divide everything by 5, we get 2 * x == 3  (mod 5). Now, we are left with a problem that has a unique solution since gcd(2,5) = 1. We can find that solution by plugging in numbers until we find one that works. In this case, it's easy enough to see that x = 4 works. Another way to go about it is to multiply both sides by 3. If we do that, we get 6 * x == 9  (mod 5) which, when we reduce the coefficients modulo 5, becomes x == 4  (mod 5).

We'll get back to how we knew to mutliply by three in a moment. First, let's see what we've got so far. We know that x == 4  (mod 5). But, we really wanted to know what values of x work in the original equation which was (mod 25). Since we know that x == 4  (mod 5), then we know that x can be any number of the form 4 + 5 * t where t is an integer. The numbers modulo 25 which satisfy that are 4, 9, 14, 19, and 24. Those are our five answers to the problem 10 * x == 15  (mod 25).

So, here's where a little group theory comes into play. The numbers, modulo n, which are relatively prime to n form a group under the operation "multiplication modulo n". What does that all mean? For our purposes, the important bit is this. If a is some number that is relatively prime to n, then there exists some other number c which is also relatively prime to n such that a * c == c * a == 1  (mod n). In this case, that doesn't help us out too much since 5 is prime, all of the numbers 1, 2, 3, and 4 are relatively prime to five. However, if our modulus had been 40 instead of 5, we could have skipped over all of the even numbers and all of the multiples of 5 when looking for a number to "cancel" the two.

Here is a fun bit of group theory stuff with which you can play to familiarize yourself more with the above. Take any number---I'll use 10. List out all of the numbers between one and your number which are relatively prime to it. Mine are 1, 3, 7, and 9. Now, make a small matrix where the i-th row and j-th column is the product of your i-th number multiplied by your j-th number (all reduced by your modulus). Mine will be:

1379
3917
7193
9731

Group theory ensures that every entry in your matrix will be one of your numbers which was relatively prime to your modulus. Additionally, because a * b == b * a  (mod n), the matrix will be symmetric around the diagonal that goes from the northwest down to the southeast. Furthermore, it assures that every number in your matrix appears exactly once in each column and exactly once in each row. In particular, this means that 1 will appear in every row and every column. It's that last property that ensures that we can always find a c for any a such that c * a == 1  (mod n) when a is relatively prime to n.

The Chinese Remainder Theorem

I think that the story of the name of the Chinese Remainder Theorem is, by far, the best introduction that one can have to it. Imagine that you're a commander in the Chinese Army about two-thousand years ago. When you went out into battle, you had 208 soldiers with you. You're back from battle now, but there surely aren't still 208 soldiers there. How many do you have?

You could count them all. You could have them stand in a some sort of matrix and hope that you can find some reasonable w and h so that if your soldiers stand in w columns and h rows, there's only a few empty spots left over or only a few soldiers not able to fit into the formation.

Another approach that you could take would be to have them cluster in groups of three. Then, you could simply see how many people are not left in a group of three. Then, you could have them cluster in groups of five and do the same. Then, you could have them cluster in groups of seven and do the same.

To steal from Sun-Tzu, assume that you had 2, 3, and 2 people left over when you grouped them by 3's, 5's, and 7's, respectively. Then, the question becomes, what numbers satisfy all of these equations:

  • x == 2  (mod 3)
  • x == 3  (mod 5)
  • x == 2  (mod 7)

You may still be stuck. But, the Chinese Remainder Theorem makes the problem tractable, even easy.

The Chinese Remainder Theorem

Given n1, n2, ... nr which are positive integers that are pairwise relatively prime (that is to say that if i is not equal to j, gcd(ni,nj) = 1), then the system of congruences:

  • x == a1  (mod n1)
  • x == a2  (mod n2)
  • ...
  • x == ar  (mod nr)

Has a solution that is unique modulo n = n1 * n2 * ... * nr.

The proof of this actually finds the unique solution. First, we start by defining Nk to be n / nk for each k = 12, ... r. That is that Nk is all of the ni multiplied together except for nk. So, for our problem, these would be:

  • N1 = 5 * 7 = 35
  • N2 = 3 * 7 = 21
  • N3 = 3 * 5 = 15

Next, we have to find the solutions xk for each of the equations Nk * xk == 1  (mod nk). For our problem, this is:

  • 35 * x1 == 2 * x1 == 1  (mod 3)
  • 21 * x2 == 1 * x2 == 1  (mod 5)
  • 15 * x3 == 1 * x3 == 1  (mod 7)

From these, we have that x1 = 2 and x2 = 1 and x3 = 1. The simultaneous solution to our system then is this number s = a1 * N1 * x1 + a2 * N2 * x2 + ...+ ar * Nr * xr. In our case, this is s == 233 == 23  (mod 105). Note, that the 105 is from 105 = 3 * 5 * 7.

This tells us that we currently have either 23 or 128 soldiers remaining. There's a good chance we can tell the difference without making them partition off into elevens, too.

Problems

  1. Find the unique (up-to-modulo-equivalence) solutions to:
    1. 2 * x == 1  (mod 9)
    2. 5 * x == 3  (mod 7)
    3. 9 * x == 6  (mod 12)
    4. 9 * x == 4  (mod 12)
  2. I sent out 150 invitations to a singles mixer. I participated in all of the activities. We did a little mixer game where we paired off into groups of 5, but one group only had 4. Then, we had a sit down dinner with 9 to a table, but three tables ended up with 10. At the end of the evening, everyone left in pairs, except for me. How many people (including me) attended the event (assuming no uninvited guests showed up)?

Next Week

We're going to start talking about prime numbers and how to tell if a number is prime and how to find the factors of a number if it is not prime. This topic will probably go on for several weeks. I'm not sure how much of it we'll get through next week.