Definition:Modulo Division
Jump to navigation
Jump to search
Definition
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.
Divisor
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$.
Polynomials
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.
Examples
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.
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$