View source for Congruence modulo a prime number

<!--
c0249001.png
$#A+1 = 43 n = 0
$#C+1 = 43 : ~/encyclopedia/old_files/data/C024/C.0204900 Congruence modulo a prime number
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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  $  p $
form a finite field of  $  p $
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  $  x $, 
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

$$ 
f( x)  \equiv  f _ {1} ( x) \dots f _ {r} ( x)  (  \mathop{\rm mod}  p) ,
$$

modulo a prime number  $  p $, 
of arbitrary integer polynomials  $  f( x) $
into irreducible factors.

A second basic question in the theory of congruences modulo a prime number  $  p $
with  $  n \geq  2 $
variables is the question of the number of solutions of a [[Congruence equation|congruence equation]]

$$ 
f( x _ {1} \dots x _ {n} )  \equiv  0  (  \mathop{\rm mod}  p),
$$

when  $  x _ {i} $
$  ( 1 \leq  i \leq  n) $
vary independently of each other over either the whole set of residue classes modulo  $  p $(
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  $  y  ^ {2} \equiv f( x) $(
$   \mathop{\rm mod}  p $) 
on a complete residue system modulo the prime number  $  p $
and the Riemann hypothesis for  $  \zeta $-
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  $  N _ {p} $
of solutions of the congruence  $  y  ^ {2} \equiv f( x) $(
$   \mathop{\rm mod}  p $), 
where the polynomial  $  f( x) = x  ^ {n} + a _ {1} x  ^ {n-} 1 + \dots + a _ {n} $
is not the square of another polynomial modulo  $  p $, 
the estimate

$$ 
| N _ {p} - p |  \leq   2 \left [ n- 
\frac{1}{2}
 \right ] p  ^ {1/2}
$$

is correct (here  $  [ x] $
is the integer part of the number  $  x $).

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

$$ 
y  ^ {2}  \equiv  x  ^ {3} + ax + b  (  \mathop{\rm mod}  p).
$$

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

$$ 
| N _ {q} - q |  \leq   c( f  ) q  ^ {1/2}
$$

for the number  $  N _ {q} $
of solutions of the equation  $  f( x, y) = 0 $
in elements of the field  $  F _ {q} $, 
consisting of  $  q = p  ^ {r} $
elements, where  $  f( x, y) $
is an absolutely-irreducible polynomial with coefficients from  $  F _ {q} $. 
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  $  n $
variables are less widely studied. The following theorem can be used here as a general result. Let  $  f( x _ {1} \dots x _ {n} ) $
be an absolutely-irreducible polynomial with integer coefficients. Then for the number  $  N _ {p} $
of solutions of the congruence

$$ 
f( x _ {1} \dots x _ {n} )  \equiv  0  (  \mathop{\rm mod}  p),\ \ 
n \geq  2,
$$

the estimate

$$ 
| N _ {p} - p  ^ {n-} 1 |  \leq   c( f  ) p  ^ {n-} 1- 1/2
$$

holds, where the constant  $  c( f  ) $
does not depend on  $  p $. 
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  $  f ( x , y ) $
over  $  F _ {q} $
is absolutely irreducible if it is still irreducible over the algebraic closure  $  \overline{F}\; _ {q} $
of  $  F _ {q} $. 
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>