Congruence

A relation between two integers and of the form , signifying that the difference between them is divisible by a given positive integer , which is called the modulus (or module) of the congruence; is then called a remainder of modulo (cf. Remainder of an integer). In order to express the congruence of the numbers and modulo , the symbol

is used. If the difference is not divisible by , then and are said to be incongruent modulo , and in order to express the incongruency of and , the symbol

is used. The congruence expresses that and have identical remainders when divided by .

Congruence modulo a fixed is an equivalence relation: it is reflexive, since (); symmetric, since it follows from () that (); and transitive, since it follows from () and () that (). Therefore, the relation " (modm)" divides the set of all integers into non-intersecting equivalence classes . Two integers belong to one and the same class if and only if they are congruent modulo . These classes are called residue classes modulo . Every integer is congruent modulo with just one of the numbers ; the numbers belong to different classes, so that there are exactly residue classes, while the numbers form a set of representatives of these classes. Any set of integers containing one number from each residue class is called a complete residue system modulo .

Congruences modulo one and the same number can be added, subtracted and multiplied in the same way as normal equalities, i.e. it follows from

that

Both parts of a congruence can be multiplied by one and the same integer, and both can be divided by a common divisor, as long as the divisor is relatively prime with the modulus of the congruence. If a common divisor of a number by which both parts of the congruence are divisible and the modulus of the congruence is , then after dividing by a congruence modulo is obtained.

The operations of addition, subtraction and multiplication of congruences induce similar operations on the residue classes. Thus, if and are arbitrary elements from the residue classes and , respectively, then always belongs to one and the same residue class, called the sum of the classes and . The difference and the product of the two residue classes and are defined in the same way. The residue classes modulo form an Abelian group of order with respect to addition. The zero element of this group is the class consisting of all integers that are multiples of the number ; the negative (inverse) of a class is the class consisting of all elements of with a minus sign. Moreover, the residue classes modulo form a ring relative to the above-defined operations of addition, subtraction and multiplication.

Let be a polynomial in variables with integer coefficients. An equation of the form

(*)

is called a congruence equation. A solution of the congruence (*) is any set of integer values of the unknowns such that the number is congruent to zero modulo . If , , belong to the residue classes modulo , then any other set , , is also a solution of the congruence. One therefore calls the set of residue classes itself, of which are representatives, a solution of the congruence (*), i.e. a solution of the algebraic equation in the ring of residue classes modulo . Given this manner of speaking, the congruence (*) has as many solutions as there are sets of residue classes of a complete system modulo that satisfy the equation . The number of solutions of more general forms of congruences, as well as of systems of congruences, is defined in the same way.

A congruence of the first degree

where is relatively prime with (this is denoted by ), has a unique solution. Those residue classes modulo whose elements are relatively prime with form an Abelian group with respect to multiplication. The unit of this group is the class which contains the number 1, while the inverse of a class is the class that contains the solutions of the congruence

The residue classes modulo consisting of elements which are relatively prime with are called reduced classes, while any system of numbers containing one number from each reduced class is called a reduced residue system. A reduced residue system consists of elements, where is the Euler function, which is equal to the number of elements in the set that are relatively prime with .

The structure of the multiplicative group of reduced residue classes modulo is explained to a significant degree by the theorems of L. Euler and P. Fermat, which show that the order of any element of the group divides .

Euler's theorem. If and are relatively prime, then

(see Euler theorem).

The particular case of this theorem for a prime modulus is Fermat's theorem: If is a prime number and is not divisible by , then

(see Fermat little theorem).

An important concept in the study of the multiplicative group of reduced residue classes is the concept of a primitive root modulo . When , there exists a positive integer for which (), for example . The least of these is called the index to which the modulo belongs.

Numbers which belong to the index (if there are any) are called primitive roots modulo . If is a primitive root modulo and runs through a complete residue system modulo , then runs through a reduced residue system modulo . Thus, if , then for a certain from the set , the congruence () holds. This is called the index of the number modulo with respect to the basis and is denoted by the symbol or, more precisely, . The properties of an index are broadly the same as the properties of a logarithm. Primitive roots exist only for moduli of the form , where is a prime number and is an integer. In these cases, the multiplicative group of reduced residue classes modulo is simply the cyclic group of order . In the other cases, the groups of reduced residue classes have a much more complex structure.

Many problems in number theory reduce to the question of the solvability or unsolvability of some type of congruence. As a result of this, the theory of congruences, which was first systematically developed by C.F. Gauss (see [5]) and used by him as a foundation of classical number theory, is to this day one of the basic means of solving number-theoretical problems. In this connection, research into the question of the number of solutions of a congruence equation is of fundamental importance to number theory. The simplest types of congruence equations are congruences of the first degree with one unknown (). A complete answer to the question of the number of solutions of congruences of the first degree is provided by the following theorem. Let . The congruence () is unsolvable if is not divisible by . When is a multiple of , the congruence has precisely solutions.

The question of the solvability of a system of linear congruences

