최대공약수 구하기

SeungHyunYoo·2021년 1월 5일
0

최대공약수

아래 코드는 두 수 a, b가 있을 때 a, b의 최대 공약수를 구하는 함수이다.

private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

a와 b의 최대공약수를 구하는데 b와 a를 b로 나눈 나머지를 재귀적으로 이용하고 있다.

이를 이해하기 위해 유클리드 호제법에 대해 알아보자

유클리드 호제법?

두 양의 정수 a, b (a > b)에 대해 a = b*q + r (0 <= r < a) 라 하면,
a, b의 최대공약수는 b,r의 최대 공약수와 같다. 즉, gcd(a,b) = gcd(b,r) 이다.
r=0 이라면 a, b의 최대공약수는 b가 된다.

위의 정의를 이용하면 두 수 a, b가 있을 때 a, b 의 최대공약수는, b와 r 즉 b와 a % b 의 최대공약수가 일치한다는 것을 알 수 있다.

따라서 처음에 소개한 함수는 a, b 대신 b, a % b 값을 재귀적으로 계산하다가 a % b가 0이 될 때의 b 값 즉 최대공약수를 구하는 코드임을 이해할 수 있다.

그렇다면 유클리드 호제법이 왜 성립하게 되는지 증명 해보자

유클리드 호제법의 증명

두 양의 정수 a, b (a > b)에 대해 a = b*q + r (0 <= r < a) 라 하면,
a, b의 최대공약수는 b,r의 최대 공약수와 같다.

임의의 두 수 a, b에 대해 최대공약수 gcd(a, b) = G라고 하면,
적당한 서로소인 정수 A, B에 대해 a=AG,b=BG 가 성립한다.

위의 a = b*q + r 식에 대입하면, AG = BGq + r 이고 r에 대해 정리하면
r = (A - Bq)G 가 된다.

이때, b = BG, r = (A - Bq)G 이므로 B와 (A - Bq)가 서로소 이면
G가 b, r의 최대공약수임을 증명할 수 있다.


B, (A - Bq)가 서로소가 아니라고 가정하면
gcd(B, A - Bq) = m (m != 1)을 만족하는 m이 존재해야 한다.(서로소가 아니므로)

적당한 소로소인 정수 k, l에 대해 B = mk, (A - Bq) = ml이 성립한다.

(A - Bq) = ml을 A에 대해 정리하면 A = Bq + ml 이고, B = mk를 대입하면
A = mk + ml 즉, A = m(k + l)이 된다.

A = m(k + l), B = mk 이므로 m은 A, B의 공약수다.
처음에(bold) 두 정수 A, B는 서로소라고 했으므로 공약수인 m은 1이어야 하므로 m != 1인 조건에 위배되고 모순이 발생한다.

따라서 B, (A-Bq)는 서로소 임을 알 수 있으며
최종적으로 gcd(a, b) == gcd(b, r) (r = a % b) 가 성립한다.


참고

나무위키

0개의 댓글