Extended Euclidean Algorithm

C++

Copy
ll euclid(ll a, ll b) {
	for (;b;swap(a,b)) {
		ll k = a/b;
		a -= k*b;
	}
	return a; // gcd(a,b)
}

Extended Euclidean Algorithm

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

C++

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

C++

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

C++

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

C++

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

int main() {
	FOR(b,1,101) F0R(a,101) if (__gcd(a,b) == 1) {
		ll x = invGeneral(a,b);
		assert((a*x-1)%b == 0);
		assert(0 <= x && x < b);
	}
}