Here are three interesting problems which seem totally unrelated at first:
Can you find an answer to these by trial and error?
Once we've done that for a little, of course we can try to use Sage to find answers using today's recipe:
Click to the left again to hide and once more to show the dynamic interactive window 
It turns out that in general, if you have a system of $k$ congruences
where all the $n_i$ are mutually coprime, we have an algorithm for solving it!
This is a very important theorem called the Chinese Remainder Theorem, because it was the Chinese mathematician Master SunTzu whom we believe first talked of this kind of problem, about the same time as the late Greek mathematicians were coming up with what we now call Diophantine equations. Whether any actual Chinese rulers used it to decide how many troops they had by lining them up in threes, fours, fives, etc. is questionable, however!
In fact, it turns out that we can even give a set of criteria for when a general system $A_i x\equiv B_i$ mod ($N_i$) has a solution, as well as an algorithm for this  whether or not the $N_i$ are mutually coprime.
In fact, you can go much further and do linear algebra modulo $n$, and this is a lot of what modern cryptography is about, not to mention the modern hardcore computational number theory Sage was largely invented to help do. We can't do everything in this class, but I do want you to know that everything you do in linear algebra has very interesting modulo $n$ counterparts, as part of the theme of number theory showing the unity of mathematics.
I need a preliminary concept to do this justice  the inverse of a number modulo $n$.
6 6 
This Sage command computes the "inverse of 26 modulo 31". This simply means it finds the least nonnegative solution of $$26x\equiv 1\text{ mod (31)}\, .$$ This is called the inverse because you can think of the solution as $26^{1}$, or $\frac{1}{26}$, in the number system $\mathbb{Z}_{31}$. Do you see why that is an appropriate interpretation?
Miniexercise: What connection do $a$ and $n$ need if we expect there to be an inverse of $a$ modulo $n$? How many inverses modulo $n$ does $a$ have?
The point is that this is definitely something we can compute, using the methods of last time of solving solitary linear congruences. It is a key piece in the proof of the Chinese Remainder Theorem! We will present a completely constructive proof  that is, we will not just prove it can be done, we will show how to get a solution to a given system of linear congruences.
Remember that we are trying to solve the system of equations $x\equiv a_i$ mod ($n_i$). Here are the steps we'll take.
Let's look at how to solve our original system using this method. First, I'll make sure I know all my initial constants.
(5, 6, 7) (1, 2, 3) 210 (5, 6, 7) (1, 2, 3) 210 
Next, I'll write down all the $c_i$, the complements to the moduli, so to speak. Remember, $c_i=N/n_i$.
(42, 35, 30) (42, 35, 30) 
Now we need to solve for the inverse of each $c_i$ modulo $n_i$. One could do this by hand. For instance, $$42d_1\equiv 2d_1\equiv 1\text{ mod }(5)\text{ yielding }d_1=3,\text{ since }2\cdot 3=6\equiv 1\text{ mod }(5)\; .$$ But that is best done on homework for careful practice; in class, we might as well use the power of Sage.
(3, 5, 4) (3, 5, 4) 
Now I'll create each of the big product numbers, as well as their sum.
(126, 350, 360) 836 (126, 350, 360) 836 
Of course, we don't recognize 836 as our answer. But:
206 206 
Let's look at Example 3.14 for another run at this.
Now, there are many, many useful things we can do with the CRT. First, a theoretical  but highly important one:
Next, we will look at a couple practical things the book does as well.
We have some more fun I want to mention, as well as an interesting result. But the CRT is the main event for today.
Let's go back to the interact from before. What happens if I let the $n_i$ NOT be relatively prime?
Click to the left again to hide and once more to show the dynamic interactive window 
It turns out that you can get CRT answers as long as $gcd(n_i,n_j)$ always divides $a_ia_j$. This allows one to separate out prime powers, and solve the congruences $$x\equiv a_j\text{ mod }(p^e)$$ where $p^e$ divides $n_j$. We will not do this, for time's sake, but it's useful to know when you can use it with Sage.
Here's something else fun that might be surprising...
Click to the left again to hide and once more to show the dynamic interactive window 
Of course, I'm cheating a little:
1681 1681 
(False, 41^2) (False, 41^2) 
In fact, we can prove that quite the opposite of what you might have thought with this example is true:
(Note that this is not true if you have a multivariable polynomial! Yikes.)
The reason is that if $f(a)=p$ for some $a$, then for any $b\equiv a$ mod ($p$) we have $f(b)\equiv f(a)$ (by welldefinedness of addition and subtraction) as well, so $$f(b)\equiv f(a)\equiv p\equiv 0\text{ mod }(p)\text{, or that }p\mid f(b)\; .$$ But the problem is that if $f(b)$ is also prime for all such $b$, then we have a polynomial which returns to height $f(x)=p$ periodically, and hence $\lim_{x\to\infty}f(x)\neq \pm \infty$, which is only possible if $f$ is a constant polynomial.
What a surprise  limits and calculus can be used in number theory! Even at this early stage, this is true; more will be later. A few more polynomials like this are below: this link has lots and lots more information.


Finally, I want to explain an exploration for our next session.
One of the most important things we can now do is study congruences with prime (power) modulus, because we can combine their solutions to get solutions for any congruences. So we will want to understand the structure of things modulo $p^e$, and especially modulo $p$. This Sagelet allows exploration of powers $a^n$ modulo $p$ for various primes $p$ and bases $a$.
Click to the left again to hide and once more to show the dynamic interactive window 
Homework to try for Friday:
