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

Addition/subtraction rule

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