# 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 $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, 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

$$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 [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 $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 [6] for the case of the elliptic congruences

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

A. Weil [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 [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 [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.

#### References

 [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 $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. [a1].