Systems of Linear Congruences

• Integers
  
• Objective
  
• Property of the greatest common divisor of two integers
  
• Relatively prime numbers
  
• The set ( a modulo m )
  
• Important convention about notation
  
• The equation x = 3 mod 4
  
• Systems of two equations
  
  • The homogeneous system
    
  • The non-homogeneous system
    
    • Lemma
      
    • The Chinese Remainder Theorem
      
  • Example
    
  • Application
    
• Systems with more than two equations
  

Integers

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

Objective

 
   / x = a mod m
   \ x = b mod n

     with gcd(m,n) = 1

Property of the greatest common divisor of two integers

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

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 )

(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)

Systems of two equations

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

 
  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

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

 
 x = 0 mod m
 x = 0 mod n       (1)

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

 
 x = a mod m
 x = b mod n        (2)

Lemma

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

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

 
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

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

Application

•  
     sin( pi.(x-5)/3 ) = 0
  <=>
      pi.(x-5)/3 = k.pi
  <=>
       x = 5 + 3 k
  <=>
       x = 5 mod 3
  <=>
       x = 2 mod 3
  

•  
     cos( pi.(x-7)/16 ) = 0
  <=>
      pi.(x-7)/16 = pi/2 + k pi
  <=>
       x - 7 = 8 + 16 k
  <=>
       x = 15 + 16 k
  <=>
       x = 15 mod 16
  

• The common roots are the solutions of the system

   
     / x =  2 mod 3
     \ x = 15 mod 16
  

  3 and 16 are relatively prime.
  There is an r and an s such that r.3 + s.16 = 1. Take r = -5 and s = 1.

  Relying on the Chinese remainder theorem, the solution is

   
      x = 15.(-5).3 + 2.1.16   mod 48
  
      x = -193 mod 48
  
      x = 47 mod 48
  

Systems with more than two equations

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

 
 x = 2 mod 6
 x = 5 mod 7
 x = 3 mod 5

 
 x = -16 mod 42
 x = 3 mod 5

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