## Congruence relation

For a positive integer $$n$$ two integers $$a$$ and $$b$$ are said to be congruent modulo $$n$$ if the remainders of $$a / n$$ and $$b / n$$ are the same, that is written as

$\begin{equation}\label{congruent-modulo} a \equiv b \pmod n \end{equation}$

it can also be proven that $$n \mid a - b$$, let $$a = xn + s$$ and $$b = yn + t$$ where $$x, y, s, t$$ are integers, if the remainders of $$a/n$$ and $$b/n$$ are the same then $$t = s$$

\begin{align*} s &= a - xn \\ s &= b - yn \end{align*}

Which means that

$a - xn = b - yn$

Reordering the equation

$\begin{equation}\label{congruent-relation-proof} a - b = n(x - y) \end{equation}$

Since $$x$$ and $$y$$ are integers then $$x - y$$ is also an integer which means that $$a - b$$ is a multiple of $$n$$ thus $$n \mid a - b$$

### Properties

1. Reflexive: $$a \equiv a \pmod n$$ since $$a - a = 0$$ is a multiple of any $$n$$
2. Symetric: $$a \equiv b \pmod n \Rightarrow b \equiv a \pmod n$$ (the same as multiplying \eqref{congruent-relation-proof} by $$-1$$)
3. Transitive: if $$a \equiv b \pmod n$$ and $$b \equiv c \pmod n$$ then $$a \equiv c \pmod n$$

### Rules

Let $$a, b, c, d$$ are integers and $$n$$ is a positive integer such that

\begin{align*} a &\equiv b \pmod n \\ c &\equiv d \pmod n \end{align*}

The following rules apply

$a \pm c \equiv b \pm d \pmod n$

proof: let $$a - c = nk$$ and $$b - d = nl$$, adding both equations $$(a + b) - (c + d) = n(k + l)$$ which is the same as $$a + b \equiv c + d \pmod n$$

#### Multiplication rule

$ac \equiv bd \pmod n$

proof: let

$a = nk + b \\ c = nl + d$

multiplying both equations

\begin{align*} ac &= (nk + b)(nl + d) \\ ac &= n^2kl + nk \cdot d + nl \cdot b + bd \\ ac - bd &= n(nkl + kd + bl) \\ \end{align*}

#### Exponentiation rule

Since $$a^k$$ is just repeated multiplication then

$a^k \equiv b^k \pmod n$

Where $$k$$ is a positive integer

Implementation based on Binary Exponentiation

/**
*
* Computes
*
*    a^k % m
*
* Given the fact that a^k can be computed in O(log k) using
* binary exponentiation
*
* @param {int} a
* @param {int} k
* @param {int} m
* @return {int}
*/
int binary_exponentiation_modulo_m(int a, int k, int m) {
if (k == 0) {
// a^0 = 1
return 1;
}

if (k % 2 == 1) {
return (binary_exponentiation_modulo_m(a, k - 1, m) * a) % m;
} else {
int t = binary_exponentiation_modulo_m(a, k / 2, m);
return (t * t) % m;
}
}


### Modular multiplicative inverse

#### Extended Euclidean Algorithm

The multiplicative inverse of a number $$a$$ is a number which multiplied by $$a$$ yields the multiplicative identity, for modular arithmetic the modular multiplicative inverse is also defined, the modular multiplicative inverse of a number $$a$$ modulo $$m$$ is an integer $$x$$ such that

$\begin{equation}\label{modular-multiplicative-inverse} a \; x \equiv 1 \pmod m \end{equation}$

Such a number exists only if $$a$$ and $$m$$ are coprime, e.g. $$gcd(a, m) = 1$$

The number $$x$$ can be found using the Extended Euclidean Algorithm, by the definition of the congruence relation $$m \mid ax - 1$$

$ax - 1 = mq$

Rearranging

$ax - mq = 1$

This is the exact form of the equation that the Extended Euclidean Algorithm solves where $$gcd(a, m) = 1$$ is already predetermined instead of discovered using the algorithm

/**
* Computes the modular mutiplicative inverse of the number a in the ring
* of integers modulo m
*
*    ax ≡ 1 (mod m)
*
* x only exists if a and m are coprimes
*
* @param {int} a
* @param {int} m
* @param {int} x
* @returns {bool} True if the number a has a modular multiplicative
* inverse, false otherwise
*/
bool modular_multiplicative_inverse(int a, int m, int &x) {
// the value multiplying y is never used
int y;
int gcd = extended_euclidean(a, m, x, y);
if (gcd != 1) {
// a and m are not coprime
return false;
}
// ensure that the value of x is positive
x = (x % m + m) % m;
return true;
}

/**
* Same as above but throws an error if the a and m are not coprimes
*
* @param {int} a
* @param {int} m
* @returns {int} The modular multiplicative inverse of a
*/
int modular_multiplicative_inverse(int a, int m) {
// the value multiplying y is never used
int x, y;
int gcd = extended_euclidean(a, m, x, y);
if (gcd != 1) {
// a and m are not coprime
throw std::invalid_argument("a and m are not relative primes");
}
// ensure that the value of x is positive
x = (x % m + m) % m;
return x;
}


### Euler's Theorem

The modular multiplicative inverse can be also found using Euler's theorem, if $$a$$ is relatively prime to $$n$$ then

$a^{\phi(m)} \equiv 1 \pmod m$

Where $$\phi(n)$$ is Euler's Phi Function

In the special case where $$m$$ is a prime number

$a^{-1} \equiv a^{m - 2} \pmod m$

/**
* Computes the modular multiplicative inverse of a in the ring
* of integers modulo m using Euler's theorem,
* it assumes that m is a prime number and that is relatively prime to a
*
*    a^{-1} ≡ a^{m - 2} (mod m)
*
* @param {int} a
* @param {int} m
* @returns {int} The modular multiplicative inverse of a
*/
int modular_multiplicative_inverse(int a, int m) {
return binary_exponentiation_modulo_m(a, m - 2, m);
}