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