Congruence modulo a double modulus

$( p, f( x))$, congruence relative to a double modulus $( p, f ( x))$

A relation between integral polynomials $a( x)$ and $b( x)$ of the form

$$a( x) - b( x) = f( x) g( x) + ph( x),$$

where $p$ is a prime number, while $f( x) = x ^ {n} + \dots + \alpha _ {n}$, $g( x)$ and $h( x)$ are polynomials with integer rational coefficients. In other words, the polynomials $a( x)$ and $b( x)$ with rational coefficients are called congruent modulo the double modulus $( p, f( x))$ if the difference $a( x) - b( x)$ between them is divisible by $f( x)$ modulo $p$. In order to denote the congruence of $a( x)$ and $b( x)$ modulo the double modulus $( p, f( x))$, the symbol

$$a( x) \equiv b( x) ( \mathop{\rm mod} ( p, f( x)))$$

is used. This symbol, as well as the actual concept of a congruence modulo a double modulus, was introduced by R. Dedekind.

A congruence modulo a double modulus is an equivalence relation on the set of all integral polynomials and, consequently, divides this set into non-intersecting classes, called residue classes modulo the double modulus $( p, f( x))$. Since every polynomial $a( x)$ is congruent modulo the double modulus $( p, f( x))$ to one and only one polynomial of the form

$$\beta _ {1} x ^ {n-1} + \beta _ {2} x ^ {n-2} + \dots + \beta _ {n} ,$$

where $\beta _ {1} \dots \beta _ {n}$ run independently of each other through a complete residue system modulo $p$, there are exactly $p ^ {n}$ residue classes modulo $( p, f ( x))$.

Congruences modulo a double modulus can be added, subtracted and multiplied in the same way as normal congruences. These operations induce similar operations on the residue classes modulo a double modulus, thus transforming the set of residue classes into a commutative ring.

The ring of residue classes modulo $( p, f( x))$ is the quotient ring of the ring of polynomials $K _ {p} [ x]$ with coefficients from a finite prime field $K _ {p}$ by the ideal $( \overline{f}\; ( x))$ generated by the polynomial $\overline{f}\; ( x)$, obtained from $f( x)$ by reduction modulo $p$. In particular, if $f( x)$ is irreducible modulo $p$, then $( \overline{f}\; ( x))$ is a maximal ideal in $K _ {p} [ x]$, and $K _ {p} [ x]/( \overline{f}\; ( x))$ is a field consisting of $p ^ {n}$ elements (an extension of degree n of the prime field $K _ {p}$).

If $f( x)$ is irreducible modulo $p$, then for congruences modulo a double modulus, the analogue of the Fermat little theorem holds:

$$a( x) ^ {p ^ {n} } \equiv a( x) ( \mathop{\rm mod} ( p, f( x))),$$

as does the Lagrange theorem: The congruence

$$z ^ {m} + a _ {1} ( x) z ^ {m-1} + \dots + a _ {m} ( x) \equiv 0 ( \mathop{\rm mod} ( p, f( x))),$$

the coefficients of which are integral polynomials, has not more than $m$ incongruent solutions modulo $( p, f( x))$. From these theorems it is possible to deduce that

$$x ^ {p ^ {n} } - x = \prod _ { d\mid } n \Phi _ {d} ( x) ( \mathop{\rm mod} p),$$

where $\Phi _ {d} ( x)$ is the product of all possible different, normalized (i.e. with leading coefficient 1), irreducible polynomials modulo $p$ of degree $d$. If the number of different, normalized, irreducible polynomials modulo $p$ of degree $n$ is denoted by $( n)$, then

$$(n) = \frac{1}{n} \sum_{d\mid n} \mu(d) p^{n/d} ,$$

where $\mu ( d)$ is the Möbius function and, in particular, $( n) > 0$ for any natural number $n$. Consequently there exists, for any integer $n > 0$, a finite field $K _ {q}$ consisting of $p ^ {n}$ elements that is an extension of degree $n$ of the residue field $K _ {p}$ modulo the prime number $p$.

References

[1]	B.A. Venkov, "Elementary number theory" , Wolters-Noordhoff (1970) (Translated from Russian)
[a1]	G.H. Hardy, E.M. Wright, "An introduction to the theory of numbers" , Oxford Univ. Press (1979) pp. Chapts. 5; 7; 8