3 Elementary Properties of Congruences

Chapter 3
Elementary Properties of Congruences

3.1 Congruences Modulo $m$

DEFINITIONS. If $a$ and $b$ are any two integers, positive or zero or negative, whose diﬀerence is divisible by $m$ , $a$ and $b$ are said to be congruent modulo $m$ , or congruent for the modulus $m$ , or congruent according to the modulus $m$ . Each of the numbers $a$ and $b$ is said to be a residue of the other.

To express the relation thus deﬁned we may write

a = b + c m,

where $c$ is an integer (positive or zero or negative). It is more convenient, however, to use a special notation due to Gauss, and to write

a \equiv b mod m,

an expression which is read $a$ is congruent to $b$ modulo $m$ , or $a$ is congruent to $b$ for the modulus $m$ , or $a$ is congruent to $b$ according to the modulus $m$ . This notation has the advantage that it involves only the quantities which are essential to the idea involved, whereas in the preceding expression we had the irrelevant integer $c$ . The Gaussian notation is of great value and convenience in the study of the theory of divisibility. In the present chapter we develop some of the fundamental elementary properties of congruences. It will be seen that many theorems concerning equations are likewise true of congruences with ﬁxed modulus; and it is this analogy with equations which gives congruences (as such) one of their chief claims to attention.

As immediate consequences of our deﬁnitions we have the following fundamental theorems:

I. If $a \equiv c mod m$ , $b \equiv c mod m$ , then $a \equiv b mod m$ ; that is, for a given modulus, numbers congruent to the same number are congruent to each other.

For, by hypothesis, $a - c = c_{1} m$ , $b - c = c_{2} m$ , where $c_{1}$ and $c_{2}$ are integers. Then by subtraction we have $a - b = (c_{1} - c_{2}) m$ ; whence $a \equiv b mod m$ .

II. If $a \equiv b mod m$ , $α \equiv β mod m$ , then $a \pm α \equiv b \pm β mod m$ ; that is, congruences with the same modulus may be added or subtracted member by member.

For, by hypothesis, $a - b = c_{1} m$ , $α - β = c_{2} m$ ; whence $(a \pm α) - (b \pm β) = (c_{1} \pm c_{2}) m$ . Hence $a \pm α = b \pm β mod m$ .

III. If $a = b mod m$ , then $c a = c b mod m$ , $c$ being any integer whatever.

The proof is obvious and need not be stated.

IV. If $a \equiv b mod m$ , $α \equiv β mod m$ , then $a α \equiv b β mod m$ ; that is, two congruences with the same modulus may be multiplied member by member.

For, we have $a = b + c_{1} m$ , $α = β + c_{2} m$ . Multiplying these equations member by member we have $a α = b β + m (b c_{2} + β c_{1} + c_{1} c_{2} m)$ . Hence $a α \equiv b β mod m$ .

A repeated use of this theorem gives the following result:

V. If $a \equiv b mod m$ , then $a^{n} \equiv b^{n} mod m$ where $n$ is any positive integer.

As a corollary of theorems II, III and V we have the following more general result:

VI. If $f (x)$ denotes any polynomial in $x$ with coeﬃcients which are integers (positive or zero or negative) and if further $a \equiv b mod m$ , then

f (a) \equiv f (b) mod m .

3.2 Solutions of Congruences by Trial

Let $f (x)$ be any polynomial in $x$ with coeﬃcients which are integers (positive or negative or zero). Then if $x$ and $c$ are any two integers it follows from the last theorem of the preceding section that

f (x) \equiv f (x + c m) mod m .

(1)

Hence if $a$ is any value of $x$ for which the congruence

f (x) \equiv 0 mod m .

(2)

is satisﬁed, then the congruence is also satisﬁed for $x = α + c m$ , where $c$ is any integer whatever. The numbers $α + c m$ are said to form a solution (or to be a root) of the congruence, $c$ being a variable integer. Any one of the integers $α + c m$ may be taken as the representative of the solution. We shall often speak of one of these numbers as the solution itself.

