# Modular Division (C Plus Plus)

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:

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:

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

## Source

First we copy the implementation from Extended Euclidean algorithm (C Plus Plus):

```<<eea>>=
void eea (int a, int b,
int& gcd, int& x, int& y) {
x=0, y=1;
int u=1, v=0, m, n, q, r;
gcd = b;
while (a!=0) {
q=gcd/a; r=gcd%a;
m=x-u*q; n=y-v*q;
gcd=a; a=r; x=u; y=v; u=m; v=n;
}
}
```

And here is the implementation of modular division:

```<<divide>>=
eea
#include <assert.h>
int divide (int A, int B, int m) {
assert (0 <= A && A<m);
assert (0 <= B && B<m);
int gcd, x, y;
eea (B, m, gcd, x, y);  // x B + y p = gcd(B,p)
if (A%gcd == 0) {
int q = A / gcd;       // x q B + y q p = q gcd = A
return ((x + m)*q) % (m/gcd);   // Return the smallest result possible
} else {
throw "no quotient";
}
}
```

## Tests

The following program calculates all division results for the moduli 6, 7, 8, 9 and 10.

```<<divide.cpp>>=
#include <iostream>
using namespace std;
divide
void assertDivide(int X, int Y, int m, int expected) {
int a = divide(X, Y, m);
if (a!=expected) {
cerr << "ERROR: " << X << " / " << Y << " [mod " << m << "] == " << expected << " but got " << a << endl;
} else {
cout << X << " / " << Y << " [mod " << m << "] == " << expected << endl;
}
}
void assertCycle (int Y, int m) {
for (int Z=1, X=Y; Z<m && X!=0; Z+=1, X=(X+Y)%m) {
assertDivide(X,Y,m,Z);
}
}
void assertCycles(int m) {
for (int Y=1; Y<m; ++Y) {
assertCycle(Y, m);
}
}
int main() {
assertCycles(6);
assertCycles(7);
assertCycles(8);
assertCycles(9);
assertCycles(10);
return 0;
}
```

## Results

