CS/알고리즘
[알고리즘] 유클리드 호제법 파헤치기
일 월
2023. 1. 25. 22:42
이 글은 위키백과의 내용을 인용·참고했습니다.
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란
ko.wikipedia.org
유클리드 호제법
호제법이란 두 수가 서로(互)를 나누어(除)서 원하는 수를 얻는 알고리즘을 뜻한다.
유클리드 호제법은 두 수의 최대공약수를 구하는 방법으로 잘 알려져있는데, 2개의 자연수(또는 *정식) a, b에 대해서(단, a>b), a와 b의 최대공약수는, b와 r (a를 b로 나눈 나머지)의 최대공약수와 같다. b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
* 정식 [整式] : 문자에 대하여 덧셈, 뺄셈, 곱셈만의 연산을 사용하여 얻어지는 대수식. 식을 정리했을 때 분모에 문자가 없고, 근호(根號) 속에도 문자가 포함되어 있지 않은 유리식을 이른다.
예시
78696과 19332의 최대공약수는 유클리드 호제법을 이용해 다음과 같이 36이라는 것을 알 수 있다.
78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0
증명
위키백과의 '정수에 대한 유클리드 호제법 증명' 부분을 더 세세하며 적어보며 이해해보려고 노력했다.
정리 (증명하고자 하는 것)
a, b가 정수이고, a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
증명
두 정수 a ≥ b인 a, b에서, a는 a를 b로 나눴을 때의 몫과 나머지인 q와 r로 나타낼 수 있다.
a = bq + r ---- (1)
(b가 최소일 때, q가 1, r이 0이므로) q는 자연수이고, 0 ≤ r < b이다.
a와 b의 최대공약수를 d라고 하면, a, b를 다음과 같이 나타낼 수 있다.
a = dα ---- (2)
b = dβ ---- (3)
여기서 α, β는 서로소(최대공약수가 1인 수)이다.
(2) 식, (3) 식을 (1) 식에 대입하면, 아래와 같은 식이 된다.
dα = dβq + r ---- (4)
r = d(α - βq) 이므로, r = dρ와 같이 나타낼 수 있다.
dα = dβq + dρ ---- (5)
b와 r의 최대공약수가 d가 아니라, dd`라고 가정해보면(d`≠ 1),
b = dd`β`, β = d`β`, r = dd`ρ`, ρ = d`ρ`로 나타낼 수 있다.
dα = dβq + dρ = dd`β`q + dd`ρ` = dd`(β`q + ρ`) ---- (6)
(6)식의 모든 변을 d로 나누면, 다음 식으로 표현된다.
α = d`(β`q + ρ`) ---- (7)
α는 d`의 배수이므로, α와 β의 최대공약수는 1이 아니다.
따라서 α, β가 서로소가 아니므로, b와 r의 최대공약수가 d가 아니라는 가정이 성립하지 않음을 알 수 있다.
이는 b와 r의 최대공약수가 d로, a와 b의 최대공약수와 같음을 의미한다. (귀류법 이용)