Among the integers in a solution of the congruence (2) there is evidently one which is positive and not greater than $m$ . Hence all solutions of a congruence of the type (2) may be found by trial, a substitution of each of the numbers $1, 2, \dots, m$ being made for $x$ . It is clear also that $m$ is the maximum number of solutions which (2) can have whatever be the function $f (x)$ . By means of an example it is easy to show that this maximum number of solutions is not always possessed by a congruence; in fact, it is not even necessary that the congruence have a solution at all.

This is illustrated by the example

x^{2} - 3 \equiv 0 mod 5 .

In order to show that no solution is possible it is necessary to make trial only of the values $1, 2, 3, 4, 5$ for $x$ . A direct substitution veriﬁes the conclusion that none of them satisﬁes the congruence; and hence that the congruence has no solution at all.

On the other hand the congruence

x^{5} - x \equiv 0 mod 5

has the solutions $x = 1, 2, 3, 4, 5$ as one readily veriﬁes; that is, this congruence has ﬁve solutions—the maximum number possible in accordance with the results obtained above.

EXERCISES

1.: Show that ${(a + b)}^{p} \equiv a^{p} + b^{p} mod p$ where $a$ and $b$ are any integers and $p$ is any prime.
2.: From the preceding result prove that $α^{p} \equiv α mod p$ for every integer $α$ .
3.: Find all the solutions of each of the congruences $x^{11} \equiv x mod 11, x^{10} \equiv 1 mod 11, x^{5} \equiv 1 mod 11$ .

3.3 Properties of Congruences Relative to Division

The properties of congruences relative to addition, subtraction and multiplication are entirely analogous to the properties of algebraic equations. But the properties relative to division are essentially diﬀerent. These we shall now give.

I. If two numbers are congruent modulo $m$ they are congruent modulo $d$ , where $d$ is any divisor of $m$ .

For, from $a \equiv b mod m$ , we have $a = b + c m = b + c' d$ . Hence $a \equiv b mod d$ .

II. If two numbers are congruent for diﬀerent moduli they are congruent for a modulus which is the least common multiple of the given moduli.

The proof is obvious, since the diﬀerence of the given numbers is divisible by each of the moduli.

III. When the two members of a congruence are multiples of an integer $c$ prime to the modulus, each member of the congruence may be divided by $c$ .

For, if $c a \equiv c b mod m$ then $c a - c b$ is divisible by $m$ . Since $c$ is prime to $m$ it follows that $a - b$ is divisible by $m$ . Hence $a \equiv b mod m$ .

IV. If the two members of a congruence are divisible by an integer $c$ , having with the modulus the greatest common divisor $δ$ , one obtains a congruence equivalent to the given congruence by dividing the two members by $c$ and the modulus by $δ$ .

By hypothesis $a c \equiv b c mod m, c = δ c_{1}, m = δ m_{1}$ . Hence $c (a - b)$ is divisible by $m$ . A necessary and suﬃcient condition for this is evidently that $c_{1} (a - b)$ is divisible by $m_{1}$ . This leads at once to the desired result.

3.4 Congruences with a Prime Modulus

The congruence²

a_{0} x^{n} + a_{1} x^{n - 1} + \dots + a_{n} \equiv 0 mod p, a_{0} ≢ 0 mod p

where $p$ is a prime number and the $a$ ’s are any integers, has not more than $n$ solutions.

Denote the ﬁrst member of this congruence by $f (x)$ so that the congruence may be written

f (x) \equiv 0 mod p

(1)

Suppose that $a$ is a root of the congruence, so that

f (a) \equiv 0 mod p .

Then we have f(x)

\equiv f (x) - f (a) mod p .

But, from algebra, $f (x) - f (a)$ is divisible by $x - a$ . Let ${(x - a)}^{α}$ be the highest power of $x - a$ contained in $f (x) - f (a)$ . Then we may write

f (x) - f (a) = {(x - a)}^{α} f_{1} (x),

(2)

where $f_{1} (x)$ is evidently a polynomial with integral coeﬃcients. Hence we have

f (x) \equiv {(x - a)}^{α} f_{1} (x) mod p .

(3)

We shall say that $a$ occurs $α$ times as a solution of (1); or that the congruence has $α$ solutions each equal to $a$ .

