Definition:Modulo Division

From ProofWiki
Jump to navigation Jump to search


Let $m \in \Z$ be an integer.

Let $\Z_m$ be the set of integers modulo $m$:

$\Z_m = \set {0, 1, \ldots, m - 1}$

The operation of division modulo $m$ is defined on $\Z_m$ as:

$a \div_m b$ equals the integer $q \in \Z_m$ such that $b \times_m q \equiv a \pmod m$

and is possible only if $q$ is unique modulo $m$.

This happens if and only if $a$ and $m$ are coprime.


For all $a, b \in \Z_m$, let $a \div_m b$ denote the operation of division modulo $m$:

$a \div_m b$ equals the integer $q \in \Z_m$ such that $b \times_m q \equiv a \pmod m$

The integers $b$ and $q$ are divisors of $a$ modulo $m$.


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$


$m \in \Z$ is an integer
$\equiv$ means that the respective coefficients are congruent modulo $m$

provided such a polynomial exists.


Arbitrary Example $1$

$7 \div_m 2 = 8 \pmod 9$

Arbitrary Example $2$

$1 \div_m 3 \equiv 6 \pmod {17}$

Arbitrary Example $3$

$4 \div_m 5 \equiv 8 \pmod {12}$

Also see

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