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 want to gauge how to group them when dispatching them to different size venues, you line them up in rows. When you do it 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 an ancient sky watcher, and have discovered that three heavenly bodies come to the region of the sky you care about with great regularity. 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 integers \(x\) 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?
In Section 5.2, 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 a course in 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 by simply checking all possibilities.
As one might expect, this is not the most promising solution strategy. If you dig into the code a bit you'll see that many cases aren't even treated properly, which could be very tedious to catch.
However, in considering systems of congruences, there is a famous theorem. This kind of simultaneous solution was apparently first considered by the Chinese mathematician Sun Tzu, about the same time as the late Greek mathematicians were coming up with what we now call Diophantine equations. A very full solution (see Subsection 5.5.1) was given by Qin Jiushao in the 13th century and rediscovered only in the 19th century in the West.
Consider a general system of \(k\) (linear) 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. In this case, we have an algorithm for solving the system.
The name comes from the provenance, and is often abbreviated CRT. 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. Similar questions of astronomical/astrological importance pepper the history of mathematics.
Finally, note that one 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 text, but you should be aware that everything done in linear algebra has very interesting modulo \(n\) counterparts, as part of the theme of number theory showing the unity of mathematics.
To do this justice, we need a very useful preliminary concept.
The inverse of a number \(a\) modulo \(n\) is the least nonnegative solution of the congruence \begin{equation*}ax\equiv 1\text{ (mod }n)\end{equation*}.
For example, the inverse of \(26\) modulo \(31\) is the least nonnegative solution of \begin{equation*}26x\equiv 1\text{ (mod }31\text{)}\, .\end{equation*} 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! Here are some questions to ponder regarding inverses.
What connection do \(a\) and \(n\) need if we expect there to exist an inverse of \(a\) modulo \(n\)?
How many inverses modulo \(n\) should \(a\) have, assuming it has one at all?
As a first step, try to find inverses to all the number you can modulo \(10\). Then do it again modulo \(11\).
The following Sage command computes the “inverse of 26 modulo 31”.
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 SageMath Cloud. (This is not supported when embedded in a web page as in your text.)
The point is that this is definitely something we can compute, using the methods of last time of solving solitary linear congruences.
