Make your own free website on Tripod.com
The set of integers. a|b, a|c inpliesa|(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 element of Z. We say that a is congruent to b modulo n [denoted a congruent b (mod n)] if n|(a - b).

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

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

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

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

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

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

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

(3) If a congruent b(mod n), b congruent 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) implies n|a- c implies acongruentc(mod n).

(4) If a congruent b(mod n), c congruent 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) implies (a + c) congruent (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 congruent bc(mod n),    bc congruent bd(mod n).

Therefore by part (3), we have

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

Legendre function  0   if p|a,
 1   if pdoes not dividea and x2 congruent 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 congruent 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 element of 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 element of Z} = {k0 + nt | t element of 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 element of Z} = {j + nt | t element of Z},

so that j = i + ns for some s element of 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 union 1 union ... union n-1.

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

i intersect j = empty set

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 congruent c(mod n),   b congruent d(mod n),
implies (a + b) congruent (c + d)(mod n),
implies 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 element of Zn).

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

a·1 = 1 · a = a  (a element of 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 not equal 0, 2 not equal 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 element of 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 element of 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 phi(n). From the above examples, we see that

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

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

If

product of primes

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

(1)
Eulers Phi function

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

Proposition 3: Suppose that a, b element of Zxn. Then a · b element of 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 element of Zxn, we se that Zxn contains an identity element with respect to ·.

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

a · b = b · a = 1.

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

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

a · b congruent 1 (mod n).

Since (a,n) = 1, there exist x,y element of 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 congruent 1(mod n).

Therefore, we may set x = b.

Proposition 4 has an interesting application. Let a,b,c element of 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)impliesd|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 congruent 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* element of Zb such that a · a* = 1. Therefore (4) is equivalent to

a* · a · x = a* · c equivalent x = a* · c.

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

x congruent 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 congruent 1(mod 5). Therefore, we must choose x so that

x congruent 24 (mod 5),

which is equivalent to

(5)
x congruent 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.