유클리드 알고리즘(최대 공약수, 최소 공배수)

Goal

---

유클리드 알고리즘(Euclidean algorithm)이란?

최대 공약수(GCD)를 구하는 알고리즘으로,

두 자연수 또는 두 다항식 사이에서 최대 공약수를 구할 때 사용되는 알고리즘이다.

(유클리드 호제법이라고도 한다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.)

 

성질

• 2개의 자연수(또는 다항식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
• 즉, a와 b의 최대 공약수를 gcd(a, b)라고 하면, gcd(a, b) = gcd(b, r) 이 성립한다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

ex)

gcd(1071, 1029) = gcd(1029, 42) = gcd(42, 21) = gcd(21, 0) = 21

 

증명

$a,b\in {\mathbb  {Z}}$ (정수)이고, $a\geq b$ 일때,

$a=bq+r$ 을 만족하는 유일한 정수 $q , r$이 존재한다. ($0\leq r<b$ )

 

$gcd(a,b) = G $ 일 때, $ a = GA $ , $b = GB $ 이다. (A, B는 서로소)

이를 $a=bq+r$에 대입하면,

$GA = GBq+r$이고, $r = G(A−Bq)$이다. 여기서 G는 b와 r의 공약수임을 알 수 있다.

따라서, B와 (A-Bq)가 서로소임을 증명하면 즉, gcd(B, A-Bq) = 1임을 증명하면,

gcd(b, r) = G 이므로, gcd(a,b) = gcd(b,r) 임을 알 수 있다.

 

$gcd(B, A−Bq) = m $ (단,  $m\neq 1 $) 이라고 하면,

$B = mk$ , $A-Bq = ml$ 이 성립한다. (단, k, l은 서로소)

위 식을 사용하여 A에 대한 식으로 풀어내면 다음과 같이 나타낼 수 있다.

$A = ml+Bq = ml+mkq = m(l+kq)$

즉, m은 A와 B의 공약수임을 알 수 있다. 그런데 A, B는 서로소이므로, m = 1이다.

따라서, gcd(B, A-Bq) = m = 1 즉, 서로소 이므로 gcd(b,r) = G 가 성립한다.

 

결론

gcd(a,b) = gcd(b,r) = G

---

최대 공약수, 최소 공배수 성질

*최대 공약수(GCM, Greatest Common Divisor)

*최소 공배수(LCM, Least Common Multiple)

 

두 정수 A, B의 최대 공약수를 G, 최소 공배수를 L이라고 할때,

• A = Ga, B = Gb (a, b는 서로소)
• L = Gab = AB / G
• GL = AB
• A, B 의 모든 공약수는 G의 약수
• A, B의 모든 공배수는 L의 배수

 

최대 공약수 최소 공배수 코드 구현

int gcd(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}