Category:Modular Division

From LiteratePrograms
Jump to: navigation, search

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}.


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}


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.


This category currently contains no pages or media.