유클리드 호제법 | GCD, LCM
유클리드 호제법 정리 두 자연수의 최대공약수를 구하는 알고리즘입니다. A ≥ B인 두 자연수 A, B에 대하여 A = qB + r를 만족하는 경우 G(A, B) = G(B, r)를 만족 G함수 : 입력(두 정수), 출력(두 정수의 최대 공약수) GCD : Greatest Common Divisor, 최대 공약수 LCM : Least Common Multiple, 최소 공배수 유클리드 호제법 증명 증명할 것 : G(A, B) = G(B, r) A ≥ B 인 두 정수 A, B에 대해서 최대공약수를 G로 했을 때 다음이 성립합니다. 1. A = Ga 2. B = Gb 결론 1 : a와 b는 서로소이다. a와 b가 서로소가 아닌 경우(공약수로 k(k ≠ 1)를 가지는 경우) A와 B의 최대공약수 Gk가 되므로 ..
2021. 12. 21.