Extended Euclidean Algorithm

ax + by = gcd(a,b) 에 대해서 gcd(a,b), x, y 를 구하는 방법

 

a = bq + r 이라고 할 때, q는 a를 b로 나눈 quotient, r는 a를 b로 나눈 remainder 이다.

 

위에 있는 식을 ax + by = gcd(a,b) 를 대입하면 bx' + ry' = gcd 와 같이 변형이 가능하다.

 

따라서 gcd(a, b) = gcd(b, r) 를 얻는다.

 

(a, b) => (b, r) 과정을 반복하면 r = 0 인 경우가 오는데 이 때의 a가 최대공약수 g가 될 것이다.

 

ax + by = gcd(a,b) 에서 gcd(a,b), x, y 를 구하는 코드

pair<ll, pair<ll, ll>> xGCD(ll a, ll b) { // returns {g, {x, y}}, ax+by=g
	if(b==0) return { a,{1,0} };
	pair<ll, pair<ll, ll>> ret=xGCD(b, a%b);
	ll g, x, y;
	g=ret.first;
	tie(x, y)=ret.second;
	return { g,{y,x-(a/b)*y} };
}

이때, tie(x, y)는 ret.second 에서 pair<ll, ll> 로 묶인것의 first, second를 x, y에 넣는다는 것을 의미한다.

 

이를 이용하여 ax = 1(mod n) 즉, a의 inverse 인 x 값을 찾아보도록 한다.

 

일단 ax + ny = 1 임을 이용하여 x, y, gcd(a, n) 을 구한다. 

 

gcd(a, n) 이 1이 아닌 경우 => 역원 x 가 존재하지 않는다.

 

gcd(a, n) 이 1인 경우 => 역원 x 가 존재한다.

 

ax = 1 (mod n) 일때 inverse x를 구하는 코드

 

pair<ll, pair<ll, ll>> xGCD(ll a, ll b) { // returns {g, {x, y}}, ax+by=g
	if(b==0) return { a,{1,0} }; // base case
	pair<ll, pair<ll, ll>> ret=xGCD(b, a%b);
	ll g, x, y;
	g=ret.first;
	tie(x, y)=ret.second;
	return { g,{y,x-(a/b)*y} }; 
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int modular=50;
	for(int i=2; i<50; i++) {
		cout<<i<<"'s inverse is ";
		pair<ll, pair<ll, ll>> res=xGCD(i, modular);
		ll g=res.first, x, y;
		tie(x, y)=res.second;
		if(g==1) cout<<(x<0 ? x+modular: x)<<endl;
		else cout<<"not exist..."<<endl;
	}

	return 0;
}