# Category:Modular Division

Modular division is a division operation performed in modular arithmetic. Specifically, given two integers a and b and a modulo m, the result of the modular division of a by b is a number z such that:

$z * b \equiv a \pmod{m}.$

For example:

$2 / 3 \equiv 6 \pmod{8}.$

since

$6 * 3 = 18 \equiv 2 \pmod{8}.$

Unlike the other three arithmetic operators, the result of a division may not always exist. For example: 1 / 2(mod 8) does not exist, since there is no integer z such that: $z * 2 \equiv 1 \pmod{8}$.

A necessary and sufficient condition for the result to exist is that the GCD (greatest common divisor) of b and m divides a:

gcd(b,m) | a

In the above example, gcd(2,8) = 2, and 1 is not a multiple of 2, so the division is not defined.

Unlike the other three arithmetic operators, the result of a division is not always unique. For example:

$2 / 6 \equiv 3 \pmod{8}$

but it is also true that:

$2 / 6 \equiv 7 \pmod{8}$

since:

$6 * 7 = 42 \equiv 2 \pmod{8}.$

In general, if:

$z \equiv a / b \pmod{m}$

Then for each integer k:

$z + k * m/gcd(b,m) \equiv a / b \pmod{m}$

Since for each such k:

$b * (z + k * m/gcd(b,m)) \equiv b * z + k * [b/gcd(b,m)] * m \equiv b * z \equiv a \pmod{m}$

The result of the division is unique modulu m/gcd(b,m).

The modular division may be calculated using the Extended Euclidean algorithm. The latter algorithm finds the GCD of two given numbers (in this case: b and m), and additionally calculates numbers x, y such that:

$bx + my = \gcd(b,m)\,$

The result of the division can be calculated if and only if a is a multiple of gcd(b,m), i.e. there exists an integer q such that:

a = q * gcd(b,m)

In this case we can multiple the previous equation by q, and get:

bqx + mqy = q * gcd(b,m) = a

Therefore. by the definition of modulus:

$bqx \equiv a \pmod{m}.$

so qx is the result of the division.

hijacker
hijacker
hijacker
hijacker

This category currently contains no pages or media.