Section 5.3 Systems of Linear Congruences
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
simultaneously solve the following three linear congruences: (mod ) (mod ) (mod )
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
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))
Theorem 5.3.2. Chinese Remainder Theorem.
Consider a general system of
(mod ) (mod ) (mod )
where all the
Proof.
This will be done in a completely constructive fashion in Subsection 5.4.1 and Algorithm 5.4.1.
Historical remark 5.3.3. Ancient Chinese work on remainders.
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. Individual cases of such systems were considered by several generations of both Chinese and Indian mathematicians. A very full solution algorithm (see Subsection 5.5.1) was given by Qin Jiushao in the 13th century. See [E.5.10, Part V] for a very comprehensive discussion.
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 as well as theoretical interest. Similar questions of astronomical/astrological importance pepper the history of mathematics. See Exercise 5.6.22 and Exercise 5.6.23.
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
It is sometimes notated
Example 5.3.5.
For example, the inverse of
This is called the inverse because you can think of the solution as being equivalent to the idea of
Question 5.3.6.
Ponder these questions regarding inverses.
What connection do
and need if we expect there to exist an inverse of moduloHow many inverses modulo
should 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
xxxxxxxxxx
inverse_mod(26,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.)