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

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$

Which means that

Reordering the 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(\mathrm{mod}n)$ since $a-a=0$ is a multiple of any $n$
2. Symetric: $a\equiv b(\mathrm{mod}n)\Rightarrow b\equiv a(\mathrm{mod}n)$ (the same as multiplying $\text{(2)}$ by $-1$)
3. Transitive: if $a\equiv b(\mathrm{mod}n)$ and $b\equiv c(\mathrm{mod}n)$ then $a\equiv c(\mathrm{mod}n)$

Rules

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

The following rules apply

Addition/subtraction rule

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(\mathrm{mod}n)$

Multiplication rule

proof: let

multiplying both equations

Exponentiation rule

Since $a^k$ is just repeated multiplication then

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

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$

Rearranging

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

Where $\varphi (n)$ is Euler’s Phi Function

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

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