유클리드 알고리즘, 확장 유클리드 알고리즘, Modulo Inverse

문제


두개의 자연수를 입력받아 최대공약수와 최소공배수를 출력하면 됩니다.

예를 들어 입력이 다음과 같다면

24 18

다음과 같이 출력하면 됩니다.

6
72



최대공약수(gcd) & 최소공배수(lcm)


gcd(Greatest Common Divisor, 최대공약수)는

두 수가 공통으로 가지고 있는 인수 중 최대값입니다.

예를 들어 gcd(24, 18)을 구한다하면,

\(24 = 2^3 \cdot 3\)이고, \(18 = 2 \cdot 3^2\) 이므로,

공통으로 들어가 있는 인수 중 최댓값은 $2 \cdot 3$인 6입니다.


lcm(Least Common Multiple, 최소공배수)는

두 수의 공배수 가운데 최소값입니다.

예를 들어 lcm(24, 18)을 구한다면,

24의 배수를 나열하면 24, 48, 72, 96, …

18의 배수를 나열하면 18, 36, 54, 72, 90, …

각 숫자의 배수 중 처음 나타나는 같은 수는 72입니다.

즉, 배수 중 같은 수를 공통으로 가지는 배수라 해서 공배수라고 하는데,

그 중 가장 작은 값이 최소공배수 입니다.


lcm(24, 18)은 다음과 같은 방법으로 구할 수도 있습니다.

$24 = 2^3 \cdot 3 = (2 \cdot 3) \cdot 2^2 = gcd(24, 18) \cdot 2^2$
$18 = 2 \cdot 3^2 = (2 \cdot 3) \cdot 3 = gcd(24, 18) \cdot 3$

이므로, 24에는 3만 곱하면, 18에는 $2^2$만 곱하면 lcm이 됩니다.

이 말은 이렇게도 쓸 수 있습니다.

$lcm(24, 18) = gcd(24, 18) \cdot 2^2 \cdot 3$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = gcd(24, 18) \cdot \frac{24}{gcd(24, 18)} \cdot \frac{18}{gcd(24, 18)}$

즉, gcd만 알고있다면 lcm구하는 건 껌이란 이야기입니다.


그럼 프로그래밍으론 gcd를 어떻게 구할까요?

두 수를 다 인수분해한 후, 공통 인수를 구할 수도 있습니다.

하지만 자연수 n을 인수분해 한다하면, 1~n/2까지 for문을 돌려가며

n을 각 수로 나누었을 때, 나누어떨어지는지 확인해야합니다.

n%1==0인지, n%2==0인지, n%3==0인지…

하나하나 비교를 해봐야 하므로 n%(n/2)==0 까지 비교한다 했을때

복잡도는 $O(n)$이 됩니다. 더 빨리 구하는 방법을 알아보겠습니다.



유클리드 호제법


유클리드 호제법은 다음 이론을 이용합니다.

두 자연수 A, B (A > B)가 있고, A를 B로 나눴을 때 나머지를 r이라 하면,
gcd(A, B) = gcd(B, r) 이다.

예를 들면, 두 자연수가 240과 46이라고 하겠습니다.

240을 46로 나눴을 때 나머지는 10입니다. 이때,

gcd(240, 46) = gcd(46, 10) 이라는 말입니다.

실제로 계산을 해봐도 둘 다 gcd는 2로 같습니다.

간단하게 증명 후 넘어가겠습니다.

A, B는 A > B 인 정수입니다. $gcd(A, B) = G$ 라고 두겠습니다. 그럼

$A = aG, B = bG$,   a와 b는 서로소인 정수

라고 할 수 있습니다. 또한 A를 B로 나눈 몫을 q, 나머지를 r이라 하면

$A = qB + r$

입니다. 이 식을 r에 대해서 정리하면

$r = A - qB = aG - qbG = (a-qb)G$

라고 쓸 수 있습니다. 지금 증명하려고 하는건 gcd(B, r)이 G라는 것입니다.
$B = bG$
$r = (a-qb)G$
이므로, $b$와 $(a-qb)$가 서로소이면 gcd(B, r)은 G가 됩니다.

$b$와 $(a-qb)$가 서로소가 아니라고 가정해보겠습니다. 그러면 공통 인수가 있을테고, 이 공통인수를 k라고 하면, 어떤 정수 s와 t에 대해서 다음과 같이 쓸 수 있습니다.

$b = sk$
$a - qb = tk$

이때 두번째 식을 a에 대해서 정리하면

