Section 5.3 Systems of Linear Congruences
Here are three interesting problems which may seem totally unrelated at first.
Question 5.3.1.
Can you find an answer to any or all of these by trial and error?
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. You choose to group them by fives (with one left over), by sixes (two left over), and by sevens (with three left over). How many helpers are there total?
You’re an ancient sky watcher, and you 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\))
Subsection 5.3.1 Introducing the Chinese Remainder Theorem
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.
Theorem 5.3.2. Chinese Remainder Theorem.
Consider a general system of \(k\) (linear) congruences:
\(x\equiv a_1\) (mod \(n_1\))
\(x\equiv a_2\) (mod \(n_2\))
\(\displaystyle \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.
Proof.
Finally, note that one can also go much further and do linear algebra modulo \(n\text{,}\) and this is a lot of what modern cryptography is about, not to mention the modern hard-core computational number theory for which Sage was largely invented. 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, demonstrating again this book’s theme of number theory showing the unity of mathematics.
Subsection 5.3.2 The inverse of a number
To do justice to the proof of
Theorem 5.3.2, we need a very useful preliminary concept.
Definition 5.3.4. The Inverse of a Number.
The inverse of a number \(a\) modulo \(n\) is the least nonnegative solution of the congruence
\begin{equation*}
ax\equiv 1\text{ (mod }n)\text{.}
\end{equation*}
It is sometimes notated \(a^{-1}\text{.}\)
Example 5.3.5.
For example, the inverse of \(26\) modulo \(31\) is the least nonnegative solution of
\begin{equation*}
26x\equiv 1\text{ (mod }31\text{)}\text{.}
\end{equation*}
This is called the inverse because you can think of the solution as being equivalent to the idea of \(\frac{1}{26}\text{,}\) or \(26^{-1}\text{,}\) in the numbers modulo \(n=31\text{.}\)
Note that there is not always an inverse!
Question 5.3.6.
Ponder these questions regarding inverses.
What connection do \(a\) and \(n\) need if we expect there to exist an inverse of \(a\) modulo \(n\text{?}\)
How many inverses modulo \(n\) should \(a\) have, assuming it has one at all?
Example 5.3.7.
As a first step, try to find inverses to all the numbers you can modulo \(10\text{.}\) Then do it again modulo \(11\text{.}\)
The following Sage command computes the “inverse of 26 modulo 31”.
Sage note 5.3.8. Getting interactive Sage help.
You can look for more information on Sage commands by using question marks. Try inverse_mod?
and inverse_mod??
in a notebook, command line interface, or CoCalc. (This also should work as embedded in the web page in your text; let us know if it doesn’t.)
The point is that the inverse is definitely something we can compute, just by solving a linear congruence.
www-groups.dcs.st-and.ac.uk/~history/Biographies/Sun_Zi.html
www-history.mcs.st-andrews.ac.uk/Biographies/Qin_Jiushao.html