Congruences

In this section we will introduce two algebraic systems which can be constructed from integers. These systems will provide us with enlightening examples of many algebraic phenomena and will prove to be important in their own right. Throughout this section let n be a positive integer.

Definition 1: Let a,b Z. We say that a is congruent to b modulo n [denoted a b (mod n)] if n|(a - b).

Example 1: 5 7 (mod 2); 17 11 (mod 3).

If n is clear from context, we will sometimes write a b instead of a b (mod n). If a is not congruent to b modulo n, we write a b (mod n). Let us establish some of the elementary properties of congruence.

Proposition 2: (1) For all a Z, a a (mod n).

(2) If a b(mod n), then b a(mod n).

(3) If a b(mod n) and b c(mod n), then a c(mod n).

If a b(mod n) and c d(mod n), then (a + c) (b + d)(mod n) and ac bd(mod n). (4) If a b(mod n) and c d(mod n), then (a + c) (b + d)(mod n) and ac bd(mod n).

Proof: (1),(2) - Clear.

(3) If a b(mod n), b c(mod n), then n|(a - b), n|b-c. Therefore, by Equation 3 in the section on number theory, n|(a - b) + (b - c) n|a- c ac(mod n).

(4) If a b(mod n), c d(mod n), then n|a - b, n|c-d. Therefore, by Equation 3 in the section on number theory, we have

n|(a + c) - (b + d) (a + c) (b + d)(mod n).

Also, we have n|c(a - b),n|b(c - d). Therefore, by the definition of congruence we see that

ac bc(mod n),    bc bd(mod n).

Therefore by part (3), we have

ac bd(mod n).

Many facts concerning congruences are quite old. For example, in the beginning of the seventeenth century, the jurist and amateur mathematician Fermat proved that if a is an integer and p is a prime such that pa, then a^p-1 1(mod p). However, the first organized study of congruences was undertaken by Gauss in his book Disquistiones Arithemidae, written in 1801. In broad terms, one of Gauss's principal goals in the Disquistiones was to study the solutions (if any exist) of the congruence

a_nxⁿ + a_n-1x^n-1 + ... + a₀ 0(mod m),

where m,a₀,...,a_n are given integers and x is to be determined. The problem as stated is incredibly difficult and much nineteenth century research in number theory was aimed at its solution, which is not complete today.

Just to get a feel for Gauss's work, let us consider the particular congruence

x² a(mod p)

where a is a given integer and p is a prime. The congruence may or may not have a solution x. For example, if p = 3 and x is any integer, then x 0,1,2(mod 3), so that x² 0,1,2²(mod 3). Thus, if x is any integer, x² 0 or 1(mod 3), so that the congruence x² 2(mod 3) has no solutions. Legendre defined the symbol (a/p) as follows:

 0   if p|a,
 1   if pa and x² a(mod p) has a solution,
-1   otherwise.

One of Gauss's greatest achievements is the law of quadratic reciprocity, which asserts that if p and q are distinct, odd primes, then

Using the quadratic reciprocity law, it is possible to determine precisely when the congruence x² a(mod p) has a solution. Given the complexity of the above formulas, the reader should have no difficulty accepting the assertion that the problem of solving congruences of a higher degree is indeed very complicated.

Much work on congruences of higher degree was undertaken during the nineteenth century and these investigations have led to some of the most significant developments of the twentieth century and are still objects of research.

In this section we will concentrate on the theory of linear congruences. If k is an arbitrary integer, let k denote the set of all integers congruent to k modulo n. Then

k = {k + ns | s Z}.

Then sets k are called residue classes modulo n. Suppose that k is a given residue class. The division algorithm says that there exist s,k₀ Z such that k = ns + k₀, 0 < k₀ < n-1. Therefore, since

{k + ns | s Z} = {k₀ + nt | t Z},

we see that k is the same as one of the residue classes

Note that none of these latter residue classes are equal. For if i = j with 0 < i < j < n, then

{i + ns | s Z} = {j + nt | t Z},

so that j = i + ns for some s Z. But then j - i is divisible by n, which contradicts the fact that 0 < (j - i) < n. Thus we have shown there are precisely n different residue classes modulo n and that these are given by

Let us denote the set of all residue classes modulo n by Z_n.

From our above discussion, it is clear that every integer is contained in some residue class modulo n, and therefore

Z = 0 1 ... n-1.

Moreover, no integer is contained in two of the residue classes 0,1,...,n-1. Indeed, if x i j, 0 < i < j < n, then

i j =

Let us define addition and multiplication of elements of Z_n as follows:

That is, the sum (respectively, product) of two residue classes a and b is the residue class containing a + b (respectively, a · b). We must, of course, check that those definitions depend only on those residue classes a and b and not the choice of elements a and b. But this is easily accomplished using Proposition 2, part(4). For if a = c and b = d, then