$a = tk + qb = tk + qsk = (t+qs)k$

즉, $a$도 인수로 $k$를 갖고있다고 나오는데 이는 두번째 줄에 a와 b는 서로소라는 가정에 어긋납니다.
즉, $b$와 $(a-qb)$가 서로소가 아니라는 가정은 틀린 것이고, 즉 서로소가 됩니다.
즉, $B$와 $r$은 공통인수가 $G$밖에 없으므로, $gcd(B, r) = G$ 입니다.
즉, $gcd(A, B) = gcd(B, r)$ 입니다.


이를 좀 더 진행시켜보면, 이번엔 두 자연수를 46과 10이라 하겠습니다.

46을 10으로 나눴을 때 나머지는 6입니다. 이때,

gcd(46, 10) = gcd(10, 6) 이 됩니다.

이런 방식으로 계속 진행해나가면 결국

gcd(240, 46) = gcd(46, 10) = gcd(10, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0)

이 됩니다. 참고로 모든 수는 0의 약수입니다. $0 = 2 \cdot 0$ 이므로 2도 0의 약수라고 생각할 수 있습니다.

즉, gcd(2, 0) = 2 가 되서 최대공약수가 2라고 구할 수 있습니다.

보통은 gcd(2, 0)까지는 안가고, gcd(4, 2)까지 진행한 후,

4%2 = 0 이므로, 최대공약수는 2 라고 구합니다.


복잡도(Time Complexity)


최악의 상황일때를 가정합니다.

n > m 일 때, gcd(n, m)을 구하는 상황입니다.

$gcd(n, m) = gcd(m, n\%m) = gcd(n\%m, m\%(n\%m))$

입니다. 즉, 두번의 연산을 해보니 각 단계에서 두개의 수 중,

최댓값이 n에서 n%m 이 되었습니다.


n > m 이므로, n을 m으로 나눌 수 있고, 그때의 몫을 q라 하면,

$n = qm + n\%m$

n > m 이므로, q > 1 입니다. 즉,

$q \cdot m \ge m \tag i$

그리고 나머지인 n%m은 당연히 m보다 작겠죠. 즉,

$m > n\%m \tag {ii}$

(i)와 (ii) 식을 합치면 다음과 같습니다.

$qm > n\%m$

이 식의 양변에 n%m을 더하면,

$qm + n\%m > 2(n\%m)$

$\Rightarrow n > 2(n\%m)$

$\Rightarrow \frac{n}{2} > n\%m$

즉, 두번의 연산만에 최댓값이 $n$에서 $\frac{n}{2}$보다 작아지게 되었죠.

엄밀히 따지면 n%m은 $\frac{n}{2}$보다 작지만,

최악의 상황(n이 매우 크고, 다음 계산의 최댓값이 최대한 적게 줄어든 상황)을 가정하면

$n \% m \approx \frac{n}{2}$

즉, 다시 생각해서 두번의 연산만에 최대값이 $n$에서 $\frac{n}{2}$가 된 것입니다.


이제 k번째 연산만에 이 유클리드 알고리즘이 끝났다고 가정해보겠습니다.

마지막 연산 때, 두개의 수 중 최대값은 얼마가 될지는 모르니 z라고 하겠습니다.

그럼 다음과 같은 식이 성립합니다.

$n (\frac{1}{2})^{\frac{k}{2}} = z$

$\Rightarrow (\frac{1}{2})^{\frac{k}{2}} = \frac{z}{n}$

양변에 $log_{\frac{1}{2}}$를 씌어주면

$\frac{k}{2} = log_{\frac{1}{2}} \frac{z}{n}$

$\Rightarrow \frac{k}{2} = log_2 \frac{n}{z}$

$\Rightarrow k = 2log_2 \frac{n}{z}$

여기서 z는 n에 비해 매우 작은 수 이므로, 복잡도 계산에서는 무시해줘도 됩니다.

즉, 복잡도는 $O(log_2 n)$이 됩니다.


사실, 더 정확한 복잡도를 구하는 방식도 존재합니다.

허나 그 방식은 피보나치 수열에 황금비율까지 이용하여 다소 복잡합니다.

하지만, 위의 worst 케이스에서의 복잡도만으로도 gcd를 구할 때,

소인수 분해($O(n)$)로 구할 때 보다 유클리드 알고리즘을 사용하는게 더 효율적임을 알 수 있습니다.


코드


import java.util.Scanner;

