## math_class: Number Theory 101 (Chinese Remainder Theorem)## Disclaimers and ApologiesI 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.
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 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 = 1492 * 1 + 284****1492 = 284 * 5 + 72****284 = 72 * 3 + 68****72 = 68 * 1 + 4****68 = 4 * 17 + 0**
So, **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 NumbersYou'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 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 CongruencesWe'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
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
But, how do we divide modulo First, a little theorem that will help us with these problems.
The linear congruence
Note: The parenthetical section of the last paragraph basically
means that Let's do an example. Suppose we were trying to solve
the congruence If we divide everything by 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
So, here's where a little group theory comes into play. The
numbers, modulo 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
Group theory ensures that every entry in your matrix will be one of
your numbers which was relatively prime to your modulus.
Additionally, because
## The Chinese Remainder TheoremI 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
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 **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 **n**,_{1}**n**, ..._{2}**n**which are positive integers that are pairwise relatively prime (that is to say that if_{r}**i**is not equal to**j**,**gcd(n**), then the system of congruences:_{i},n_{j}) = 1**x == a**_{1}(mod n_{1})**x == a**_{2}(mod n_{2})**...****x == a**_{r}(mod n_{r})
Has a solution that is unique modulo **n = n**._{1}* n_{2}* ... * n_{r}
The proof of this actually finds the unique solution. First, we
start by defining n / n for each
_{k}k = 1, 2, ... r. That
is that N is all of the _{k}n
multiplied together except for _{i}n. So, for
our problem, these would be:_{k}**N**_{1}= 5 * 7 = 35**N**_{2}= 3 * 7 = 21**N**_{3}= 3 * 5 = 15
Next, we have to find the solutions N.
For our problem, this is:_{k} * x_{k} == 1 (mod n_{k})**35 * x**_{1}== 2 * x_{1}== 1 (mod 3)**21 * x**_{2}== 1 * x_{2}== 1 (mod 5)**15 * x**_{3}== 1 * x_{3}== 1 (mod 7)
From these, we have that x and
_{2} = 1x. The simultaneous solution to our
system then is this number
_{3} = 1s = a.
In our case, this is
_{1} * N_{1} * x_{1} + a_{2} * N_{2} * x_{2} + ...+ a_{r} * N_{r} * x_{r}s == 233 == 23 (mod 105).
Note, that the 105 is from
105 = 3 * 5 * 7.This tells us that we currently have either ## Problems- Find the unique (up-to-modulo-equivalence) solutions to:
**2 * x == 1 (mod 9)****5 * x == 3 (mod 7)****9 * x == 6 (mod 12)****9 * x == 4 (mod 12)**
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 WeekWe'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. |