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+\cdots +{\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)(\mathrm{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}+\cdots +{\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 $(\bar{f}(x))$ generated by the polynomial $\bar{f}(x)$, obtained from $f(x)$ by reduction modulo $p$. In particular, if $f(x)$ is irreducible modulo $p$, then $(\bar{f}(x))$ is a maximal ideal in $K_p[x]$, and $K_p[x]/(\bar{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)(\mathrm{mod}(p,f(x))),$$

as does the Lagrange theorem: The congruence

$$z^m+a_1(x)z^{m-1}+\cdots +a_m(x)\equiv 0(\mathrm{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}{\mathrm{\Phi }}_d(x)(\mathrm{mod}p),$$

where ${\mathrm{\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[edit]