## 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 * vwhereuandvare integers. It shows that the set is non-empty (one way to do this is to letu = aandv = b). Then, it takes the smallest member of that set, sayd = a * x + b * y. Next, the proof uses the Division Algorithm to obtain integersqandrsuch thata = q * d + rwhereris greater than or equal to zero and less thand. It goes on to show that the last expression there foracan be solved forrand thedcan be replaced witha * x + b * y. The result is thatr = a * (1 - q * x) + b * (-q * y). This shows thatrhas to be zero. Ifrwere greater than zero and less thandthendwas not the smallest element of the set. We can do the same forb.That all shows that

ddivides bothaandb. Ifcis some arbitrary divisor ofaandb, then it also a divisor ofa * x + b * y = d. Thus,cis less than or equal tod. 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 divisible 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 **1 * 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:

1 | 3 | 7 | 9 |

3 | 9 | 1 | 7 |

7 | 1 | 9 | 3 |

9 | 7 | 3 | 1 |

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

**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 _{k}** to be

**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 **x _{k}** for each
of the equations

**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 _{1} = 2** and

**x**and

_{2}= 1**x**. The simultaneous solution to our system then is this number

_{3}= 1**s = 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 **23** or **128**
soldiers remaining. There's a good chance we can tell the difference
without making them partition off into elevens, too.

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