# 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:

For example:

since

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:

*g**c**d*(*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:

since:

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***g**c**d*(*b*,*m*)

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

*b**q**x*+*m**q**y*=*q***g**c**d*(*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.*