Now suppose that congruence (1) has a root $b$ such that $b ≢ a mod p$ . Then from (3) we have

\begin{matrix} f (b) \equiv {(b - a)}^{α} f_{1} (b) mod p . \end{matrix}

But

\begin{matrix} f (b) \equiv 0 mod p, {(b - a)}^{α} ≢ 0 mod p . \end{matrix}

Hence, since $p$ is a prime number, we must have

\begin{matrix} f_{1} (b) \equiv 0 mod p . \end{matrix}

By an argument similar to that just used above, we may show that $f_{1} (x) - f_{1} (b)$ may be written in the form

\begin{matrix} f_{1} (x) - f_{1} (b) = {(x - b)}^{β} f_{2} (x), \end{matrix}

where $β$ is some positive integer. Then we have

\begin{matrix} f (x) \equiv {(x - a)}^{α} {(x - b)}^{β} f_{2} (x) mod p . \end{matrix}

Now this process can be continued until either all the solutions of (1) are exhausted or the second member is a product of linear factors multiplied by the integer $a_{0}$ . In the former case there will be fewer than $n$ solutions of (1), so that our theorem is true for this case. In the other case we have

f (x) \equiv a_{0} {(x - a)}^{α} {(x - b)}^{β} \dots {(x - l)}^{λ} mod p .

We have now $n$ solutions of (1): $a$ counted $α$ times, $b$ counted $β$ times, …, $l$ counted $λ$ times; $α + β + \dots + λ = n$ .

Now let $η$ be any solution of (1). Then

f (η) \equiv a_{0} {(η - a)}^{α} {(η - b)}^{β} \dots {(η - l)}^{λ} \equiv 0 mod p .

Since $p$ is prime it follows now that some one of the factors $η - a, η - b, \dots, η - l$ is divisible by $p$ . Hence $η$ coincides with one of the solutions $a, b, c, \dots, l$ . That is, (1) can have only the $n$ solutions already found.

This completes the proof of the theorem.

EXERCISES

1.

Construct a congruence of the form

a_{0} x^{n} + a_{1} x^{n - 1} + \dots + a_{n} \equiv 0 mod m, a_{0} ≢ 0 mod m,

having more than $n$ solutions and thus show that the limitation to a prime modulus in the theorem of this section is essential.

2.

Prove that

x^{6} - 1 \equiv (x - 1) (x - 2) (x - 3) (x - 4) (x - 5) (x - 6) mod 7

for every integer $x$ .

3.

How many solutions has the congruence

x^{5} \equiv 1 mod 11

? the congruence

x^{5} \equiv 2 mod 11

3.5 Linear Congruences

From the theorem of the preceding section it follows that the congruence

a x \equiv c mod p, a ≢ 0 mod p,

where $p$ is a prime number, has not more than one solution. In this section we shall prove that it always has a solution. More generally, we shall consider the congruence

a x \equiv c mod m

where $m$ is any integer. The discussion will be broken up into parts for convenience in the proofs.

I. The congruence

a x \equiv 1 mod m,

(1)

in which a and m are relatively prime, has one and only one solution.

The question as to the existence and number of the solutions of (1) is equivalent to the question as to the existence and number of integer pairs $x, y$ satisfying the equation,

a x - m y = 1,

(2)

the integers $x$ being incongruent modulo $m$ . Since $a$ and $m$ are relatively prime it follows from theorem IV of § 1.9 that there exists a solution of equation (2). Let $x = α$ and $y = β$ be a particular solution of (2) and let $x = \bar{α}$ and $y = \bar{β}$ be any solution of (2). Then we have

\begin{matrix} a α - m β = 1, \\ a \bar{α} - m \bar{β} = 1; \end{matrix}

whence

\begin{matrix} a (α - \bar{α}) - m (β - \bar{β}) = 0 . \end{matrix}

Hence $α - \bar{α}$ is divisible by $m$ , since $a$ and $m$ are relatively prime. That is, $a \equiv \bar{α} mod m$ . Hence $α$ and $\bar{α}$ are representatives of the same solution of (1). Hence (1) has one and only one solution, as was to be proved.

