# 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  and J.L. Lagrange . E. Artin  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  for the case of the elliptic congruences

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

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

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 .

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.

How to Cite This Entry:
Congruence modulo a prime number. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Congruence_modulo_a_prime_number&oldid=46463
This article was adapted from an original article by S.A. Stepanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article