```1 / 1 [mod 6] == 1
2 / 1 [mod 6] == 2
3 / 1 [mod 6] == 3
4 / 1 [mod 6] == 4
5 / 1 [mod 6] == 5
2 / 2 [mod 6] == 1
4 / 2 [mod 6] == 2
3 / 3 [mod 6] == 1
4 / 4 [mod 6] == 1
2 / 4 [mod 6] == 2
5 / 5 [mod 6] == 1
4 / 5 [mod 6] == 2
3 / 5 [mod 6] == 3
2 / 5 [mod 6] == 4
1 / 5 [mod 6] == 5
1 / 1 [mod 7] == 1
2 / 1 [mod 7] == 2
3 / 1 [mod 7] == 3
4 / 1 [mod 7] == 4
5 / 1 [mod 7] == 5
6 / 1 [mod 7] == 6
2 / 2 [mod 7] == 1
4 / 2 [mod 7] == 2
6 / 2 [mod 7] == 3
1 / 2 [mod 7] == 4
3 / 2 [mod 7] == 5
5 / 2 [mod 7] == 6
3 / 3 [mod 7] == 1
6 / 3 [mod 7] == 2
2 / 3 [mod 7] == 3
5 / 3 [mod 7] == 4
1 / 3 [mod 7] == 5
4 / 3 [mod 7] == 6
4 / 4 [mod 7] == 1
1 / 4 [mod 7] == 2
5 / 4 [mod 7] == 3
2 / 4 [mod 7] == 4
6 / 4 [mod 7] == 5
3 / 4 [mod 7] == 6
5 / 5 [mod 7] == 1
3 / 5 [mod 7] == 2
1 / 5 [mod 7] == 3
6 / 5 [mod 7] == 4
4 / 5 [mod 7] == 5
2 / 5 [mod 7] == 6
6 / 6 [mod 7] == 1
5 / 6 [mod 7] == 2
4 / 6 [mod 7] == 3
3 / 6 [mod 7] == 4
2 / 6 [mod 7] == 5
1 / 6 [mod 7] == 6
1 / 1 [mod 8] == 1
2 / 1 [mod 8] == 2
3 / 1 [mod 8] == 3
4 / 1 [mod 8] == 4
5 / 1 [mod 8] == 5
6 / 1 [mod 8] == 6
7 / 1 [mod 8] == 7
2 / 2 [mod 8] == 1
4 / 2 [mod 8] == 2
6 / 2 [mod 8] == 3
3 / 3 [mod 8] == 1
6 / 3 [mod 8] == 2
1 / 3 [mod 8] == 3
4 / 3 [mod 8] == 4
7 / 3 [mod 8] == 5
2 / 3 [mod 8] == 6
5 / 3 [mod 8] == 7
4 / 4 [mod 8] == 1
5 / 5 [mod 8] == 1
2 / 5 [mod 8] == 2
7 / 5 [mod 8] == 3
4 / 5 [mod 8] == 4
1 / 5 [mod 8] == 5
6 / 5 [mod 8] == 6
3 / 5 [mod 8] == 7
6 / 6 [mod 8] == 1
4 / 6 [mod 8] == 2
2 / 6 [mod 8] == 3
7 / 7 [mod 8] == 1
6 / 7 [mod 8] == 2
5 / 7 [mod 8] == 3
4 / 7 [mod 8] == 4
3 / 7 [mod 8] == 5
2 / 7 [mod 8] == 6
1 / 7 [mod 8] == 7
1 / 1 [mod 9] == 1
2 / 1 [mod 9] == 2
3 / 1 [mod 9] == 3
4 / 1 [mod 9] == 4
5 / 1 [mod 9] == 5
6 / 1 [mod 9] == 6
7 / 1 [mod 9] == 7
8 / 1 [mod 9] == 8
2 / 2 [mod 9] == 1
4 / 2 [mod 9] == 2
6 / 2 [mod 9] == 3
8 / 2 [mod 9] == 4
1 / 2 [mod 9] == 5
3 / 2 [mod 9] == 6
5 / 2 [mod 9] == 7
7 / 2 [mod 9] == 8
3 / 3 [mod 9] == 1
6 / 3 [mod 9] == 2
4 / 4 [mod 9] == 1
8 / 4 [mod 9] == 2
3 / 4 [mod 9] == 3
7 / 4 [mod 9] == 4
2 / 4 [mod 9] == 5
6 / 4 [mod 9] == 6
1 / 4 [mod 9] == 7
5 / 4 [mod 9] == 8
5 / 5 [mod 9] == 1
1 / 5 [mod 9] == 2
6 / 5 [mod 9] == 3
2 / 5 [mod 9] == 4
7 / 5 [mod 9] == 5
3 / 5 [mod 9] == 6
8 / 5 [mod 9] == 7
4 / 5 [mod 9] == 8
6 / 6 [mod 9] == 1
3 / 6 [mod 9] == 2
7 / 7 [mod 9] == 1
5 / 7 [mod 9] == 2
3 / 7 [mod 9] == 3
1 / 7 [mod 9] == 4
8 / 7 [mod 9] == 5
6 / 7 [mod 9] == 6
4 / 7 [mod 9] == 7
2 / 7 [mod 9] == 8
8 / 8 [mod 9] == 1
7 / 8 [mod 9] == 2
6 / 8 [mod 9] == 3
5 / 8 [mod 9] == 4
4 / 8 [mod 9] == 5
3 / 8 [mod 9] == 6
2 / 8 [mod 9] == 7
1 / 8 [mod 9] == 8
1 / 1 [mod 10] == 1
2 / 1 [mod 10] == 2
3 / 1 [mod 10] == 3
4 / 1 [mod 10] == 4
5 / 1 [mod 10] == 5
6 / 1 [mod 10] == 6
7 / 1 [mod 10] == 7
8 / 1 [mod 10] == 8
9 / 1 [mod 10] == 9
2 / 2 [mod 10] == 1
4 / 2 [mod 10] == 2
6 / 2 [mod 10] == 3
8 / 2 [mod 10] == 4
3 / 3 [mod 10] == 1
6 / 3 [mod 10] == 2
9 / 3 [mod 10] == 3
2 / 3 [mod 10] == 4
5 / 3 [mod 10] == 5
8 / 3 [mod 10] == 6
1 / 3 [mod 10] == 7
4 / 3 [mod 10] == 8
7 / 3 [mod 10] == 9
4 / 4 [mod 10] == 1
8 / 4 [mod 10] == 2
2 / 4 [mod 10] == 3
6 / 4 [mod 10] == 4
5 / 5 [mod 10] == 1
6 / 6 [mod 10] == 1
2 / 6 [mod 10] == 2
8 / 6 [mod 10] == 3
4 / 6 [mod 10] == 4
7 / 7 [mod 10] == 1
4 / 7 [mod 10] == 2
1 / 7 [mod 10] == 3
8 / 7 [mod 10] == 4
5 / 7 [mod 10] == 5
2 / 7 [mod 10] == 6
9 / 7 [mod 10] == 7
6 / 7 [mod 10] == 8
3 / 7 [mod 10] == 9
8 / 8 [mod 10] == 1
6 / 8 [mod 10] == 2
4 / 8 [mod 10] == 3
2 / 8 [mod 10] == 4
9 / 9 [mod 10] == 1
8 / 9 [mod 10] == 2
7 / 9 [mod 10] == 3
6 / 9 [mod 10] == 4
5 / 9 [mod 10] == 5
4 / 9 [mod 10] == 6
3 / 9 [mod 10] == 7
2 / 9 [mod 10] == 8
1 / 9 [mod 10] == 9
```