# Congruences

Congruences are an important tool for the study of divisibility.

Definition.

Let be an integer.

Two integers and are congruent modulo if divides . We write:

We read this as ” is congruent to modulo “.

The integer is called the modulus.

If does not divides , then is incongruent to and we write .

If , then is a residue of modulo . When , then is called the least non – negative residue of modulo .

Since is divisible by if and only if it is divisible by , without loss generality we can focus on the positive modulus and in the hereafter will be a natural number.

Definition.

Let . The set of all integers that are congruent modulo to is called a residue class modulo .

All members which are in the same residue class are mutually congruent.

We will first show that each integer falls in one and only one residue class.

Theorem 1. Congruences modulo satisfy:

1.) refleksive;

2.) symmetric;

3.) transitive;

This means, the congruence relation is an equivalence relation on the set . Therefore, the residue classes partition the integers.

Proof.

1.)If , then . Since is divisible by any integer, that is valid.

2.) If , then . Therefore, or , that is, .

3.) If and , then and . It follows that , that is, .

Hence , every integer falls in one and only one residue class.

There are exactly residue classes modulo , which is discussed in the following theorem.

Theorem 2. Let . There exist exactly residue classes. In particular,

gives a complete set of residue classes.

There are infinitely many sets of complete residue classes. In particular, a set is called a complete residue system modulo if for each integer there is exactly one such that

In other words, a complete residue system we obtain so we take by one member of the each equivalence class.

The residue classes have the following important property:

If one element of the some residue class modulo is relatively prime with , then it is and every other element of the same class.

A reduced residue system modulo is the subset of a complete residue system consisting only those  elements that are relatively prime with .

A reduced class modulo has exactly elements, where is with denoted the Euler’s phi-function.

Theorem 3. Let be a complete residue system modulo , and . Then is also a complete residue system modulo .

The definition of congruence can be represented as:

The following theorem gives an equivalent way of looking at congruences.

Theorem 4.  If , then , and conversely.

We know that equality can be added, subtracted and multiplied. Analogous properties also apply to congruences, which gives us the following theorem.

Theorem 5. If and , then

a) ,

b) ,

c) ,

and

d) , for some ,

is valid.

We can add, subtract and multiply only those congruences that have the same modulus. We find that the congruence multiplies an integer so that and we multiply whit this number, and the modulus remains the same.

Theorem 6. If and , then

is valid.

Specifically, if and , then .

Consider that on the concrete example. We take the congruence . We divide congruence by . Since , that we obtain .

Definition. An integer is said to be a multiplicative inverse of modulo if satisfies .

Theorem 7. (Existence of multiplicative inverse) Let be an integer. Then has a multiplicative inverse modulo if and only if .

Congruences can also be raised to powers, which provides us with the following theorem.

Theorem 8. If and , then

Notice that the statement of the Theorem 8. in a trivial way filled for . The specified result we can generalize.

Proposition 1. Let be a polynomial with integer coefficients. If , then .

For the divisibility theory of basic importance is the following theorem:

Theorem 9. Let and . The numbers and leave the same remainder when divided with if and only if .

We will show now how to solve some problems from the divisibility theory, by using congruences.

Example 1. Find the remainder when the number is divided with .

Solution.

By the remainder theorem we have:

It follows:

By using the theorem 8. we obtain the following:

From the theorem 9. now it follows that and leave the same remainder when divided by . Therefore, we must determine the remainder when the number is divided by .

Since , that the requested remainder is equal to remainder when is divided by .

We use now the remainder theorem on the pair :

It follows:

From the theorem 8. now it follows that

that is,

Therefore, the remainder when is divided by is .

Example 2. Find the remainder when the number is divided by .

Solution.

Let . Since and , that by theorems 5. and 8. follows:

By the theorem 9. we have now that the number leaves the same remainder when it is divided by as the number . Write this number as:

Since and , that by theorems 5. and 8. follows:

Therefore, the number gives the remainder by dividing with .

Sometimes it is very useful to use the following fact:

If and , then .

We will show now how to use this rule.

Example 3. Determine the last two digits of the number .

Solution.

The last two digits of the given number are in fact digits of the remainder which we obtain by dividing this number with . Firstly, we will write the given number on the following way:

Since , that by the theorem 7. follows .

Therefore, the requested remainder is equal to the remainder which we obtain by dividing the number with . Write this number as

Since , by the theorem 7. follows:

The above congruence we write in the following way:

Since , that by substituting it in the previous congruence, we obtain

that is,

Finally. since , we have

Hence the last two digits of is .

Solution to a congruence

The solution to the congruence , where is a polynomial with integer coefficients,  is each integer that satisfies this congruence.

If is one solution to the congruence , and , then is also a solution to the above congruence (by the proposition 1.), that is, the whole class .

Two solutions and are equivalent if . The number of solutions to a congruence is equal to the number of non- equivalent solutions.

Example 4. Solve the following congruence:

Solution.

The one obvious solution to the given congruence is , because . However, a solution to this congruence is also a whole class modulo to which belongs the number .  This means that the solution to the given congruence are all integers that leave the remainder when are divided by , and all of these numbers are of the form . We have now:

that is,

and this congruence holds. Therefore, the solution to  is

Shares