Introduction to Cryptography

Veikko Keränen, Jouko Teeriaho (RAMK, 2006)

ELEMENTARY NUMBER THEORY AND ALGORITHMS

3.  Congruences

3.1  Remainder and Congruence

Definition 3.1
Two integers  a  and  b  are congruent (or  a  is conguent to  b)  modulo  m,  if  m  divides the difference  a - b,  i.e.,  
a - b = q m,  for some   q  ∈  ℤ.   This situation is denoted by

				a ≡ b (mod m).

The integers  a  and  b  can be represented by using the division algorithm (Theorem 1.1) in the form (Subscript[ a =(Subscript[q, 1]) m+r, 1])  and  (Subscript[ b =(Subscript[q, 2]) m+r, 2]),  0 ≤  (Subscript[r, 1]), (Subscript[r, 2]) < m.  Here   a-(Subscript[r, 1])=(Subscript[q, 1]) m  and   b-(Subscript[r, 2]) =(Subscript[q, 2]) m,  and therefore, by Definition 3.1, the integer  a  is congruent to the remainder  (Subscript[r, 1])  and the integer  b  is congruent to the remainder  (Subscript[r, 2])  (modulo  m).  In other words, we have  

	a ≡ (Subscript[r, 1]) (mod m)   and   b ≡ (Subscript[r, 2]) (mod m),
	
where  (Subscript[r, 1])  and  (Subscript[r, 2])  are the remainders in question modulo  m.

Furthermore,  

(3.1)	a ≡ b (mod m)  if and only if the remainders  (Subscript[r, 1])  and  (Subscript[r, 2])  are equal.  

We can prove (3.1) by using the new notation as follows:

		a ≡ b (mod m) 
	 ⇔ 	a - b = q m   			(by definition)
	 ⇔ 	((Subscript[ (Subscript[q, 1]) m+r, 1]))  –  ((Subscript[ (Subscript[q, 2]) m+r, 2])) = q m
	 ⇔ 	(Subscript[r, 1]) – (Subscript[r, 2]) = (q – (Subscript[q, 1])+ (Subscript[q, 2])) m	(the multiplier  (q – (Subscript[q, 1])+ (Subscript[q, 2]))  is an integer)
	 ⇔ 	(Subscript[r, 1]) – (Subscript[r, 2]) = 0 			(since  0 ≤  (Subscript[r, 1,]) (Subscript[r, 2]) < m)
	 ⇔ 	(Subscript[r, 1]) = (Subscript[r, 2])
	
Consequently,  a ≡ b (mod m)  if and only if the integers  a  and  b  have the same remainder modulo  m.

Mathematica function  Mod[a, m]  gives the remainder  (Subscript[r, 1])  modulo  m   according to the division algorithm (Subscript[ a =(Subscript[q, 1]) m+r, 1]).

Example 3.1

a = 36;  m = 17;  Mod[a, m]

a = 17015;  m = 17;  Mod[a, m]

Indeed  36 = 2*17 + 2  and  17015 = 1000*17 + 15.

□

In the following example we test whether two quite large integers  a  and  b  are congruent modulo m ( = 17):

Example 3.2

m = 17; a = 3456789; b = 34567894; 

Mod[a - b, m] == 0

As a result we obtained that  a = 3456789  and  b = 34567894  are indeed congruent modulo  m = 17,  i.e.,  a ≡ b (mod m).  This is the case since the remainder is  = 0,  when  a  -  b  is divided by  m = 17  (see Definition 3.1).  Actuelly, one can easily compute that  a  -  b = -1830065*17.

Let us still check  that the remainders of   a  and  b  are equal, when  a  and  b  are divided by  m = 17:

Mod[a, 17]
Mod[b, 17]

Both remainders are thus  = 9.  Futhermore, we can chek that  a  =  203340*17 + 9  and  b = 2033405*17 + 9.

□

Generally, the remainders  (mod  m)  are  0, 1, 2, ...,  m - 1.  Thus, each integer is congruent to (mod m) exactly one integer in  {0, 1, 2, ...,  m - 1}.  Remember also that   a ≡ b (mod m)   if and only if the remainders of  a  and  b  are equal modulo  m  (we saw this in (3.1) above).