Congruences ( Integers modulo m)

Prerequisites

In this section all letters stand for integers.
The greatest common divisor of n and m is noted as (n,m).
Let d = (n,m). All the linear combinations r.n + s.m of n and m are multiples of d.
If a is a divisor of b we write a | b.

Definition

Let m be a strictly positive integer. 

 
        a = b mod m
<=>
        m | (b - a)

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

Properties

The following properties are easy to prove from the definition. 

 
If      a = b mod m  and
        c = d mod m
Then
        a+c = b+d mod m
        a-c = b-d mod m
        a.c = b.d mod m
        an  = bn    mod m   (with n > 0)
        n.a = n.b mod m

Simplification law

 
If       e divides a, b and m
Then
        a = b mod m  <=>  a/e = b/e mod m/e

Cancellation law

 
If      (k,m) = 1
Then
        ak = bk mod m <=>   a = b mod m

Proof: 
 
        ak = bk mod m

<=>     m | (a-b)k
                        since (k,m) = 1
<=>     m | (a-b)

<=>     a = b mod m

The equation ax = b mod m

Solvability condition

 
        ax = b mod m  has a solution x
<=>     there is a k and an x such that ax - b = km
<=>     there is a k and an x such that ax - km = b
<=>     there is a linear combination of a and m that gives b.
<=>     b is a multiple of (a,m)
The last assertion holds because all linear combinations of a and m are exactly all the multiples of (a,m)

ax = b mod m has a solution

<=>

b is a multiple of (a,m)


Simplify the equation

To solve the equation ax = b mod m, first check if the solvability condition is satisfied.

Then d = (a,m) divides a, b and m. So, the equation can be simplified to 

 
        ax/d = b/d mod m/d

<=>     a'x = b' mod m'   with (a',m')=1
If (a',b') is k, then we can use the cancellation law, to simplify the last equation.

Example:
18x = 6 mod 8

(18,8)=2 is a divisor of 6. The solvability condition is satisfied.

Simplification law gives 9x = 3 mod 4 and the cancellation law gives

3x = 1 mod 4

Solving the equation

We start with the simplified equation ax = b mod m with (a,m)=1.

Take the (m-1) multiples a ; 2a ; 3a ; ... ; (m-1)a all taken mod m .

All these multiples are different!
If for instance 3a = 5a mod m then canceling a we have 3 = 5 mod m and this is impossible because 3 and 5 are smaller than m.

Hence, all these multiples are the numbers 1,2,3,...,m-1 in an arbitrary order.

Therefore, the equation ax = b mod m has just one solution modulo m.

In previous example, we try x = 1, 2 and 3 and we find that (3 mod 4) is the solution.

The equation ax = 1 mod m

Now consider the equation 
 
        ax  = 1 mod m
The theorem of Fermat gives a solution for a special case.

Theorem of Fermat

If p is prime and (a,p)=1 then a(p-1) = 1 mod p.

Proof:
From above we know that since (a,p)= 1, the (p-1) multiples
a mod p ; 2a mod p ; 3a mod p ; ... ; (p-1)a mod p
are the numbers 1,2,3,...,p-1 in an arbitrary order.

Hence,
(1a)(2a)(3a)...((p-1)a)= 1.2.3. ... .(p-1) mod p
Since (1,p)=(2,p)=(3,p)=..(p-1,p)=1 , we can use the cancellation law. 

 
So,
        a(p-1)   = 1 mod p

Euler function phi

Say m is a positive integer.

phi(m) = the number of positive integers n < m such that (n,m)=1.

Properties of the Euler function phi

It can be proved that :

If p is prime then phi(p) = p-1 and phi(p2)=p.(p-1)

If (a,b)=1 then phi(a.b) = phi(a).phi(b)


Generalisation of the theorem of Fermat

If (a,m) = 1 then aphi(m) = 1 mod m.

Proof:
Take all the numbers b from the set {1, 2, ... m} such that (b,m)=1.
Let b1, b2,..., bn be these numbers. n = phi(m) .

Take the multiples a.b1 mod m, a.b2 mod m, ...,a.bn mod m

All these numbers are different!
If for instance a.bi = a.bj mod m then from the cancellation law, we have bi = bj mod m and this is impossible.

Additionally, each number a.bi is relative prime to m since a and bi are relative prime to m.

Therefore, these n different numbers
a.b1 mod m, a.b2 mod m, ...,a.bn mod m
are the n different numbers relative prime to m.
So, these numbers are b1, b2,... bn in an arbitrary order.

Hence, (a.b1)(a.b2)...(a.bn) = b1.b2. ... .bn mod m 

 
Using the cancellation law, we have

        aphi(m)      = 1 mod m

The smallest solution of ax = 1 mod m with (a,m) = 1

Let n be the smallest strictly positive integer such that 
 
           an  = 1 mod m
Now we make the euclidian division phi(m) : n. It gives us a quotient q and a remainder r. phi(m) = n.q + r with r < n or r = 0. Hence, 
 
        1 = aphi(m)  = an q + r = 1. ar mod m  => ar = 1 mod m
This is impossible unless r = 0.

Thus phi(m) = n.q + 0 and n divides phi(m). Conclusion

The smallest strictly positive integer n such that 
 
           an  = 1 mod m
is a divisor of phi(m).

Second method to solve ax = b mod m

We start with the simplified equation ax = b mod m with (a,m)=1.
Then, 
 
                  a. x = b mod m

             multiply both sides with aphi(m)-1

<=>     a.aphi(m)-1 . x = b.aphi(m)-1          mod m

<=>                 x = b.aphi(m)-1            mod m


      b.aphi(m)-1    mod m  is the unique solution!

Solving systems with equations x = a mod m

This topic is treated via this link.

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