a c(mod n),   b d(mod n),

(a + b) (c + d)(mod n),

a + b = c + d.

Therefore, the operation of addition of residue classes is consistent. A similar argument holds for multiplication.

Addition and multiplication are commutative and associative and the two operations obey the distributive law

The residue class 0 is the identity element with respect to addition:

a + 0 = 0 + a = a  (a Z_n).

The residue class 1 is the identity element with respect to multiplication:

a·1 = 1 · a = a  (a Z_n).

Every residue class a has an inverse -a with respect to addition. In fact we may set -a = -a. Then

Thus, in most respects, the algebraic system Z_n possesses the same properties as Z. However, there is at least one important difference. Recall that we proved that the product of two nonzero integers is nonzero. This property of Z does not carry over to Z_n. For example, let us consider Z₆. We clearly have 3 0, 2 0; nevertheless,

In this circumstance we say that 3 and 2 are divisors of zero. We leave to the reader the verification of the fact that if n is prime, then Z_n has no divisors of zero, while if n > 1 and not prime, then Z_n always has divisors of zero.

Note that if (a,n) = 1, then (a + kn, n) = 1 for all k Z. Therefore if one element of a residue class modulo n is relatively prime to n, every element of the residue class is relatively prime to n. When this occurs we say that the residue class is reduced. Let Z^x_n denote the set of all reduced residue classes modulo n.

Example 2: Z^x₆ = {1,5}; Z^x₇ = {1,2,3,4,5,6}; Z^x₁₀ = {1,3,7, 9}.

Since Z_n = {0,1,2,...,n-1}, and since a Z^x_n if and only if (a,n) = 1, we see that the number of elements in Z^x_n is equal to the number of positive integers a such that a < n and (a,n) = 1. This number is usually denoted (n). From the above examples, we see that

(6) = 2,   (7) = 6,   (10) = 4.

The function (n) is defined for positive integers n and is called Euler's phi function or totient.

If

is the decomposition of n into a product of powers of distinct primes, then

The reader should verify that this formula works in the special cases of the examples given above.

Proposition 3: Suppose that a, b Z^x_n. Then a · b Z^x_n.

Proof: Since a · b = a · b, it suffices to show that if (a,n) = 1, (b,n) = 1, then (a·b, n) = 1. Suppose that (a·b, n) > 1. Then (a·b,n) is divisible by some prime p. Therefore, p|a·b and p|n. However, by Theorem 8 of the section on Number Theory, either p|a or p|b. Suppose that p|a. Then since p|n, p|(a,n), which is a contradiction to the assumption (a,n) = 1.

By Proposition 3, · defines a law of multiplication among reduced residue classes. Since 1 Z^x_n, we se that Z^x_n contains an identity element with respect to ·.

Let a Z^x_n. Then there exists b Z^x_n such that a · b = b · a = 1. Proposition 4: Let a Z^x_n. Then there exists b Z^x_n such that

That is, a has an inverse with respect to multiplication.

Proof: It suffices to find b Z such that (b,n) = 1 and

a · b 1 (mod n).

Since (a,n) = 1, there exist x,y Z such that

We clearly have (x,n) = 1, since any common divisor of x and n divides a · x + n · y = 1. Moreover,

a · x 1(mod n).

Therefore, we may set x = b.

Proposition 4 has an interesting application. Let a,b,c Z and suppose that it is required to solve the equation

in integers. Such an equation is called a Diophantine equation, after the Greek mathematician Diophantus, who first studied its solutions. If d = (a,b), then d|(ax + by)d|c. Therefore, in order for (2) to have any solutions, we must have c = dc'. If we set a = a'd, b = b'd, we see that (2) is equivalent to the equation

But (a',b') = 1 since d = (a,b). Therefore, without loss of generality, we may restrict ourselves to equations of the form (2) for which (a,b) = 1. Equation (2) is equivalent to the congruence

ax c(mod b).

In turn, the congruence (3) is equivalent to the equation

among residue classes of Z_b. By Proposition 4, since (a,b) = 1, there exists a^* Z_b such that a · a^* = 1. Therefore (4) is equivalent to

a^* · a · x = a^* · c x = a^* · c.

Therefore, in order to solve Equation (2), it is sufficient to choose x so that

x a^*c(mod b).

Then ax - c is divisible by b. Choose y so that ax - c = -by. It is clear from the above argument that all solutions of equation (2) are obtained in this way.

Let us now give an example to show that this whole process is computationally viable. Consider the equation

Then 3^* = 2 since 3 · 2 1(mod 5). Therefore, we must choose x so that

x 24 (mod 5),

which is equivalent to

x 4 (mod 5).

For given x satisfying (5), set

For example, some solutions are x = 4, y = 0; x = 9, y = -3; x = -1, y = 3.