Section6.3Systems of Linear Congruences
Here are three interesting problems which may seem totally unrelated at first:
- You have lots of volunteers at a huge campaign rally. Because you are very efficient at moving them, and you are bored, you line them up by fives (with one left over), by sixes (two left over), and by sevens (with three left over). How many are there total?
- 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 come in the same year?
- 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?
Subsection6.3.1The Chinese Remainder Theorem
In the previous section, we were able to solve any one linear congruence completely. It's a good feeling.
But we know that this is a pretty restricted result. If you've had linear algebra, you've tried to solve big systems over the reals or complex numbers; sometimes in real-life operations research problems, there can be hundreds of thousands of linear equations to solve simultaneously!
It turns out this is true for modular arithmetic too, especially in encryption standards. Can we solve a system of linear congruences? Of course, one could ask a computer to do it.
But 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\))
This is a very important theorem called the Chinese Remainder Theorem, because it was the Chinese mathematician 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. A very full solution (see below) was given by Qin Jiushao in the 13th century and rediscovered only in the 19th century in the West.
Subsubsection6.3.1.1Interesting facts
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, many of the example problems in Qin's text mention divination, alignment of different calendars, and the like, so we can assume such problems were of practical interest as well as theoretical, even at that time.
One can even give a set of criteria for when a general system \[A_i x\equiv B_i\text{ mod (}N_i)\] has a solution, as well as an algorithm for this - whether or not the \(N_i\) are mutually coprime. This was Qin's major contribution.
You can also 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 you should be aware 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.
Subsection6.3.2The inverse of a number
To do this justice, we need a very useful preliminary concept - that of the inverse of a number modulo \(n\).
For example, the inverse of \(26\) modulo \(31\) is 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 numbers modulo \(n=31\).
Note that there is not always an inverse! Some questions related to this:
- What connection do \(a\) and \(n\) need if we expect there to be an inverse of \(a\) modulo \(n\)?
- How many inverses modulo \(n\) should \(a\) have?
- As a first step, try to find inverses to all the number you can modulo \(10\); do it again modulo \(11\).
Remark6.3.2
Sage note:
You can look for more information on Sage commands (in a normal Sage session) by using question marks; try inverse_mod? and inverse_mod?? in a Sage notebook, command line interface, or cloud. (This is not supported when embedded in a web page as here.)