public class Main {
	public static void main(String[] ar){
		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();
		
		int gcd = calcGCD(n1, n2);
		int n1Factor = n1/gcd;
		int n2Factor = n2/gcd;
		int lcm = n1Factor*n2Factor*gcd;
		
		System.out.println(gcd);
		System.out.println(lcm);
	}
	public static int calcGCD(int n1, int n2){
		int max = n1;
		int min = n2;
		if(n2>n1){
			max = n2;
			min = n1;
		}
		
		if(n1%n2==0) return n2;
		else return calcGCD(n2, n1%n2);
	}
}



확장 유클리드 알고리즘


위에서 설명한 유클리드 알고리즘을 확장한 것입니다.

일단 확장 유클리드 알고리즘을 적용하기 위해선 베주 항등식을 알아야합니다.

베주 항등식을 간단히 말하면 다음과 같습니다.

a와 b가 정수이고 둘중 적어도 하나는 0이 아닐때,
$ax+by=d$에서 d가 gcd(a, b)의 배수이면 x, y는 항상 정수해를 갖는다

왜 위의 명제가 맞는지 알고 써야 하니 먼저 증명을 하겠습니다.

x, y가 정수일 때, $m = ax+by>0$을 만족하는 집합 S가 있다고 가정하면,

\(S = \{m \mid m = ax+by>0, x \in \Bbb Z, y \in \Bbb Z \}\)

a, x, b, y 모두 정수이기 때문에 S는 자연수의 부분집합입니다.
(x, y) = (1, 0)또는 (-1, 0)이면 m=|a|이므로, |a|는 S의 원소입니다.
(x, y) = (0, 1)또는 (0, -1)이면 m=|b|이므로, |b|는 S의 원소입니다.
d를 S의 원소 중 가장 작은 값이라 하겠습니다.
그럼 $d$도 S의 원소이기 때문에, 어떤 정수 $k, l$에 대해 다음과 같습니다.

$d = ak + bl$

이제 보여주고 싶은 건, S의 모든 원소가 $d$의 배수라는 겁니다.
S에서 임의의 원소 $x$를 뽑아 살펴봅니다.
$x$도 S의 원소이기 때문에, 어떤 정수 $u, v$에 대해 다음과 같습니다.

$x = au + bv$

원소 $x$를 뽑아 $d$로 나눠주면, $x \ge d$ 이므로, 다음과 같이 쓸 수 있습니다.

$x = qd + r, \;\;0 \le r \lt d$

이때 $x$가 $d$의 배수가 아니라고 가정한다면, 일단 $0 \lt r \lt d$입니다.
위의 식을 $r$에 대해서 정리하면,

$r = qd - x = q(ak+bl) - (au+bv) = (qk-u)a + (ql-v)b \in S$

$(qk-u)$와 $(ql-v)$ 모두 정수이므로, $r$도 $S$의 원소라고 볼 수 있는데,
이때 $0 \lt r \lt d$와 $d$가 S에서 가장 작은 원소라는 것이 모순이 됩니다.
즉, $x$가 $d$의 배수가 아니라는 명제는 거짓이 되고,
결국 S의 모든 원소는 $d$의 배수가 됩니다.
그런데 아까 $|a|$와 $|b|$가 모두 S의 원소라 했으므로, $a$와 $b$는 모두 $d$의 배수입니다.
즉, $d$는 $a$와 $b$의 공약수입니다. $gcd(a, b) = G$라 한다면
$d$는 $G$의 약수가 됩니다.
$gcd(a, b) = G$이므로, 서로소인 $A, G$에 대해 다음과 같이 표현할 수 있습니다.

$a = AG, b = BG$

$d$에 위의 식을 대입하면,

$d = ak + bl = (AG)k + (BG)l = (Ak+Bl)G$

즉, $d$는 $G$의 배수가 됩니다.
정리하면 $d$는 $gcd(a, b)$의 약수이자 배수이므로,

$d = gcd(a, b)$

입니다.


다시 확장 유클리드로 돌아가면,

확장 유클리드는 두 정수 A, B가 주어졌을 때, 베주 항등식인

$Ax + By = gcd(A, B)$

에서 gcd(A, B)를 구하고 이때 정수해 (x, y)를 동시에 구하는 알고리즘입니다.

기본 원리는 유클리드 호제법으로 gcd를 구하는 것과 같습니다.


예를 들어 gcd(102, 46)를 구해보겠습니다.

