유클리드 알고리즘

유클리드 알리고즘

---

유클리드 알고리즘은 최대공약수를 효율적으로 구하는 알고리즘입니다. 

최대공약수란?

두 개 이상의 자연수가 주어졌을 때 공통된 약수중 가장 큰 약수를 최대 공약수라고 합니다. 

예시 : 32와 24의 최대공약수 구하기

• 32의 약수 = {1, 2, 3, 4 ,6, 8, 12, 24}
• 24의 약수 = {1, 2, 4, 8, 16, 32} 

32와 24의 공약수는 {1, 2, 4, 8}이고 이 중 가장 큰 약수인 8이 최대 공약수 입니다. 

최대 공약수인 8의 약수는 {1, 2, 4, 8}입니다. 근데 이 약수들은 두 수의 공약수들과 같죠? 그러므로 최대공약수를 알면 최대 공약수를 통해 두 수의 공약수들 또한 알 수 있습니다. 

유클리드 알고리즘이란?

일반적으로 두 수 A, B가 주어졌을 때 A = B * q + r  (A : 제수, B : 피제수, q : 몫, r : 나머지) 이라고 할 때 GCD(A, B) = GCD(B, r) = 최대공약수 G, 즉 A와 B의 최대 공약수는 B와 r의 최대공약수와 같다는 것입니다.

알고리즘 과정

• A = 0 이면 GCD(0, B) = B이므로 GCD(A, B) = B임을 알 수 있습니다.
• B = 0 이면 GCD(A, 0) = A이므로 GCD(A, B) = A임을 알 수 있습니다.
• A = B*q+r로 나타낼 수 있고 GCD(A, B) =GCD(B, R)임을 이용하여 GCD(B, R)을 찾아 나갑니다.

32와 24의 최대공약수를 유클리드 호제법을 통해 구해보겠습니다.

GCD(32, 24) 

• A= 32
• B =24
• R = 32 - 24*1 = 8

GCD(24, 8)

• A = 24
• B = 8
• R = 24- 8*3 =0 

GCD(8, 0) 

• A= 8
• B= 0 
• GCD(8, 0) = 8 (B가 0이므로)

따라서 GCD(32, 24) = GCD(24, 8) = GCD(8, 0) = 8이 됩니다.

유클리드 알고리즘 증명 2가지 

증명 1

 유클리드 호제법은 다음의 3가지 성질을 이용합니다.

•   GCD(A, 0) = A
•   GCD(B, 0) = B
•   A = B*q + r (B ≠ 0, 0≤ r ≤ b-1) 일 때 GCD(A, B) = GCD(B, r) = 최대공약수 G

이 세가지 성질을 증명하면 유클리드 호제법이 정확한 결과를 도출한다는 것을 증명할 수 있겠죠?

• GCD(A, 0) = A

우선 A의 약수중 가장 큰 정수는 A입니다. 또한 모든 정수 N에대해서 N*0 =0이므로 A도 0의 약수가 될 수 있습니다.         

따라서 A와 0 의 최대공약수는 A가 됩니다.

• GCD(B, 0) =B 

위에 1번에서 증명한 것과 같은 내용이므로 B와 0의 최대공약수는 B가 됩니다.

• GCD(A,B)= GCD(B,r)= 최대공약수 G

이를 증명하기 앞서 GCD(A, B) = GCD(B, A-B)임을 먼저 증명해보겠습니다. 

우선 A-B를 C라고 부르겠습니다. 

GCD(A, B)는 A와 B의 최대공약수 이므로 A를 나누어 떨어지게 합니다. 그러므로 A는 GCD(A, B)의 배수입니다. 그러면  X*GCD(A,B) = A를 만족하는 어떤 정수 X가 존재하겠죠? 

또한 GCD(A, B)는 B도 나누어 떨어지게 하니까 B도 GCD(A, B)의 배수입니다. Y*GCD(A, B) =B를 만족하는 어떤 정수 Y도 존재할 것입니다.

앞에서 A-B = C라고 했습니다.

X*GCD(A, B) - Y*GCD(A, B) = C

→ (X-Y) * GCD(A, B) = C 

따라서 GCD(A, B)는 C를 나누어 떨어지게 합니다.