II. The solution $x = α$ of the congruence $a x \equiv 1 mod m$ , in which $a$ and $m$ are relatively prime, is prime to $m$ .

For, if $a α - 1$ is divisible by $m$ , $α$ is divisible by no factor of $m$ except $1$ .

III. The congruence

a x \equiv c mod m

(3)

in which $a$ and $m$ and also $c$ and $m$ are relatively prime, has one and only one solution.

Let $x = γ$ be the unique solution of the congruence $c x = 1 mod m$ . Then we have $a γ x \equiv c γ \equiv 1 mod m$ . Now, by I we see that there is one and only one solution of the congruence $a γ x \equiv 1 mod m$ ; and from this the theorem follows at once.

Suppose now that $a$ is prime to $m$ but that $c$ and $m$ have the greatest common divisor $δ$ which is diﬀerent from 1. Then it is easy to see that any solution $x$ of the congruence $a x \equiv c mod m$ must be divisible by $δ$ . The question of the existence of solutions of the congruence $a x \equiv c mod m$ is then equivalent to the question of the existence of solutions of the congruence

a \frac{x}{δ} \equiv \frac{c}{δ} mod \frac{m}{δ},

where $\frac{x}{δ}$ is the unknown integer. From III it follows that this congruence has a unique solution $\frac{x}{δ} = α$ . Hence the congruence $a x \equiv c mod m$ has the unique solution $x = δ α$ . Thus we have the following theorem:

IV. The congruence $a x \equiv c mod m$ , in which $a$ and $m$ are relatively prime, has one and only one solution.

COROLLARY. The congruence $a x \equiv c mod p$ , $a ≢ 0 mod p$ , where $p$ is a prime number, has one and only one solution.

It remains to examine the case of the congruence $a x = c mod m$ in which $a$ and $m$ have the greatest common divisor $d$ . It is evident that there is no solution unless $c$ also contains this divisor $d$ . Then let us suppose that $a = α d$ , $c = γ d$ , $m = μ d$ . Then for every $x$ such that $a x = c mod m$ we have $α x = γ mod μ$ ; and conversely every $x$ satisfying the latter congruence also satisﬁes the former. Now $α x = γ mod μ$ , has only one solution. Let $β$ be a non-negative number less than $μ$ , which satisﬁes the congruence $α x = γ mod μ$ . All integers which satisfy this congruence are then of the form $β + μ ν$ , where $ν$ is an integer. Hence all integers satisfying the congruence $a x = c mod m$ are of the form $β + μ ν$ ; and every such integer is a representative of a solution of this congruence. It is clear that the numbers

β, β + μ, β + 2 μ, \dots, β + (d - 1) μ

(A)

are incongruent modulo $m$ while every integer of the form $β + μ ν$ is congruent modulo $m$ to a number of the set (A). Hence the congruence $a x = c mod m$ has the $d$ solutions (A).

This leads us to an important theorem which includes all the other theorems of this section as special cases. It may be stated as follows:

V. Let

a x \equiv c mod m

be any linear congruence and let $a$ and $m$ have the greatest common divisor $d (d \geq 1)$ . Then a necessary and suﬃcient condition for the existence of solutions of the congruence is that $c$ be divisible by $d$ . If this condition is satisﬁed the congruence has just $d$ solutions, and all the solutions are congruent modulo $m / d$ .

EXERCISES

1.: Find the remainder when $2^{40}$ is divided by $31$ ; when $2^{43}$ is divided by $31$ .
2.: Show that $2^{2^{5}} + 1$ has the factor $641$ .
3.: Prove that a number is a multiple of $9$ if and only if the sum of its digits is a multiple of $9$ .
4.: Prove that a number is a multiple of $11$ if and only if the sum of the digits in the odd numbered places diminished by the sum of the digits in the even numbered places is a multiple of $11$ .

ptail

top

Chapter 3Elementary Properties of Congruences

3.1 Congruences Modulo m

3.2 Solutions of Congruences by Trial

3.3 Properties of Congruences Relative to Division

3.4 Congruences with a Prime Modulus

3.5 Linear Congruences

Chapter 3
Elementary Properties of Congruences

3.1 Congruences Modulo $m$