NTIC Systems of Linear Congruences

🔗

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. When you do it 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 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.

xxxxxxxxxx
 
@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']])
def _(a_1=(r'\(a_1\)',1), a_2=(r'\(a_2\)',2), a_3=(r'\(a_3\)',3), n_1=(r'\(n_1\)',5), n_2=(r'\(n_2\)',6), n_3=(r'\(n_3\)',7)):
    try:
        answer = []
        for i in [1..n_1*n_2*n_3]:
            if (i%n_1 == a_1) and (i%n_2 == a_2) and (i%n_3 == a_3):
              answer.append(i)
        string1 = r"<ul><li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_1,n_1)
        string2 = r"<li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_2,n_2)
        string3 = r"<li>$x\equiv %s \text{ (mod }%s)$</li></ul>"%(a_3,n_3)
        pretty_print(html("The simultaneous solutions to "))
        pretty_print(html(string1+string2+string3))
        if len(answer)==0:
            pretty_print(html("are none"))
        else:
            pretty_print(html("all have the form "))
            for ans in answer:
                pretty_print(html("$%s$ modulo $%s$"%(ans,n_1*n_2*n_3)))
    except ValueError as e:
        pretty_print(html("Make sure the moduli are appropriate for solving!"))
        pretty_print(html("Sage gives the error message:"))
        pretty_print(html(e))

🔗

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 or Sun Zi, probably 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.

🔗

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

This will be done in a completely constructive fashion in Subsection 5.4.1.

🔗

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\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.3. 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.4.

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

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

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

xxxxxxxxxx
 
inverse_mod(26,31)

🔗

Sage note 5.3.7. Getting interactive Sage help.

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 or Jupyter notebook, command line interface, or CoCalc. (This is not supported when embedded in a web page as in your text.)

🔗

The point is that the inverse is definitely something we can compute, just by solving a linear congruence.