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:
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: .
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:
but it is also true that:
In general, if:
Then for each integer k:
Since for each such k:
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:
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:
so qx is the result of the division.
This category currently contains no pages or media.