$102 = 46 \cdot 2 + 10$
$\Rightarrow 10 = 102 \cdot 1 + 46 \cdot (-2)$

다음에는 gcd(46, 10)를 계산해줘야겟죠.

$46 = 10 \cdot 4 + 6$
$\Rightarrow 6 = 46 \cdot 1 + 10 \cdot (-4)$
$\;\;\;\;\;\;\; = 46 \cdot 1 + (102 \cdot 1 + 46 \cdot (-2)) \cdot (-4)$
$\;\;\;\;\;\;\; = 102 \cdot (1 \cdot (-4)) + 46 \cdot (1 + (-2)\cdot(-4))$
$\;\;\;\;\;\;\; = 102 \cdot (-4) + 46 \cdot 9$

다음에는 gcd(10, 6)를 계산해줍니다.

$10 = 6 \cdot 1 + 4$
$\Rightarrow 4 = 10 \cdot 1 + 6 \cdot(-1)$
$\;\;\;\;\;\;\; = (102 \cdot 1 + 46 \cdot (-2)) \cdot 1 + (102 \cdot (-4) + 46 \cdot 9) \cdot (-1)$
$\;\;\;\;\;\;\; = 102 \cdot 1 + 46 \cdot (-2) + 102 \cdot ((-4)\cdot(-1)) + 46\cdot(9 \cdot (-1))$
$\;\;\;\;\;\;\; = 102 \cdot (1 + ((-4)\cdot(-1))) + 46((-2) + 9(-1))$
$\;\;\;\;\;\;\; = 102 \cdot 5 + 46 \cdot (-11)$

다음에는 gcd(6, 4)를 계산해줍니다.

$6 = 4 \cdot 1 + 2$
$\Rightarrow 2 = 6 \cdot 1 + 4 \cdot (-1)$
$\;\;\;\;\;\;\; = (102 \cdot (-4) + 46 \cdot 9) \cdot1 + (102 \cdot 5 + 46 \cdot (-11)) \cdot (-1)$
$\;\;\;\;\;\;\; = 102 \cdot ((-4) \cdot 1 + 5\cdot(-1)) + 46(9\cdot1 + (-11) \cdot (-1))$
$\;\;\;\;\;\;\; = 102 \cdot (-9) + 46 \cdot(20)$

다음 gcd(4, 2)를 계산해보면

$4 = 2 \cdot 2$

라서 나머지가 0이죠

즉, 아까 gcd(6, 4) 계산했을 때 나온 식인

$2 = 102 \cdot (-9) + 46 \cdot 20$

이 정답인 식입니다. 즉, gcd(102, 46) = 2 이고,

$102x + 46y = 2$

의 정수해는 (x, y) = (-9, 20) 입니다.


이제 이 과정을 코딩 해봐야합니다.

각 과정에서 나머지에 대해 정리한 식을 살펴보겠습니다.

처음 두 식은 다음과 같습니다.

$10 = 102 \cdot 1 + 46 \cdot (-2)$
$6\;\; = 102 \cdot (-4) + 46 \cdot 9$

이 두 식을 이렇게 표현해보겠습니다.

$r_1 = 102 \cdot s_1 + 46 \cdot t_1$
$r_2 = 102 \cdot s_2 + 46 \cdot t_2$

참고로 $r_1$이 10이고, $r_2$가 6입니다.

그 다음 식을 살펴보면

$4 = 102 \cdot (1 + ((-4)\cdot(-1))) + 46((-2) + 9(-1))$

이를 문자식으로 표현을 해보면

$(r_1\%r_2) = 102 \cdot(s_1 - s_2 \cdot (r_1/r_2)) + 46(t_1 - t_2 \cdot (r_1/r_2))$

지금은 (1, 2, 3)번 식의 관계를 표현했지만,

(2, 3, 4)번 식의 관계도 똑같습니다.

즉, 피보나치와 비슷하게 n번째 식을 알려면 (n-1)번째와 (n-2)번째 식을 알아야합니다.

그러면 1번째, 2번째 식은 초기값으로 정해줘야겠죠.

도출한 점화식와 첫번째 식을 같이 놓고 보면

$(r_1\%r_2) = 102 \cdot(s_1 - s_2 \cdot (r_1/r_2)) + 46(t_1 - t_2 \cdot (r_1/r_2))$

$10 = 102 \cdot 1 + 46 \cdot (-2)$
$\;\;\;\; = 102 \cdot (1 - 0 \cdot (2)) + 46 \cdot(0 - 1 \cdot (2))$

