Extended Euclidean Algorithm

C++

Copy
ll euclid(ll a, ll b) {
	while (b > 0) {
		ll k = a / b;
		a -= k * b;
		swap(a, b);
	}
	return a;
}

Java

Copy
static long euclid(long a, long b) {
	while (b > 0) {
		long k = a / b;
		a -= k * b;

		long temp = b;
		b = a;
		a = temp;
	}
	return a;
}

Python

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

C++

Copy
array<ll, 3> extend_euclid(ll a, ll b) {
	// we know that (1 * a) + (0 * b) = a and (0 * a) + (1 * b) = b
	array<ll, 3> x = {1, 0, a};
	array<ll, 3> y = {0, 1, b};

	// run extended Euclidean algo
	while (y[2] > 0) {
		// keep subtracting multiple of one equation from the other
		ll k = x[2] / y[2];
		for (int i = 0; i < 3; i++) { x[i] -= k * y[i]; }
		swap(x, y);
	}
	return x;  // x[0] * a + x[1] * b = x[2], x[2] = gcd(a, b)
}

Java

Copy
static long[] extendEuclid(long a, long b) {
	// we know that 1 * a + 0 * b = a and 0 * a + 1 * b = b
	long[] x = {1, 0, a};
	long[] y = {0, 1, b};

	// run extended Euclidean algo
	while (y[2] > 0) {
		// keep subtracting multiple of one equation from the other
		long k = x[2] / y[2];
		for (int i = 0; i < 3; i++) { x[i] -= k * y[i]; }

Python

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

C++

Copy
ll euclid(ll a, ll b) {
	if (b == 0) { return a; }
	return euclid(b, a % b);
}

Java

Copy
static long euclid(long a, long b) {
	if (b == 0) { return a; }
	return euclid(b, a % b);
}

Python

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

C++

Copy
pl extend_euclid(ll a, ll b) {  // returns {x,y}
	if (b == 0) { return {1, 0}; }
	pl p = extend_euclid(b, a % b);
	return {p.s, p.f - a / b * p.s};
}

Java

Copy
static long[] extendEuclid(long a, long b) {  // returns {x,y}
	if (b == 0) { return new long[] {1, 0}; }
	long[] p = extendEuclid(b, a % b);
	return new long[] {p[1], p[0] - a / b * p[1]};
}

Python

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]]

C++

Copy
ll inv_general(ll a, ll b) {
	array<ll, 3> x = extend_euclid(a, b);
	assert(x[2] == 1);  // gcd must be 1
	return x[0] + (x[0] < 0) * b;
}

Java

Copy
static long invGeneral(long a, long b) {
	long[] x = extendEuclid(a, b);
	assert (x[2] == 1);  // gcd must be 1
	return x[0] + (x[0] < 0 ? 1 : 0) * b;
}

Python

Copy
def inv_general(a: int, b: int) -> int:
	"""Returns the modular inverse of two positive, non-zero integer values."""
	arr = extend_euclid(a, b)
	assert arr[2] == 1, "GCD must be 1."
	return arr[0] + (arr[0] < 0) * b