Euclidean Algorithm

Suppose we have non-negative integers $a$ and $b$. The original Euclidean Algorithm computes $\gcd(a,b)$ and looks like this:

Copy
def euclid(a: int, b: int) -> int:
	assert (
		int(a) > 0 and int(b) > 0
	), "Arguments must be positive, non-zero numeric values."

	while b > 0:
		k = a // b
		# subtract multiples of one equation from the other.
		a -= b * k
		a, b = b, a

	return a

Extended Euclidean Algorithm

The extended Euclidean algorithm computes integers $x$ and $y$ such that

We can slightly modify the version of the Euclidean algorithm given above to return more information!

Copy
def extend_euclid(a: int, b: int) -> list[int]:
	assert (
		int(a) > 0 and int(b) > 0
	), "Arguments must be positive, non-zero numeric values."

	# we know that 1 * a + 0 * b = a and 0 * a + 1 * b = b.
	x_arr = [1, 0, int(a)]
	y_arr = [0, 1, int(b)]
	q = -1

Recursive Version

Copy
def euclid(a: int, b: int) -> int:
	"""Recursive Euclidean GCD."""
	return a if b == 0 else euclid(b, a % b)

becomes

Copy
def extend_euclid(a: int, b: int) -> list[int]:
	if not b:
		return [1, 0]
	p = extend_euclid(b, a % b)
	return [p[1], p[0] - (a // b) * p[1]]

The pair will equal the first two returned elements of the array in the iterative version. Looking at this version, we can prove by induction that when $a$ and $b$ are distinct positive integers, the returned pair $(x,y)$ will satisfy $|x|\le \frac{b}{2\gcd(a,b)}$ and $|y|\le \frac{a}{2\gcd(a,b)}$. Furthermore, there can only exist one pair that satisfies these conditions!

Note that if we do all calculations in 64-bit integers, we won't wind up with overflow issues even when $a,b$ are quite large (say, $\approx 2^{60}$).

Application - Modular Inverse

Additionally, it seems that when multiplication / division is involved in this problem, $n^2 < \texttt{LLONG\_MAX}$.

Solution

Application - Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) states that there is a unique solution to a system of simultaneous modular congruences with pairwise coprime moduli. Mathematically, suppose we are given pairwise coprime positive integers $m_1,m_2,\cdots,m_k$, $a_i\in [0, m_i)$, and the system

If we let

then there is exactly one solution for $x$ modulo $M$.

It suffices to solve only the case $k=2$, because for greater $k$ we can just combine pairs of modular congruences until only one remains.

Solution

Application - Linear Diophantine Equation

A Linear Diophantine Equation is an equation of the form

where $a$, $b$ and $c$ are known constants, and we want to find integer values of $x$ and $y$ satisfying the equation. Each number in the equation has to be an integer.

We can solve a Linear Diophantine Equation using the extended Euclidean algorithm, which calculates values $x_g$ and $y_g$ that satisfy the equation:

A Linear Diophantine Equation can be solved if $c$ is divisible by $\gcd(a, b)$, and otherwise it cannot be solved. This observation is derived from Bézout's Identity.

Let's calculate the value of $x$ and $y$ assuming $g = \gcd(a, b)$ divides $c$. Since $g | c$ we can multiply the Bézout equation through by $c / g$, resulting in:

So one solution to $ax + by = c$ is $x_0 = x_g \cdot \frac{c}{g}, \ y_0 = y_g \cdot \frac{c}{g}$.

A solution to the Diophantine equation is never unique, because we can form an infinite number of solutions if we know one solution.

Theorem: If $(x_0, y_0)$ is an integer solution of the Diophantine Equation $ax + by = c$, then all integer solutions to the equation are of the form

where $k$ is any integer.

Proof: We have

here note that the two $k$-terms cancel each other out, so no matter what integer $k$ we choose, our equation results back in $c$.

But we still need to check that we haven't missed any other solutions. So suppose $(x, y)$ is some solution to the equation — any solution at all. Since it agrees with $(x_0, y_0)$ on the right-hand side, we can subtract one from the other:

Here, note that the numbers $\frac{a}{\gcd(a, b)}$ and $\frac{b}{\gcd(a, b)}$ are coprime (i.e., they have no factors left in common except $1$). That means $\frac{b}{\gcd(a, b)}$ has no choice but to divide evenly into $x - x_0$. In other words, $x - x_0$ must be some whole multiple of $\frac{b}{\gcd(a, b)}$; we call that multiple $k$. Once we have fixed the value of $k$, the equation above tells us $y - y_0$ has to equal $-k \frac{a}{\gcd(a, b)}$, proving the theorem.

Problems