즉, 초기값을 (s1, s2) = (1, 0) , (t1, t2) = (0, 1)으로 잡고 쭉 계산하면 됩니다.


코드

import java.util.Scanner;

public class Main {
	public static void main(String[] ar){
		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();
		
		int gcd = calcGCD(n1, n2);
		int n1Factor = n1/gcd;
		int n2Factor = n2/gcd;
		int lcm = n1Factor*n2Factor*gcd;
		
		System.out.println(gcd);
		System.out.println(lcm);
	}
	
	public static int calcGCD(int n1, int n2){
		int max = Math.max(n1, n2);
		int min = Math.min(n1, n2);
		int[] r = {max, min};
		int[] s = {1, 0};
		int[] t = {0, 1};
		int q = r[0]/r[1];
		int remainder = r[0]%r[1];
		
		while(remainder>0){
			q = r[0]/r[1];
			
			r[0] = r[1];
			r[1] = remainder;
			int tempS = s[0];
			s[0] = s[1];
			s[1] = tempS-s[1]*q;
			int tempT = t[0];
			t[0] = t[1];
			t[1] = tempT-t[1]*q;
			
			remainder = r[0]%r[1];
		}
		
		return r[1];
	}
}


Recursive 확장 유클리드 알고리즘


확장 유클리드의 원리와 과정은 위에서 설명한 바와 똑같습니다.

다만, Recursive를 이용한 다른 점화식으로 구현하는 걸 설명하고자 합니다.

우리는 계속 gcd(a, b) = gcd(b, a%b)를 사용하고 있습니다.

이 두 식을 다음과 같이 나타낼 수 있습니다.

$ax+by = gcd(a, b) \tag i$
$bx’+(a\%b)y’ = gcd(b, a\%b) \tag {ii} $

참고로 처음 식은 맨 처음에 베주 항등식입니다.

여기서 a%b는 다음과 같이 쓸 수 있습니다.

$a\%b = a - (a/b)b \tag {iii}$

(iii)을 (ii)에 대입하면

$bx’+(a - (a/b)b)y’ = ay’ + b(x’-(a/b)y’) = gcd(b, a\%b)$

근데, gcd(b, a%b) = gcd(a, b) 이므로,

$gcd(b, a\%b) = ay’ + b(x’-(a/b)y’) = ax+by = gcd(a, b)$

즉, x = y’, y = x’-(a/b)y’ 가 됩니다.


예를 들어 위에서 썻던 예를 그대로 쓰면, gcd(102, 46)을 구하는 과정입니다.

gcd(102, 46) = gcd(46, 10) = gcd(10, 4) = gcd(4, 2)

마지막에 끝나는 지점이 gcd(4, 2).

즉, 첫번째 숫자가 두번째 숫자로 나누어 떨어질 때 입니다.

이때 gcd는 두번째 숫자인 2가 됩니다. 즉, gcd(4, 2) = 2

이때의 식을 이렇게 세웁니다.

$gcd(4, 2) = 2 = 4 \cdot 0 + 2 \cdot 1$

즉, 위의 식이

$gcd(b, a\%b) = bx’+(a\%b)y’$

이게 되는 겁니다. x’ = 0, y’ = 1 이죠.

여기서 바로 앞 과정인 gcd(10, 4)를 구해보면

$gcd(10, 4) = 10x + 4y$ 이고,

아까 구한 x = y’, y = x’-(a/b)y’ 점화식을 그대로 넣으면

$gcd(10, 4) = 10 \cdot 1 + 4 \cdot (0-2\cdot1)$
$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 10 \cdot 1 + 4 \cdot (-2)$

즉, 유클리드 알고리즘의 마지막까지 갔다가, 마지막에서 기본값을

(x, y) = (0, 1)로 준 다음 다시 거꾸로 숫자를 맞춰가며

처음 지점인 gcd(102, 46) = 102x + 46y 의 (x, y)까지 맞춰가는 형태입니다.


코드

import java.util.Scanner;

public class Main {
	static int x, y, gcd, temp;
	public static void main(String[] ar){
		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();
		calcGCD(n1, n2);
		
		int n1Factor = n1/gcd;
		int n2Factor = n2/gcd;
		int lcm = n1Factor*n2Factor*gcd;
		System.out.println(gcd);
		System.out.println(lcm);
	}
	public static void calcGCD(int n1, int n2){
		if(n1%n2>0){
			calcGCD(n2, n1%n2);
			temp = y;
			y = x - (n1/n2)*y;
			x = temp;
		}else{
			x = 0;
			y = 1;
			gcd = n2;
		}
	}
}



