§ Modular inverse calculation

• Easy way to calculate $a^{-1}$ mod $p$ is to use $a^{p-2}$. We know that $a^{p - 1} \equiv 1$ from Lagrane's theorem, so $a^{p-2} \cdot a \equiv 1$, or $a^{-1} \equiv a^{p-2}$. This can be done fairly quickly with repeated exponentiation.

• Another way to do this is to use extended eucliean division. Suppose $a \not \equiv 0$ (mod p). Then we can find numbers $\alpha, \beta$ such that $a \alpha + p \beta = gcd(a, p) = 1$. If we look at the whole equation (mod $p$), we find that $a \alpha \equiv 1$ (mod $p$), or $\alpha$ is the modular inverse of $a$.

pair<int, int> euc(int x, int y) {
  if (x < y) { return euc(y, x); }
  // x > y
  if (x % y == 0) { return {0, 1}; }
  int a, b; std::tie(a, b) = euc(y, x%y);
  // ay + b(x%y) = gcd(y, x%y) = gcd(x, y)
  // ay + b(x - y(x//y)) = gcd(y, x%y) = gcd(x, y)
  // ay + bx - by(x//y)  = gcd(y, x%y) = gcd(x, y)
  // (a - b(x//y))y + bx = gcd(y, x%y) = gcd(x, y)
  // bx + (a - b(x//y))y = gcd(y, x%y) = gcd(x, y)
  // intuition?
  return {b, a - b*(x/y)};
}