개발여행의 블로그
[유클리드 호제법] Euclidean algorithm 본문
유클리드 호제법 (유클리드 알고리즘)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다.
* 최대공약수 : GCD(Greatest Common Divisor)
양의 정수 A, B가 존재하고 A가 B보다 크다는 전제하에 A를 B로 나눈 나머지를 r이라고 칭한다.
이때 A와 B의 최대공약수는 B와 r 사이의 최대공약수와 같다.
이것이 유클리드 호제법이다.
그 이유를 살펴보자!
A는 어떤 수 * 최대공약수, B는 어떤 수 * 최대공약수로 나타낼 수 있다.
즉 아래와 같이 나타낼 수 있다.
(최대공약수이기 때문에 더 이상 약수는 존재하지 않아야 하므로 a와 b는 서로소이다.)
여기서 증명해야 할 것은
A와 B의 최대공약수는 G이므로
A를 B로 나눈 나머지가 r이었을 때, B와 r의 최대공약수도 G인지 확인해야 할 것이다.
위에서 A를 B로 나눈 몫은 q, 나머지는 r이라고 나타냈다.
A는 아래와 같이 나타낼 수 있다. A는 몫(q) * B + 나머지(r)이다.
A, B를 최대공약수로 나타냈을 때의 식을 대입해보면
아래와 같이 나타낼 수 있다.
여기서 r과 B 사이의 최대공약수가 여전히 G인 것을 확인할 수 있다.
즉 (a – q·b) 와 b가 서로소임을 보이면 된다.
공통되는 약수가 없으면 r과 B의 최대공약수도 G가 되기 때문이다.
(a – q·b) 와 b가 서로소인 것을 증명하기 위해서
결과를 부정하는 귀류법을 사용한다.
만약 (a – q·b) 와 b가 서로소가 아니라면
a-q·b = xn,
b = yn
으로 나타낼 수 있다.
서로소가 아니기 때문에 공통인 약수 n을 가지고 있을 것이다.
a-q·b = xn
식에서
b에 yn을 대입하면
a-q·yn = xn
즉, a = (yq + x)n으로 정리할 수 있다.
이때, b = yn
b는 여전히 yn이다.
a ((yq + x)n)와 b (yn)는 n이라는 공약수가 존재하게 되므로
a와 b는 서로소가 아니게 된다.
즉, a와 b는 서로소이다라는 전제에 위배된다.
따라서 귀류법을 통해 a와 b가 서로소임을 증명한 것이다.
'개발 > Algorithm' 카테고리의 다른 글
| [알고리즘 javaScript] 숫자 추출 (0) | 2021.11.24 |
|---|---|
| [알고리즘 javaScript] palindrome 팰린드롬:회문 문자열 (0) | 2021.11.24 |
| [leetcode] 859. Buddy Strings solution(문제 풀이) (0) | 2021.08.21 |
| [leetcode] 7. Reverse Integer 문제 풀이 (0) | 2021.08.15 |
| 트리와 이진트리(Tree and Binary Tree) (0) | 2020.05.27 |