[Number Theory] Euclidean Algorithm & Inverse Element

With the inverse element, we can get the value of modulo in a division, such as $k =(a / b) %m$. To generate a inverse element, we should know the euclidean algorithm.

Euclidean Algorithm

The euclidean algorithm is a method for computing greatest common divisor (GCD) of two integers.
The algorithm can be described as this:

gcd(a, b) = gcd(b, a \% b) 

Proof:

Suppose $c = gcd(a, b)$ and $a > b$.
Then we can write a equation.

a = xb + m

Because the gcd of $a$ and $b$ is $c$, so we can replace the $a$ and $b$ with $k1 * c$ and $k2 * c$. After replaced $a$ and $b$, it seems like we also can replace $m$ with $k3 * c$. So the equation will like this:

k1 * c = x * k2 * c + k3 * c

So $m$ and $b$ have the same gcd. Therefore the value of the $gcd(a, b)$
is the same with the value of $gcd(b, a % b)$

So for this, we can get a $gcd(a, b)$ quickly with such as c++ language.

The code will like this:

int gcd(int a, int b) {
    if(b == 0) return a;
    return gcd(b, a % b);
}

Solve ax + by = gcd(a, b)

We can use the extgcd to get the value of $x$ and $y$.

Suppose we have solved the $x'$ and $y'$ in this equation.

bx' + (a \% b)y' = gcd(a, b)

Then we replace the $a % b$ with $a - (a / b) * b$:

bx' + (a - \frac {a} {b} b)y' = gcd(a, b)

=>

ay' + b(x' - \frac {a} {b} y') = gcd(a, b)

So we can know $x = y'$, and $y = (x' - (a / b)y')$.

When the $b = 0$, we can let $x = 1$ and $y = 0$ to get one result of $x$ and $y$:

a * 1 + b * 0 = a = gcd(a, b)

Code:

int extgcd(int a, int b, int &x, int &y) {
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

Inverse Element

Suppose we have a function:

a * x \equiv b (m)

We want to solve the $x$. If we know the $y$ in $a * y \equiv 1(m)$, then we can solve the $x$ in the before function. We call the $y$ is the inverse element of $a$. If we get the $y$, we can use $x = a^{-1} * a * x = a^{-1} * b$ to get $x$.

The function $a * y \equiv 1(m)$ can be replaced by $a * y - k * m = 1$. It's very clearly that it has no solutions when $gcd(a, m) != 1$. We can solve this function by extgcd.