유클리드 호제법

CS/알고리즘

HWAN JJ 2022. 2. 16. 20:32

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를

ko.wikipedia.org

정의

2개의 자연수 또는 정수의 최대 공약수를 구하는 알고리즘의 하나이다.

호제법이란 말의 뜻은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수을 얻는 알고리즘을 나타낸다.

설명

두 정수 또는 자연수 A, B가 있을 때, A와 B 사이의 최대 공약수는 B와 A를 B로 나눈 나머지 사이의 최대 공약수와 같다.

다시 말하자면, A와 B 사이의 최대 공약수를 GCD(A, B)라고 했을 때, GCD(A, B) = GCD(B, A%B)이다. (A>B)

증명

A=BQ+R (0≤ R < B) 을 만족하는 유일한 정수 Q, R이 존재한다. (A, B, Q, R이 각각 정수이기 때문에)

위에서 말한 GCD(A, B)를 K라고 하고, A = K*a, B = K*b라고 하자. 그러면 a, b는 서로소이다.

1. A = BQ + R

2. K*a = K*b*Q + R

위에 보는 것처럼 1 번식을 2 번식으로 치환 가능하고, 2 번식의 좌측 변이 K의 배수이기 때문에,

R 또한, 자명하게 K의 배수이다. => K|R

이제, R = K*p라고 하자,

만약 GCD(b, p) = K` > 1이라고 하고, b = K` * b`, p = K` * p`으로 두면,

1. A = BQ + R

2. K*a = K*b*Q + K*p

3. Ka = (K*K`) b`Q + (K*K`) p`

4. a = K` * (b`Q + p`)

으로 1 번식으로부터 4 번식을 유추할 수 있고, 이를 통해 다시 a가 K`의 배수임을 알 수 있다.

이는 K`|a 그리고 K`|b 가 되어 a와 b가 서로소라는 것에 대해 모순이다.

그에 따라, GCD(b, p)는 1을 초과하지 않는 자연수이므로, GCD(b, p) = K` = 1이다.

=> b, q 역시 서로소이고, 이에 따라 GCD(Kb, Kp) = GCD(B, R) = K이다.

즉, GCD(A, B) = GCD(B, R) = K 이다.

코드

GCD(A, B) = GCD(B, A% B)을 이용하면, 재귀적으로 코드를 작성하는 것이 편하다.

- 재귀 함수의 종료 조건은?

더 이상 계산할 필요가 없을 때, B|A가 성립하는 경우, B가 최대 공약수가 된다.

만약, A와 B가 서로소라면, B가 1이 되고 나서야, B|A가 성립할 것이다.

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

연습문제