이번에는 GCD(B, C)가 A를 나누어 떨어지게 한다는 것을 증명해보겠습니다. GCD(B, C)는 B를 나누어 떨어지게 하므로 B는 GCD(B, C)의 배수입니다. 따라서 X * GCD(B, C) =B를 만족하는 어떤 정수 X가 있을 것입니다. 또한 GCD(B, C)는 C를 나누어 떨어지게 하므로 Y * GCD(B, C)= C를 만족하는 어떤 정수 Y가 있을 것입니다. 

A-B=C 이므로 B+C = A입니다.

X*GCD(B, C) + Y*GCD(B, C) = A

→ (X+Y)*GCD(B, C) =A 

 따라서 GCD(B, C)는 A를 나누어 떨어지게 합니다.

그럼 이제 GCD(A, B) = GCD(A, A-B)임을 증명해 보이겠습니다. 위 과정을통해 GCD(A, B)는 B와 C를 나누어떨어지게 함을 알 수 있습니다. 따라서 GCD(A, B)는 당연히 B와 C의 공약수이겠죠? GCD(B, C)는 B와 C의 최대공약수 입니다. GCD(A, B)는 B와 C의 공약수 중 하나이므로  GCD(A, B)는 GCD(B, C)보다 작거나 같아야합니다. 

GCD(B, C)도 위 과정을통해 B와 A를 나누어 떨어지게함을 알 수 있었습니다. 따라서 GCD(B, C)는 A와 B의 공약수가 됩니다. GCD(A, B)는 A와 B의 최대공약수 이므로 GCD(B, C)는 GCD(A, B)보다 작거나 같아야합니다. 

GCD(B, C)  ≤  GCD(A, B) 이고 GCD(A, B)  ≤  GCD(B, C)이므로 

GCD(A, B) = GCD(B, C) = GCD(B, A-B)가 됩니다.

마지막으로 GCD(A, B)= GCD(B, r)이라는것을 증명해보겠습니다. 나눗셈은 뺄셈의 연속이라는것을 생각해보면 이해하기 쉬우실 것 같습니다. 

우리는 위 증명들을 통해 GCD(A, B) = GCD(B, A-B)라는것을 증명했습니다.

GCD(A, B) = GCD(B, A-B)를 반복해보면 GCD(A, B) = GCD(B, A-B) = GCD(B, A-2B) = GCD(B, A-3B) .... = GCD(B, A-B*q)가 됩니다.

A = B*q + r이므로 A-B*q 는 r입니다. 그러므로 GCD(A, B) = GCD(B, R)이 됩니다.

따라서 GCD(A, B) = GCD(B, r)이 성립됩니다.

이로써 증명1번이 끝났습니다.

증명 2.

GCD(A, B) = G일 때,

A = aG

B = bG

따라서 a와 b는 서로소입니다. 서로소는 두 수의 공약수가 1인 것을 의미합니다. 따라서 서로소가 아니라면 a와 b사이에 다른 공약수가 있다는 의미이므로 G가 최대공약수가 될 수 없겠죠. 

유클리드 알고리즘에서는 GCD(A, B) = GCD(B, r) = 최대공약수 G가 성립한다고 했습니다. 그럼 우리는 GCD(B, r) = 최대공약수임을 증명하면 GCD(A, B) = GCD(B, r)이 성립함을 증명할 수 있겠습니다 

식을 정리해보면

r = A - B*q = Ga-Gbq = G(a-bq) 이므로 

• B =Gb 
• r = G(a-bq)

여기서 G가 최대공약수임을 증명하면 됩니다. 그럼 귀류법을 통해 G가 최대공약수가 아니라고 가정해보겠습니다. G가 최대공약수가 아니려면 b와 a-bq가 서로소가 아니어야 합니다. 따라서 a-bq와 b가 1이 아닌 공약수 m을 가진다고 해보겠습니다. 

b = mx 

a-bq= my 

이 식을 연립하면 a-mxq = my, 즉  a= m(xq+y)가 되겠네요. 

따라서 

• b = mx 
• a = m(xq+y)

정리된 식을 보시면 m이라는 a와 b에 공통된 약수 m이 존재합니다. 위에서 a와 b가 서로소라고 했는데 공약수 m이 존재하므로 a와 b는 서로소가 아니게 됩니다. 따라서 a-bq와 b는 서로소가 아니다라는 가정은 거짓이 되므로 a-bq와 b는 서로소이고 b와 r의 최대공약수는 G입니다.

 

증명이 굉장히 길었는데 사실 이를 코드로 구현하는것은 매우 간단합니다.

재귀로 구현한 유클리드 알고리즘

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