# MAT 338 Day 8 2011

## 3342 days ago by kcrisman

Here are three interesting problems which seem totally unrelated at first:

• You have lots of volunteers at a huge campaign rally.  Because you are very efficient at moving them, you line them up by fives (one left over), by sixes (two left over), and by sevens (with three left over).  How many are there?
• You're a comet watcher, and the comets are coming.  Three of them come to the region of the sky you care about with alarming frequency.  Comet 1 comes every five years, starting next year.  Comet 2 comes every six years, starting two years from now.  Comet 3 comes every seven years, starting three years from now.  When will they all line up?
• You like math a lot.  You want to know what numbers simultaneously solve the following three linear congruences:
• $x\equiv 1$ mod (5)
• $x\equiv 2$ mod (6)
• $x\equiv 3$ mod (7)

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:

@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']]) def _(a_1=('$a_1$',1),a_2=('$a_2$',2),a_3=('$a_3$',3),n_1=('$n_1$',5),n_2=('$n_2$',6),n_3=('$n_3$',7)): try: answer = CRT_list([a_1,a_2,a_3],[n_1,n_2,n_3]) html("The simultaneous solutions to ") html("<ul><li>$x\equiv %s \\text{ mod }(%s)$</li>"%(a_1,n_1)) html("<li>$x\equiv %s \\text{ mod }(%s)$</li>"%(a_2,n_2)) html("<li>$x\equiv %s \\text{ mod }(%s)$</li></ul>"%(a_3,n_3)) html("all have the form $%s$ modulo $%s$"%(answer,n_1*n_2*n_3)) except ValueError, e: html("Make sure the moduli are appropriate for using the CRT!") html("Sage gives the error message:") html(e)

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

• $x\equiv a_1$ mod ($n_1$)
• $x\equiv a_2$ mod ($n_2$)
• $\ldots$
• $x\equiv a_k$ mod ($n_k$)

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 Sun-Tzu 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!

### Interlude:

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 hard-core 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.

### Back to the CRT:

I need a preliminary concept to do this justice - the inverse of a number modulo $n$.

inverse_mod(26,31)
 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?

Mini-exercise: 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.

1. Let's call the product of the moduli $n_1 n_2 \cdots n_k=N$.
2. Let each $N/n_i$ be called $c_i$.  It's sort of a 'complement' to the $i$th modulus within the big product $N$.
3. Now find the inverse of each $c_i$ modulo $n_i$ - that is, find $d_i$ such that $c_i d_i\equiv 1$ mod ($n_i$) for all $i$.
• Notice that this is possible.  You can't find an inverse modulo any old thing!  But in this case, $c_i$ was constructed to be a product of a bunch of numbers, all of which are coprime to $n_i$.  So we are okay.
4. For each $i$, multiply the three numbers $a_i \cdot c_i \cdot d_i$.
5. Here is a harder step - evaluating each of those products modulo the various $n_j$.
• By definition, each $c_j$ is divisible by $n_i$ (except for $c_i$ itself), so modulo $n_i$ the product is $$a_j c_j d_j \equiv 0\text{ mod }(n_i)\; .$$
• The product $$a_i c_i d_i \equiv a_i \cdot 1\equiv a_i\text{ mod }(n_i)\; ,$$ of course.
6. Now add all these numbers together to get $$x=a_1 c_1 d_1+a_2 c_2 d_2+\cdots +a_k c_k d_k\; .$$ For each $n_i$, the previous step shows this sum is $$x\equiv 0+0+\cdots +a_i +\cdots +0\text{ mod }(n_i)\; .$$
7. Any other solution $x'$ has to still fulfill $x'\equiv a_i\equiv x$ mod ($n_i$), so $n_i\mid x'-x$ for all moduli $n_i$. Since all $n_i$ are relatively prime to each other, $N\mid x'-x$ too (if $a|c$ and $b|c$ and $gcd(a,b)=1$, then $ab|c$).  So $x'\equiv x$ mod ($N$) - which means $x$ is the only solution modulo $N$!

Let's look at how to solve our original system using this method.  First, I'll make sure I know all my initial constants.