Modulo Inverse


위에서 설명한 확장 유클리드 알고리즘은 Modulo Inverse를 구하는데 사용할 수 있습니다.

먼저 Modulo Inverse를 설명하자면,

평소에 우리가 사용하는 숫자 체계에서 사용하는 Inverse는 다음과 같습니다.

$a^{-1} = \frac{1}{a}$


하지만 Modulo라는 세계에서는 조금 다릅니다.

일단 Modulo를 설명하자면,

$5 \equiv 11 \pmod 3$

입니다. 5를 3으로 나눈 나머지와 11을 3으로 나눈 나머지가 같으므로 위와 같이 식을 쓸 수 있습니다.


다른 식을 봐보자면

$Ax \equiv 1 \pmod p$

위식은 Ax%p = 1%p 를 의미하는데요,

이때 x를 p에 대한 A의 Modulo Inverse라고 부릅니다.

즉, A에 대해서 봤을 때,

평소에 사용하는 Inverse가 A에 곱해서 1이 나오게 하는 숫자라면,

Modulo Inverse는 A에 곱해서 p로 나눴을 때 나머지가 1이 나오게 하는 숫자(정수)입니다.


숫자로 예를 들면, 다음과 같은 식이 있다고 가정해보겠습니다.

$7x \equiv 1 \pmod 3$

여기서 x는 $\frac{1}{7}$ 이어도 됩니다. 1%3 = 1 이니까요.

하지만 modulo inverse는 정수여야 합니다.

어떤 수를 곱해야 3으로 나눴을 때 1이 나오는지 알려면

1부터 3 이전 숫자까지 직접 다 넣어봐야합니다.

여기선 1, 2만 넣어보면 되죠.

x가 1이여야 7x = 7이 되서 3으로 나눴을 때 나머지가 1이 됩니다.

즉, 3에 대한 7의 Modulo Inverse는 1 입니다.


Modulo Inverse의 특징을 하나 살펴보자면,

$Ax \equiv 1 \pmod P \tag i$

에서 P에 대한 A의 Modulo Inverse는 A와 P가 서로소 일때만 존재합니다.

간단하게 증명하자면,

만약 A와 P가 서로소가 아니고, 이때 $gcd(A, P) = G$ 라고 한다면,
서로소인 두 정수 $a, p$에 대해서 다음과 같이 나타낼 수 있습니다.

$A = aG, \;\;P = pG \tag {ii}$

그리고, $Ax$를 $P$로 나눴을 때 몫을 $q$라고 한다면, 위의 모듈러 식은 다음과 같이 쓸 수 있습니다.

$Ax = qP + 1 \tag {iii}$

(iii)번 식에 (ii)식을 대입하여 정리하면

$aGx = qpG + 1$
$\Rightarrow (ax-qp)G = 1$
$\Rightarrow ax-qp = \frac{1}{G}$

좌변의 $a, x, q, p$ 모두 정수이므로, $ax-qp$도 정수입니다.
우변도 정수가 되려면 $G$가 1이여야만 하고, 이는 $a, p$가 서로소가 아니라는 가정에 모순입니다.
즉, $A$와 $P$가 서로소일때만 Modulo Inverse가 존재합니다.


이 방법으로 Modulo Inverse를 구한다면, 즉,

$Ax \equiv 1 \pmod p$

에서 p에 대한 A의 Modulo Inverse를 구한다면,

x에 1~(p-1)까지 대입해봐야 합니다. 복잡도는 $O(p)$가 되겠죠.

하지만 확장 유클리드 알고리즘을 이용해 Modulo Inverse를 구하면,

이때 복잡도는 worst 케이스 일때 $O(log_2 A)$ 입니다.


A와 p가 서로소라고 하면, 위의 식은 다음과 같이 쓸 수 있습니다.

$Ax = 1 + py$
$\Rightarrow Ax - py = 1$

y는 음수여도 상관없으므로, -를 +로 바꾸면

$Ax + py = 1$

베주 항등식이 나왔고, 이제 정수해 (x, y)를 확장 유클리드 알고리즘으로 구할 수 있습니다.

그리고 이 항등식에 mod p를 취하면,

$Ax \equiv 1 \pmod p$

즉, 유클리드 알고리즘으로 구한 정수해 (x, y)에서 x가 A의 Modulo Inverse가 되는 것입니다.