Polynomial congruence

The polynomial congruence is a term from the mathematical branch of number theory . It is a congruence in which polynomials with integer coefficients occur on both sides . One example is congruence

${\displaystyle x^{4}+2x+1\equiv x^{3}-6x^{2}{\pmod {13}}}$

The normalized representation of such a congruence is

${\displaystyle a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n}x^{n}\equiv 0{\pmod {m}}}$

To get this shape one has to partially subtract the right hand side of a congruence on both sides.

The degree of congruence is the highest index for which is not divisible by . It depends on the module and is not identical to the degree of the corresponding polynomial. However, it is also called the degree of the polynomial modulo . No degree is defined for a congruence where all coefficients are divisible by the module. Degree 1 congruences are linear congruences . ${\displaystyle i}$ ${\displaystyle a_{i}}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$

Two polynomials and are identically congruent modulo if the difference is divisible by . Then you write ${\displaystyle f(x)}$ ${\displaystyle g(x)}$ ${\displaystyle m}$ ${\displaystyle f(x)-g(x)}$ ${\displaystyle m}$

${\displaystyle f(x)\equiv g(x){\pmod {m}}}$

Whole numbers that ${\displaystyle x}$

${\displaystyle f(x)\equiv 0{\pmod {m}}}$

satisfy are called roots or solutions of the polynomial congruence. Together with this solution, all elements of the associated residual class are also solutions. Two roots of the same residue class are not considered to be substantially different and are therefore identified; this corresponds to the transition from to the remainder class ring . If a prime number , then there is a field , and one has the usual theory of polynomials over fields, in particular a polynomial congruence modulo a prime number can have at most as many roots as the degree of congruence. If not a prime number, this statement no longer applies; for example, has the polynomial congruence ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Z} /(m)}$ ${\displaystyle m}$ ${\displaystyle \mathbb {Z} /(m)}$ ${\displaystyle 0\leq x<m}$ ${\displaystyle m}$

${\displaystyle x^{4}-1\equiv 0{\pmod {16}}}$

fourth degree the eight roots 1,3,5,7,9,11,13,15.

swell

• Karl-Heinz Indlekofer : Number theory. Birkhäuser, Stuttgart 1978, ISBN 3-7643-0942-3
• GH Hardy EM Wright: An Introduction to the Theory of Numbers , Oxford University Press (1979), ISBN 0-19-853171-0 , chap. VII: General Properties of Congruences