n_1, n_2, n_3 = 5,6,7 a_1, a_2, a_3 = 1,2,3 N = n_1*n_2*n_3 n_1, n_2, n_3; a_1, a_2, a_3; N
 (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$.

c_1,c_2,c_3 = N/n_1,N/n_2,N/n_3; c_1,c_2,c_3
 (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.

d_1=inverse_mod(42,5);d_2=inverse_mod(35,6);d_3=inverse_mod(30,7) d_1,d_2,d_3
 (3, 5, 4) (3, 5, 4)

Now I'll create each of the big product numbers, as well as their sum.

a_1*c_1*d_1,a_2*c_2*d_2,a_3*c_3*d_3;a_1*c_1*d_1+a_2*c_2*d_2+a_3*c_3*d_3
 (126, 350, 360) 836 (126, 350, 360) 836

Of course, we don't recognize 836 as our answer. But:

mod(836,N)
 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:

• Suppose that $X\equiv Y$ mod ($N$), and $N=\prod p_i^{e_i}$. Certainly if $N$ divides $X-Y$, so does a factor of $N$, so $X\equiv Y$ mod ($p_i^{e_i}$) for each prime power factor of $N$.  Thus, solutions to the "big" congruence are also solutions to the many little ones.
• But the CRT allows me to reverse this process. After all, all the powers of primes in a prime factorization are coprime to each other, so the simultaneous solution of the systems $X\equiv Y$ mod ($p_i^{e_i}$) will give me (one!) solution of $X\equiv Y$ mod ($N$), considered modulo $N$.
• That means that any question about congruences is really a question about congruences modulo prime powers. We will use this fact again and again in the remainder of the course, and it is a huge reason why the CRT is so intensely powerful.

Next, we will look at a couple practical things the book does as well.

• If you have several simultaneous congruences $A_ix\equiv B_i$ mod ($N_i$), then first write their individual solutions in the form $x\equiv a_i$ mod ($n_i$).  Then you can use the CRT to get a solution of that system, which is also a solution of the 'big' system.  Example 3.15 in the book is useful for this.
• If you have one complicated congruence $Ax\equiv B$ mod ($N$) with a composite modulus $N$, you can just take $N=p_1^{e_1}\cdots p_k^{e_k}$ and then solve all the congruences $Ax\equiv B$ mod ($p_i^{e_i}$) first.  Then use the CRT to 'patch' them together for a final solution. This is a little tedious, but certainly doable.  Example 3.16 in the book is good for this.
•  Don't forget in both cases to get back to the original modulus!

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?

@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']]) def _(a_1=('$a_1$',1),a_2=('$a_2$',2),a_3=('$a_3$',3),n_1=('$n_1$',4),n_2=('$n_2$',6),n_3=('$n_3$',7)): try: answer = CRT_list([a_1,a_2,a_3],[n_1,n_2,n_3]) html("The simultaneous solutions to ") html("<ul><li>$x\equiv %s \\text{ mod }(%s)$</li>"%(a_1,n_1)) html("<li>$x\equiv %s \\text{ mod }(%s)$</li>"%(a_2,n_2)) html("<li>$x\equiv %s \\text{ mod }(%s)$</li></ul>"%(a_3,n_3)) html("all have the form $%s$ modulo $%s$"%(answer,n_1*n_2*n_3)) except ValueError, e: html("Make sure the moduli are appropriate for using the CRT!") html("Sage gives the error message:") html(e)

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

f(x)=x^2+x+41 @interact def _(n=(0,[0..39])): html("Is $%s$ for $x=%s$, which is $%s$, a prime number?"%(f,n,f(n))) print is_prime(f(n))

## Click to the left again to hide and once more to show the dynamic interactive window

Of course, I'm cheating a little:

f(40)
 1681 1681
is_prime(f(40)),factor(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:

• There is no non-constant polynomial $f(x)$ with integer coefficients such that $f(x)$ is prime for all integers $x$.

(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 well-definedness 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.

g(x)=8*x^2-488*x+7243 for n in [0..30]: g(n),is_prime(g(n))
h(x)=x^6+1091 for n in [0..3906]: if is_prime(h(n)): print (n,h(n))

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

@interact(layout=[['p','a']]) def _(p=(7,prime_range(50)),a=(3,[0..50])): b=mod(a,p) top=ceil(2*p/10)*10 html("If we look at some of the powers of $%s$"%(a,)) html("modulo the prime $%s$, we get:"%(p,)) html("<ul>") for m in [0..top]: html("<li>$%s^{%s}\equiv %s\\text{ mod }(%s)"%(a,m,b^m,p)) html("</ul>") ## Click to the left again to hide and once more to show the dynamic interactive window Homework to try for Friday: 1. Do Exercises 3.8, 3.10, and 3.11. 2. Also do Exercise 3.16(a,b). 3. When eggs in a basket are removed two, three, four, five, or six at a time, there remain, respectively, one, two, three, four, or five eggs. When they are taken out seven at a time, none are left over. Find the smallest number of eggs that could have been contained in the basket. (Brahmagupta, 7th century AD) 4. Find a problem on the internet about pirates quarreling over treasure (or monkeys over bananas) that could be solved using the CRT, and solve it. Or do Exercise 3.18. But internet ones are more fun! 5. Solve the system$4x\equiv 2$mod (6),$3x\equiv 5$mod (7),$2x\equiv 4$mod (11). 6. Solve the congruence$5x\equiv 22$mod (84). 7. Find some conjecture to state about values of$a^n$mod ($p$), for$p$prime and$0\leq n < p$you discovered using the Sagelet. This could be anything profounder than $$a^0\equiv 1\text{ mod }(p)\text{ or }1^n\equiv 1\text{ mod }(p)$$ for all prime$p$and for all$n\$, but should at least be some pattern you tested for a number of values. We will start next time with this!