The set of integers. a|b, a|c a|(bx + cy)   for all integers x,y Let a be a nonnegative integer and let b be a positive integer. Then there exist natural numbers q and t such that 0 < r < b and a = bq + r. Let p be a prime. If p divides a product ab, then either p divides a or p divides b.

### 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 ap-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

anxn + an-1xn-1 + ... + a0 0(mod m),

where m,a0,...,an 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

x2 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 x2 0,1,22(mod 3). Thus, if x is any integer, x2 0 or 1(mod 3), so that the congruence x2 2(mod 3) has no solutions. Legendre defined the symbol (a/p) as follows:

0   if p|a,
1   if pa and x2 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

(p/q)(q/p) = (-1)(p-1)(q-1)/4,
(2/p) = (-1)(p2-1)/8,
(-1/p) = (-1)(p-1)/2.

Using the quadratic reciprocity law, it is possible to determine precisely when the congruence x2 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,k0 Z such that k = ns + k0, 0 < k0 < n-1. Therefore, since

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

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

0,1,...,n-1.

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

0,1,2...,n-1.

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

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 Zn as follows:

a + b = a + b,
a · b = a · b.

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

a·(b + c) = a·b + a·c.

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

a + 0 = 0 + a = a  (a Zn).

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

a·1 = 1 · a = a  (a Zn).

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

a + -a = -a + a = 0.

Thus, in most respects, the algebraic system Zn 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 Zn. For example, let us consider Z6. We clearly have 3 0, 2 0; nevertheless,

3 · 2 = 6 = 0.

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 Zn has no divisors of zero, while if n > 1 and not prime, then Zn 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 Zxn denote the set of all reduced residue classes modulo n.

Example 2: Zx6 = {1,5}; Zx7 = {1,2,3,4,5,6}; Zx10 = {1,3,7, 9}.

Since Zn = {0,1,2,...,n-1}, and since a Zxn if and only if (a,n) = 1, we see that the number of elements in Zxn 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

(1)

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

Proposition 3: Suppose that a, b Zxn. Then a · b Zxn.

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 Zxn, we se that Zxn contains an identity element with respect to ·.

Let a Zxn. Then there exists b Zxn such that a · b = b · a = 1. Proposition 4: Let a Zxn. Then there exists b Zxn such that

a · b = b · a = 1.

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

a · x + n · y = 1.

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

(2)
ax + by = c

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

a'x + b'y = c'.

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

(3)
ax c(mod b).

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

(4)
a · x = c

among residue classes of Zb. By Proposition 4, since (a,b) = 1, there exists a* Zb 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

3x + 5y = 12

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

x 24 (mod 5),

which is equivalent to

(5)
x 4 (mod 5).

For given x satisfying (5), set

y = (-3x + 12)/5.

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