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

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

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

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

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

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

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);
}