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