Notes on modular arithmetic and the Chinese Remainder Theorem
Teuvo Laurinolli
Galois club / Oulun Lyseo
May 2012
In these notes all numbers,denoted by different letters, are elements of , that is, integers .
1. Congruences and congruence arithmetic
DEFINITION 1
For integers we define the congruenceof under division by
to hold true if and only if
is divisible by or in symbols |,
or equivalently
,
or still
dividing by leaves as the remainder.
* * * * *
In the congruence arithmetic (mod ) the integers and satisfying the congruence relation (mod ) are considered equal. Such an arithmetic can also be called circular or clock arithmetic(mod ) in which the number line is wound around a circle (clock face) with the perimeter . Along such a circle the points of the usual number line coincide, as also do the points . Generally for any with , the infinitely many points coincide on this number circle (mod ).
EXAMPLE 1
In the congruence arithmetic (mod 12) it makes perfectly sense to write equations like or or which are all true. The first equation could also be written in equivalent forms or (mod 12) etc. but is the simplest form of the same fact.
As in the above example, it is customary to write simply (mod ) instead of more official (mod ). The use of equality sign = emphasizes the fact that on the number circle (mod ) congruent numbers are represented by the same point.
LEMMA 1 [Basic properties of congruences (mod )]
For all integers appearing below we have
(i) (reflexivity)
(ii)If then (symmetry)
(iii)If and then (transitivity)
(iv)Every is congruent with one and only one i.e.. the remainder of when divided by .
(v)If and then and
(vi)If and then
(vii)If then , and
(viii)If then
(ix)If for then where denotes any polynomial expression of variables with all coefficients in . [Such involves only additions, subtractions and multiplications, but no divisions.]
Proof: Cases (i)-(vi) follow directly from the definition of congruence. Case (vii) follows from (v) and (vi). Case (viii) follows from (vi) because power is a repeated multiplication. Case (ix) generalizes the statements (v)-(viii) and follows from them by induction.
QED
From the previous lemma we see that congruences behave very much like equations. Valid congruences can be added, subtracted, multiplied or raised to powers and the resulting congruences are valid. Also if numbers occurring in a polynomial expression (with integer coefficients) are replaced be congruent numbers then the value of the expression remains congruent with the original value.
WARNING: In general, you cannot divide congruences. For example, dividing the (mod 6) valid congruenceby 3 we get an invalid congruence . However, you are allowed to divide a congruence (mod ) by an integer provided that and are relatively prime i.e. have no common divisors besides 1, or in symbols gcd() = 1.
2. Greatest common divisor and the Euclidean algorithm
The greatest common divisor gcd() of two integers is defined, as the name tells, to be the greatest of their common divisors. We have, for example,
,
,
.
If we say that are relatively prime.
A simple method to find for given integers is to write both of them as products of their prime factors and pick the common prime factors (mind the multiplicity) to produce the gcd. For example, we have
and .
Hence
.
If the numbers are very large, this factorization method can be tedious. Fortunately, there is another systematic method, the Euclidean algorithm, which was discovered already in ancient times some 23 centuries ago.
EUCLIDEAN ALGORITHM(for finding the greatest common divisor of )
Let Starting from these numbers we construct a strictly decreasing sequence of integers until we reach zero
where and the subsequent numbers (are obtained recursively by divisionsof two preceding numbers and by setting the remainder =. The last non-zero element in this sequence, that is , is the required greatest common divisor.
The algorithm proceeds as follows:
(i)Set
(ii)Divide by and call the quotient and remainder . We havethe equation .
(iii)Clearly because in division the remainder must be smaller than divisor.
(iv)Then we divide to get
.
(v)Again .
We continue in this way until the remainder comes down to zero. Then the last two division equations can be written as
(because )
LEMMA 2 (The Euclidean algorithm produces the gcd of the initial numbers )
Let. Then , where is the last non-zero remainder in the above algorithm.
Proof: Since is a divisor in it must be a divisor in because by (ii) we have . For the same reason by (iv) must be a divisor in and so on. We see that must be a divisor in all remainders and hence also in the last non-zero remainder . Hence .
On the other hand it follows from the last equation that is a divisor in and consequently (by earlier equations) in all preceding numbers of the sequence. Hence is a common divisor in and consequently because is the greatest common divisor of . We conclude that = the last non-zero remainder of the Euclidean algorithm.
QED.
EXAMPLE 2
Let us use Euclidean algorithm to find . We set . We generate the sequence 0f remainders by successive divisions
(hence )
(hence )
(hence )
(hence )
By Lemma 2 then .
LEMMA 3 (The greatest common divisor expressed as a linear combination)
Let and let .
Then we can find integers such that .
Proof: We show that all remainders produced by the Euclidean algorithm starting from the numbers can be expressed as a required linear combination.
From the first division equation of the algorithm we get
and hence where
Similarly from the second division equation we get
and hence where
It is clear that we can continue in the same way and successively express all remainders in the form where are integers (because all quotients are integers). But this proves the lemma since is one of the remainders (the last non-zero remainder).
QED
NOTE: A more formal version of the above proof uses mathematical induction.
3. Finding multiplicative inverses in modular arithmetic
[Modular arithmetic = congruence arithmetic]
Consider modular arithmetic (mod ) i.e. arithmetic where we do additions and multiplications in the finite set of numbers placed evenly along the circular clock face.
It is clear that every has an additive inverse which satisfies . For a given we simply choose .
Analogously we define to be a multiplicative inverse of if (mod ). This is often indicated symbolically by (mod ).
EXAMPLE 3
Consider the set of integers (mod 6). Of its five elements only 1 and 5 have multiplicative inverses which are 1 and 5 themselves because and (mod 6). Hence and (mod 6). The elements 0, 2, 3 and 4 do not have inverses.
On the other hand, in the set all non-zero elements have inverses which are the following:
In any the element 0 cannot have an inverse since for all we have (mod ).
LEMMA 4 (Existence of multiplicative inverse)
The element has a multiplicative inverse (mod ) if and only if .
Proof: ( Assume . Then by Lemma 3 there are integers such that . Hence . Then clearly (mod ).
If , that is , then and we are done. Otherwise there is a non-zero element such that (mod ). By Lemma 1 the congruence remains true if is replaced by and then we conclude that .
() Assume has a multiplicative inverse . Then (mod ). Hence and . We see that any common factor of must be a factor of 1 which however has only one factor namely 1 itself. Therefore the only common factor of is 1 and hence .
QED.
REMARK 1
The first part of the previous proof provides also a method (based on the Euclidean algorithm) for finding the inverse of if it exists. Sometimes however there are shorter ad hoc methods for finding the inverse.
EXAMPLE 4
To find the inverse of 69 (mod 173) we apply the Euclidean algorithm with and as follows
We conclude that (mod 173) exists since . Now we roll back the above division equations to get
and then we have, since (mod 173), that
(mod 173),
from which
(mod 173)
To verify the answer we calculate
(mod 173).
4. Chinese Remainder Theorem
This result was first discovered in ancient times (ca. 200-300 AD) by the Chinese scholar Sun Tzu and it was used to solve problems like the following.
PROBLEM
An old lady came to town market place to sell her eggs which she had in her bag. Accidentally, a horse of a bypassing rider tramped on the bag and smashed all eggs. The rider offered to compensate the damage and asked how many eggs there had been in the bag. The lady replied with a conundrum: ”I had not counted the eggs but when I picked them out in threes (triples) one remained, when I picked them out in fives three remained and when I picked them out in sevens five remained. Altogether the number was certainly less than ten dozens.” How many eggs did she have in her bag?
In mathematical terms the problem amounts to finding the number such that the following system of three congruences (equations of modular arithmetic) is true:
(mod 3)
(mod 5)
(mod 7)
A general method for solving such systems is formulated in the following theorem.
CHINESE REMAINDER THEOREM (CRT)
Letbe positive integers, all greater than 1 and pairwise relatively prime, and let be any positive integers. Then the system of congruences
(mod )
(mod )
- - -
(mod )
has a solution which is unique (mod ) where .
Proof: Define numbers by setting . So is equal to the product from which the factor has been removed. Clearly then and are relatively prime and therefore. By Lemma 4 each has a multiplicative inverse (mod ) and we have (mod ).
We will show that the number
[*]
is a solution to the system of congruences .
Choose an arbitrary congruence (mod ) of our system. The number defined by [*] satisfies this congruence since clearly
(mod )[because for all we have (mod ) ]
But (mod ) and so
(mod ).
Hence we conclude that is a solution of the system of congruences.
Let us proceed to prove the second part of the theorem, that is unique (mod ).
Assume that is another solution. Then by the basic properties of the congruences stated in Lemma 1 we see that for each , (mod ). Therefore the difference is divisible by each and hence also by their product . But then (mod ) which proves the uniqueness (mod ).
QED
EXAMPLE 5
Let us apply the CRT to solve the egg problem. We have and . Then and , and .
To find the inverses we could use the Euclidean algorithm as in Example 4 but let us now apply more direct calculations.
We must have (mod 3) but because (mod 3)this condition reduces to (mod 3) and with a little guesswork we get .
Similarly the condition (mod 5) reduces to since (mod 5).
Finally the condition (mod 7) reduces to since again (mod 7).
Now [*] in the proof of CRT gives the required solution
To satisfy the upper bound (ten dozens) we will find a smaller solution using the uniqueness property that all solutions are congruent (mod ). So we get
(mod 105)
which gives the final answer 103 eggs.
EXAMPLE 6
Some sources (to be found by entering CRT in the Google search window) it is indicatedthat CRT can be used to improve computational efficiency in arithmetic operations with very large integers. Let us illustrate this technique by calculating the product of and .
We set up a ’CRT machine’ by choosing as the modulo divisors , all prime numbers (and hence relatively prime), whence . [We have to choose so many divisors that will be smaller than which, of course, is always possible.] We will now replace by smaller numbers congruent with them. We have
(mod 29) (mod 29)
(mod 59) (mod 59)
(mod 71) (mod 71)
Let now . By the congruence rules (Lemma 1) we have
(mod 29)
(mod 59)
(mod 71)
Now the required product is the solution () of this system. This solution can be constructed by the CRT as provided by the expression [*] in its proof.
We have now , and .
To find their respective inverses ’s we have the conditions
(mod 29) from which ,
(mod 59) from which ,
(mod 71) from which .
Finally we get
To produce an answer we take the remainder of the above one (mod ) and we get
(mod ).
For verification calculate directly .
THE AUTHOR’S FINAL REMARK
I find it hard to see how the procedure in the above example improves computational efficiency as it seems that the intermediate computations are much more time (and space) consuming than direct multiplication of x and y.
In many websources it is indicated that CRT is routinely applied in cryptography (encoding anddecoding information) and particularly public key cryptography like RSA.
1