modulo a prime number is solved completely in the general theory of linear equations over arbitrary fields. The case of a composite modulus can be reduced to the case of a prime modulus.

The form of algebraic congruences with one unknown which is the next most complex to study is a two-term congruence

If the congruence has solutions, then is called an -th power residue modulo ; if it does not, then is called an -th power non-residue modulo . More specifically, when , the residues or non-residues are called quadratic, when , cubic, and when , bi-quadratic.

The question of the number of solutions of a congruence

modulo a composite number reduces to the question of the number of solutions of the congruence

for every . The following theorem holds: If are pairwise relatively prime (coprime) positive integers, then the number of solutions of the congruence () can be expressed by the values , , which are equal to the number of solutions of the corresponding congruences () according to the formula . In its turn, the question of the number of solutions of the congruence

generally reduces to the question of the number of solutions of the congruence () where is a prime number. The following theorem forms the basis of this reduction: Every solution () of a congruence () can be uniquely continued to a solution () of the congruence () provided that the formal derivative (), i.e. a unique solution of the congruence () then exists such that ().

A similar situation also arises in the case of a congruence equation in several variables, i.e. in non-degenerate cases the question of the number of solutions of the congruence (), modulo a composite number reduces to the question of the number of solutions of the same congruence modulo a prime number .

An upper bound for the number of solutions of a congruence (), where , (), is given by Lagrange's theorem: The number of solutions of a congruence () does not exceed the degree of the polynomial . The study of the question of the exact number of solutions of the congruence () generally meets with considerable difficulties, so that only a few results have so far (1984) been obtained in this area.

The Lagrange theorem ceases to hold in the case of a composite modulus. The above-mentioned specific property of prime numbers is explained by the fact that the residue classes modulo a prime number form a field (see Congruence modulo a prime number). Another specific property of prime numbers which is explained by this fact is expressed in the Wilson theorem.

In the study of quadratic congruences

modulo a prime number , as well as in their applications, the Legendre symbol and the Jacobi symbol are introduced.

Congruence equations modulo a prime number in two unknowns (and generally in any number of unknowns),

can be treated as equations over the finite prime field of elements. Methods of the theory of algebraic functions and algebraic geometry are therefore used in studying them, as well as methods of number theory. Using these methods, an asymptotic expansion in the form

was first obtained for the number of solutions of a broad class of congruences (). The same asymptotic expansions were subsequently deduced using methods of number theory without going beyond the limits of the theory of congruences (see [6]).

Comparatively little is known about algebraic congruences in several unknowns. The following can be considered as a general result (Chevalley's theorem). Let be a polynomial with integer rational coefficients, the degree of which is less than . The number of solutions of the congruence

is then divisible by the prime number . One very strong result for this type of questions was obtained by P. Deligne [9] (see also [10]).

Great value is also attached to research into the question of the number of solutions of congruences in an incomplete residue system. A systematic solution to this type of problems was first attempted by I.M. Vinogradov (see [4]). An example of this type of problems is the problem of the distribution of quadratic residues and non-residues in the set , which is connected with the study of solutions of the congruence () (see Vinogradov hypotheses; Distribution of power residues and non-residues).

References

[1]	Z.I. Borevich, I.R. Shafarevich, "Number theory" , Acad. Press (1966) (Translated from Russian) (German translation: Birkhäuser, 1966)
[2]	B.A. Venkov, "Elementary number theory" , Wolters-Noordhoff (1970) (Translated from Russian)
[3]	I.M. Vinogradov, "Fundamentals of number theory" , Moscow (1972) (In Russian)
[4]	I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian)
[5]	C.F. Gauss, "Untersuchungen über höhere Arithmetik" , Springer (1889) (Translated from Latin)
[6]	S.A. Stepanov, "A constructive method in the theory of equations over finite fields" Trudy Mat. Inst. Steklov. , 132 (1973) pp. 237–246 (In Russian)
[7]	H. Hasse, "Zahlentheorie" , Akademie Verlag (1963)
[8]	K. Chandrasekharan, "Introduction to analytic number theory" , Springer (1968)
[9]	P. Deligne, "La conjecture de Weil I" Publ. Math. IHES , 43 (1974) pp. 273–307
[10]	N.M. Katz, "An overview of Deligne's proof of the Riemann hypothesis for varieties over finite fields" F.E. Browder (ed.) , Mathematical developments arising from Hilbert problems , Proc. Symp. Pure Math. , 28 , Amer. Math. Soc. (1976) pp. 275–305

Comments

The simultaneous system of congruences (), , where for all , has a unique residue class modulo as solution. This is the content of the Chinese remainder theorem.

The procedure to extend solutions of () to solutions of () is described in the Hensel lemma (cf. [a2]), and extends to a technique in the theory of -adic numbers (cf. -adic number).

References

[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapt. 5; 7; 8
[a2]	N. Koblitz, "-adic numbers, -adic analysis and zeta-functions" , Springer (1977) pp. Chapt. 1