확장 유클리드 알고리즘 (Extended Euclidian Algorithm)

확장 유클리드 알고리즘 (Extended Euclidian Algorithm) 이란?

확장 유클리드 알고리즘은 두 정수 a와 b의 최대공약수(GCD) 를 구하는 동시에, 베주 항등식 ax + by = gcd(a, b)을 만족하는 정수 해 x, y (여기서는 s, t)를 찾는 알고리즘입니다. 이를 이용하여 모듈러(%) 연산에 대한 곱셈의 역원을 구할 수 있습니다.

---

기본 공식

각 단계의 값들은 이전 두 단계의 값들을 사용하여 다음과 같이 계산됩니다.

• 몫: $qi=r_{i-2}÷r_{i-1}$ ​
• 나머지: $ri=r_{i-2}(mod(r_{i-1}))$
• s 계수: $si=s_{i-2}-(qi\times s_{i-1})$
• t 계수: $ti=t_{i-2}-(qi\times t_{i-1})$

---

문제: 17x≡1(mod29) 의 해 x 구하기

이는 17 mod 29에 대한 곱셈 역원을 찾는 것과 같습니다.

1. 확장 유클리드 알고리즘

먼저, a=29와 b=17에 대해 확장 유클리드 알고리즘을 실행하여 아래 표를 완성합니다.

• i = 0: 29⋅(1)+17⋅(0)=29

• i = 1: 29⋅(0)+17⋅(1)=17

• i = 2: 29⋅(1)+17⋅(−1)=12

• i = 3: 29⋅(−1)+17⋅(2)=5

• i = 4: 29⋅(3)+17⋅(−5)=2

• i = 5: 29⋅(−7)+17⋅(12)=1 (최대공약수)

• i = 6: (나머지가 0이므로 종료)

단계 (i)	몫 (qi​)	나머지 (ri​)	s	t
0	-	29	1	0
1	-	17	0	1
2	1	12	1	-1
3	1	5	-1	2
4	2	2	3	-5
5	2	1	-7	12
6	2	0	-	-

---

2. 결과 해석 및 역원 찾기

1. GCD 확인: 곱셈 역원은 GCD가 1일 때만 존재합니다. 위 표에서 나머지가 0이 되기 직전의 나머지는 1이므로, 역원이 존재함을 확인할 수 있습니다.

2. 등식 찾기: 나머지가 1인 행(5행)의 값들을 사용하여 베주 항등식을 만듭니다.

   • s=−7, t=12

   • $as+bt=gcd(a,b)$

   • → $29\times (-7)+17\times 12=1$

3. 역원 계산:

   • 우리가 찾으려는 것은 17 mod 29 에 대한 역원입니다.

   • 위 등식에 mod 29 연산을 적용합니다.

   • $(29\times (-7)+17\times 12)(mod29)=1(mod29)$

   • ⬆️ 29×(−7) 항은 29로 나누어 떨어지므로 0이 됩니다.

   • 남은 식은 $17\times 12\equiv 1(mod29)$ 입니다.

결론

위 식에 따라, 17 mod 29에 대한 곱셈 역원은 12입니다.

---

코드

#include <bits/stdc++.h>
using namespace std;
long long n, a;
 
tuple<long long, long long, long long> xgcd(long long a, long long b) {
	if (b == 0) {
		return {a, 1, 0};
	}
 
	long long gcd, prev_x, prev_y;
	tie(gcd, prev_x, prev_y) = xgcd(b, a % b);
 
	return {gcd, prev_y, prev_x - (a / b) * prev_y};
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> n >> a;
 
	cout << n - a << " ";
	long long gcd, x, y;
	tie(gcd, x, y) = xgcd(a, n);
 
	// gcd가 1이 아니면 역원은 존재하지 않음
	if (gcd > 1)
		cout << -1;
	else
		// x가 역원이지만 음수일 수 있으므로 양수로 변환
		cout <<  (x % n + n) % n;
 
	return 0;
}