Systems of Linear Congruences




Integers

In the following sections, we only work with integers and all names of constants and variables, such as a, b, x, m, n, ... , are names of integers.

In the following sections we assume that m is a strictly positive integer in an expression like 'modulo m' or 'mod m'

Objective

This page offers a general method to solve systems
 
   / x = a mod m
   \ x = b mod n

     with gcd(m,n) = 1

Property of the greatest common divisor of two integers

The greatest common divisor of m and n is written as gcd(m,n).

Property:
The greatest common divisor d of m and n, can be written as a linear combination of m and n. So, there are always integers r and s such that d = r.m + s.n

Example:
gcd(12,40) = 4
4 can be written as a linear combination of 12 and 40.
-3.(12) + 1.(40) = 4

Relatively prime numbers

Two integers m and n are said to be relatively prime if and only if gcd(m,n) = 1. Then, there are always integers r and s such that r.(m) +s.(n) = 1.

Example
gcd(3,5) = 1 => 1 can be written as a linear combination of 3 and 5 ; 2.3 + (-1).5 = 1.

The set ( a modulo m )

Definition:

(a modulo m) is the set of all integers of the form (a + (a multiple of m))

Notation : a mod m

Examples :

 
      43 belongs to the set  3 mod 4 because  43 is (3 + (a multiple of 4))

      a mod 4 = b mod 4  <=> (b-a) is a multiple of 4

      3 mod 4 = 15 mod 4  because  15 -3 is a multiple of 4

Important convention about notation

 
   If an integer b belongs to the set   a mod m, then we write

        b = a mod m

   This is equivalent with

        b = a + (a multiple of m)

The equation x = 3 mod 4

 
Consider the equation x = 3 mod 4  with x as the unknown.

   x = 3 mod 4 means  x = 3 + (a multiple of 4)
So, this equation has infinitely many solutions for x.

Systems of two equations

Example
 
  /  x = 2 mod 6
  \  x = 5 mod 7

We look for all the numbers x such that
 
  x  is (2 + (a multiple of 6)) AND  x is (5 + (a multiple of 7))

  So, the intersection of the sets  2 mod 6 and  5 mod 7 is required
The set of solutions is not obvious.

In the following sections we will show how such a system can be solved.

We include here not only the final solving procedure but we also show the line of thought leading to this method.

The homogeneous system

Say m and n are two relatively prime integers.
We consider the system
 
 x = 0 mod m
 x = 0 mod n       (1)
The first equation means: x = 0 + (a multiple of m) or shorter x = a multiple of m

The second equation means: x = 0 + (a multiple of n) or shorter x = a multiple of n

The set of solutions is the set of all common multiples of m and n. But, since m and n are relatively prime, the common multiples of m and n are the multiples of (m.n) . So set of solutions of the system (1) is ( 0 mod m.n )

The non-homogeneous system

Say m and n are two relatively prime integers. We investigate the system
 
 x = a mod m
 x = b mod n        (2)

Lemma

Let x' be one known solution of the system (2).
Then, the set V = x' mod m.n is the set of solutions of the system (2).

Proof:

  1. We'll show that each element of V is a solution of (2).

    An element x" of the set V can be written as x' + k.m.n

     
    We know that   x' = a mod m
    
       =>          x' + (k.n).m = a mod m
    
       =>          x" = a mod m         (3)
    
    ----------------------------------------
    We know that      x' = b mod n
    
       =>             x' + (k.m).n = b mod n
    
       =>             x" = b mod n     (4)
    
    ----------------------------------------
    
    From (3) and (4) we see that x" is a solution of system (2)
    
  2. We'll show that a random solution of (2) is an element of the set V.

    Say x" is a random solution of (2). Then

     
         x' is (a + (a multiple of m))  and  x" is (a +(a multiple of m))
    
    =>   (x"-x') is (a multiple of m)
    
    =>   x" - x' = 0 mod m            (5)
    
    and also
    
         x' is (b + (a multiple of n))  and  x" is (b +(a multiple of n))
    
    =>   (x"-x') is (a multiple of n)
    
    =>   x" - x' = 0 mod n            (6)
    
    
    From (5) and (6) we have
    
         x" - x' is a solution of the  homogeneous system (1)
    
    But, the set of solutions of that system  (1) is  ( 0 mod m.n )
    
    So, we have
    
        x" - x' = 0 mod m.n
    <=>
        x" - x' is a multiple of (m.n)
    <=>
        x" = x' + (a multiple of (m.n))
    <=>
        x" = x' mod m.n
    <=>
        x" is an element of V
    
    

The Chinese Remainder Theorem

Given :
  • Relative prime integers m and n.
    Since gcd(m,n) = 1, there are integers r and s such that r.m +s.n = 1.
  • The system
     
      / x = a mod m
      \ x = b mod n         (2)
    
    
    
Then, the set of all solutions of the system is (a.s.n + b.r.m) mod m.n

Proof :

We know that r.m + s.n = 1 and from this it follows that r.m + s.n - 1 = 0

 
    0 is  (a multiple of m)

=>  r.m+s.n -1 is (a multiple of m)

=>  s.n -1 is (a multiple of m)

=>  s.n = 1 mod m

and

    0 is  (a multiple of n)

=>  r.m+s.n -1 is (a multiple of n)

=>  r.m -1 is (a multiple of n)

=>  r.m  = 1 mod n

Then it follows

   s.n = 1 mod m   =>  a.s.n = a mod m
and
   r.m = 1 mod n   =>  b.r.m = b mod n


but then is

   a.s.n + b.r.m  = a mod m
   a.s.n + b.r.m  = b mod n
Relying on the lemma it follows that
 
a.s.n + b.r.m  mod m.n  is the set of solutions of (2)

Example

 
 x = 2 mod 6
 x = 5 mod 7
So, m = 6 and n = 7 ; a = 2 and b = 5.
(-1).6 + 1.7 = 1 ; So, r = -1 and s = 1.

Then x = 16 mod 42 is the set of solutions.

Application

Find the common roots of the functions sin( pi.(x-5)/3 ) and cos( pi(x-7)/16 )

Systems with more than two equations

The method from above can gradually be expanded.
A system of n equations can be reduced to (n-1) equations.

We show the method of reducing by means of an example.

 
 x = 2 mod 6
 x = 5 mod 7
 x = 3 mod 5
First solve the system of the first two equations. We find x = -16 mod 42.
To find solutions of the given system, we now have to solve:
 
 x = -16 mod 42
 x = 3 mod 5
We find x= 68 mod 210.

Notice: This is only correct because 6, 7 and 5 are relatively prime in pairs.


Topics and Problems

MATH-abundance home page - tutorial

MATH-tutorial Index

The tutorial address is http://home.scarlet.be/math/

Copying Conditions

Send all suggestions, remarks and reports on errors to Johan.Claeys@ping.be     The subject of the mail must contain the flemish word 'wiskunde' because other mails are filtered to Trash