View source for Congruence modulo a prime number

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249001.png" /> form a finite field of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249002.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249003.png" />, which is of great significance to [[Algebraic number theory|algebraic number theory]], coding theory and other branches of mathematics, is the question of the study of the laws of decomposition

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249004.png" /></td> </tr></table>

modulo a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249005.png" />, of arbitrary integer polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249006.png" /> into irreducible factors.

A second basic question in the theory of congruences modulo a prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249007.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249008.png" /> variables is the question of the number of solutions of a [[Congruence equation|congruence equation]]

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c0249009.png" /></td> </tr></table>

when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490010.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490011.png" /> vary independently of each other over either the whole set of residue classes modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490012.png" /> (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 [[#References|[1]]] and J.L. Lagrange [[#References|[2]]]. E. Artin [[#References|[3]]] established a link between the problem of the number of solutions of the hyper-elliptic congruences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490013.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490014.png" />) on a complete residue system modulo the prime number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490015.png" /> and the Riemann hypothesis for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490016.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490017.png" /> of solutions of the congruence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490018.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490019.png" />), where the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490020.png" /> is not the square of another polynomial modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490021.png" />, the estimate

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490022.png" /></td> </tr></table>

is correct (here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490023.png" /> is the integer part of the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490024.png" />).

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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490025.png" /></td> </tr></table>

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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490026.png" /></td> </tr></table>

for the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490027.png" /> of solutions of the equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490028.png" /> in elements of the field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490029.png" />, consisting of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490030.png" /> elements, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490031.png" /> is an absolutely-irreducible polynomial with coefficients from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490032.png" />. 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 [[#References|[7]]].

Congruences modulo a prime number with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490033.png" /> variables are less widely studied. The following theorem can be used here as a general result. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490034.png" /> be an absolutely-irreducible polynomial with integer coefficients. Then for the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490035.png" /> of solutions of the congruence

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490036.png" /></td> </tr></table>

the estimate

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490037.png" /></td> </tr></table>

holds, where the constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490038.png" /> does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490039.png" />. A better estimate has been obtained by P. Deligne [[#References|[9]]].

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

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> C.F. Gauss, "Untersuchungen über höhere Arithmetik" , Springer (1889) (Translated from Latin) {{MR|0188045}} {{ZBL|21.0166.04}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> J.L. Lagrange, "Démonstration d'un théorème d'arithmétique" , ''Oeuvres'' , '''3''' , Paris (1869) pp. 189–201</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> E. Artin, "Quadratische Körper in Gebiete der höheren Kongruenzen II" ''Math. Z.'' , '''19''' (1924) pp. 207–246</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian) {{MR|0807530}} {{ZBL|0577.01049}} </TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> H. Hasse, "Zahlentheorie" , Akademie Verlag (1963) {{MR|0153659}} {{ZBL|1038.11500}} </TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> H. Hasse, "Abstrakte Begründung der komplexen multiplication und Riemannsche Vermutung in Funktionenkörpern" ''Abh. Math. Sem. Hamburg Univ.'' , '''10''' (1934) pp. 325–347</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top"> 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)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top"> P. Deligne, "La conjecture de Weil I" ''Publ. Math. IHES'' , '''43''' (1974) pp. 273–307 {{MR|0340258}} {{ZBL|0314.14007}} {{ZBL|0287.14001}} </TD></TR></table>



====Comments====
A polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490040.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490041.png" /> is absolutely irreducible if it is still irreducible over the algebraic closure <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490042.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c024/c024900/c02490043.png" />. For some material on polynomials over finite fields and their factorizations in the context of coding theory cf. [[#References|[a1]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> F.J. MacWilliams, N.J.A. Sloane, "The theory of error-correcting codes" , '''I-II''' , North-Holland (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8 {{MR|0568909}} {{ZBL|0423.10001}} </TD></TR></table>