Definition:Modulo Division/Polynomials

Definition

Let $\map f x$ and $\map g x$ be integral polynomials.

The operation of polynomial division modulo $m$ is defined as:

$\map f x \div_m \map g x$ equals the integral polynomial $\map h x$ such that:

$\map g x \times_m \map h x \equiv \map f x \pmod m$

where:

$m \in \Z$ is an integer

$\equiv$ means that the respective coefficients are congruent modulo $m$

provided such a polynomial exists.

Divisor

Let $\map f x \div_m \map g x$ denote the operation of polynomial division modulo $m$:

$\map f x \div_m \map g x$ equals the integral polynomial $\map h x$ such that:

$\map g x \times_m \map h x \equiv \map f x \pmod m$

The polynomials $\map g x$ and $\map h x$ are (polynomial) divisors of $\map f x$ modulo $m$.

Examples

Arbitrary Example $1$

Let:

\(\ds \map f x\)

\(=\)

\(\ds x^3 - x^2 - 1\)

\(\ds \map g x\)

\(=\)

\(\ds x + 1\)

Then $\map f x$ divided by $\map g x$ modulo $3$ is:

$x^2 + x - 1$

Arbitrary Example $2$

Let:

\(\ds \map f x\)

\(=\)

\(\ds x^3 - x^2 - 1\)

\(\ds \map g x\)

\(=\)

\(\ds x + 1\)

Then $\map f x$ not divisible by $\map g x$ modulo $11$.

Arbitrary Example $3$

Let:

\(\ds \map f x\)

\(=\)

\(\ds x^3 - x^2 - 1\)

\(\ds \map g x\)

\(=\)

\(\ds x - 5\)

Then $\map f x$ divided by $\map g x$ modulo $11$ is:

$x^2 + 4 x - 2$

Also see

• Results about polynomial division modulo $m$ can be found here.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): division modulo $n$
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): division modulo $n$