Congruence modulo a prime number

From Encyclopedia of Mathematics
Jump to: navigation, search

A congruence in which the modulus is a prime number. A distinguishing feature of the theory of congruences modulo a prime number is the fact that the residue classes modulo form a finite field of elements. Congruences modulo a prime number can therefore be treated as equations over finite prime fields and algebraic-geometric methods, as well as methods of number theory, can be used to study them.

One of the basic questions in the theory of congruences with one variable , which is of great significance to algebraic number theory, coding theory and other branches of mathematics, is the question of the study of the laws of decomposition

modulo a prime number , of arbitrary integer polynomials into irreducible factors.

A second basic question in the theory of congruences modulo a prime number with variables is the question of the number of solutions of a congruence equation

when vary independently of each other over either the whole set of residue classes modulo (problems of complete residue systems), or over a particular part of it (problems of incomplete residue systems).

The first results of the research into the question of the number of solutions of quadratic and bi-quadratic congruences with two variables were obtained by C.F. Gauss [1] and J.L. Lagrange [2]. E. Artin [3] established a link between the problem of the number of solutions of the hyper-elliptic congruences () on a complete residue system modulo the prime number and the Riemann hypothesis for -functions of algebraic function fields with a finite field of constants, which were introduced by him. In particular, he stated the hypothesis that for the number of solutions of the congruence (), where the polynomial is not the square of another polynomial modulo , the estimate

is correct (here is the integer part of the number ).

Artin's hypothesis was first proved by H. Hasse [6] for the case of the elliptic congruences

A. Weil [8] subsequently extended the method of Hasse to cover the general case and obtained the estimate

for the number of solutions of the equation in elements of the field , consisting of elements, where is an absolutely-irreducible polynomial with coefficients from . The Hasse–Weil method is complicated and requires the use of modern abstract algebraic geometry. A simple and purely arithmetic method of proving the results of Hasse and Weil can be found in [7].

Congruences modulo a prime number with variables are less widely studied. The following theorem can be used here as a general result. Let be an absolutely-irreducible polynomial with integer coefficients. Then for the number of solutions of the congruence

the estimate

holds, where the constant does not depend on . A better estimate has been obtained by P. Deligne [9].

For results on congruences modulo a prime number on an incomplete residue system, see Vinogradov hypotheses; Two-term congruence; Distribution of power residues and non-residues.


[1] C.F. Gauss, "Untersuchungen über höhere Arithmetik" , Springer (1889) (Translated from Latin) MR0188045 Zbl 21.0166.04
[2] J.L. Lagrange, "Démonstration d'un théorème d'arithmétique" , Oeuvres , 3 , Paris (1869) pp. 189–201
[3] E. Artin, "Quadratische Körper in Gebiete der höheren Kongruenzen II" Math. Z. , 19 (1924) pp. 207–246
[4] I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian) MR0807530 Zbl 0577.01049
[5] H. Hasse, "Zahlentheorie" , Akademie Verlag (1963) MR0153659 Zbl 1038.11500
[6] H. Hasse, "Abstrakte Begründung der komplexen multiplication und Riemannsche Vermutung in Funktionenkörpern" Abh. Math. Sem. Hamburg Univ. , 10 (1934) pp. 325–347
[7] 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)
[8] A. Weil, "Courbes algébriques et variétés abéliennes. Sur les courbes algébriques et les varietés qui s'en deduisent" , Hermann (1948)
[9] P. Deligne, "La conjecture de Weil I" Publ. Math. IHES , 43 (1974) pp. 273–307 MR0340258 Zbl 0314.14007 Zbl 0287.14001


A polynomial over is absolutely irreducible if it is still irreducible over the algebraic closure of . For some material on polynomials over finite fields and their factorizations in the context of coding theory cf. [a1].


[a1] F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , I-II , North-Holland (1977)
[a2] G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 MR0568909 Zbl 0423.10001
How to Cite This Entry:
Congruence modulo a prime number. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article