안녕하세요,,
오늘은 유클리드 호제법입니다.
유클리드 호제법은 지난번과 같이 문자와 집합 기호로 여러분을 혼동시키지 않기 위해 최대한 말로 풀어 설명하도록 하겠습니다.(그래도 이해가 안 갈수 있습니다. 괜찮아요 님만 그런거 아닙니다)
시작해 볼까요?
유클리드 호제법
유클리드 호제법은 a = bq + r 일때 (a,b) = (b,r) 이라는 정리입니다.
시작부터 멘붕이 오네요. 다시 설명하겠습니다.
'a를 b로 나눈 몫이 q, 나머지가 r 일때 a와 b의 최대공약수는 b와 r의 최대공약수와 같다' 라는 뜻이었습니다.
증명합시다.
pf)
먼저 a 와 b의 최대공약수를 d, b와 r의 최대공약수를 e라고 합시다.
i) 그렇다면 d|a, d|b 이므로
d|a-bq, a-bq = r 이므로 d|r
->d는 b와 r의 공약수, e는 b와 r의 최대공약수
∴ d|e (최대공약수의 약수가 공약수이기 때문)
ii) 두번째로 위와 똑같은 방법으로 e에 적용시킬 겁니다.
e|b, e|r => e|bq+r => e|a
-> e는 a, b 의 공약수 / d는 a, b의 최대공약수
∴ e|d
iii) d|e, e|d이므로 d = e 로 증명 끝.
<더 쉽게>
127과 47의 최대공약수를 구하고 싶으면 위와 같이 셋팅을 한 다음에 계산을 하면 됩니다.
파란색 화살표는 |와 | 사이에 있는 두 수를 나누었을 때의 몫이고, 화살표가 가리키는 숫자 옆(| 안에 있는 숫자)는 나머지입니다.
이 나누는 과정을 반복하면 두 수가 서로소 인지를 판별할 수 있습니다.
이번거는 어렵지 않았을 겁니다. '|' 기호만 들어가서 좀 햇갈릴 수 있을 뿐이지 개념은 중 1꺼 밖에 안 씁니다.
그래서! 유클리드 알고리즘도 같이 소개하려고 합니다.
유클리드 알고리즘
유클리드 알고리즘은 유클리드 호제법을 알고리즘화 한 것입니다.
공식으로 나타내면,,
(a,b) = (b,r) = ... = (r',r'')에서 r''이 0이 되는 경우 = (a,b) = r'
어려운거 다 압니다.
쉽게 말하면 아까 한 유클리드 호제법을 0이 될 때 까지 반복한다는 것입니다.
이걸 이용해서 코드를 짤 수 있는데요, 코드는 인터넷 찾아보면 나옵니다(쓰기 귀찮아요)
저의 궁극적인 목표는 정수를 이용해서 코드업 1298번을 푸는 겁니다.
1298번을 푸는 데에는 '확장 유클리드 알고리즘'이 필요한데요..
뭔가 이름이 비슷한 걸 보니 연관성이 있을 것 같고, 실제로 연관성이 있습니다.
이번 글에 그걸 몰아넣기에는 좀 그렇고, 다음 글에 확장 유클리드 알고리즘과 디오판틴 부정방정식을 푸는 방법으로 찾아뵙겠습니다.
안녕히 계세요,,
