수학 유클리드 호제법(Euclidean algorithm)

유클리드 호제법에 대해서 알아보겠습니다.

유클리드 호제법을 사용하면, 최대 공약수(Greatest common factor)를 쉽게 구할 수 있습니다.
​

G(a, b) = G(b, r)
여기서 r는 a/b의 나머지
​
1024와 54로 예를 들어보겠습니다.
G(1024, 54) = G(54, 52) = G(52, 2) = G(2, 0) = 2
즉, 1024와 54의 최대 공약수는 2입니다.
​
1024 = 1, 2, 4, 8, 16, 32, 64, 128, ,256, 512, 1024
54 = 1, 2, 3, 6, 9, 18, 27, 54
​
​
증명은 아래와 같습니다.

​
G(a, b)를 a와 b의 최대 공약수로 정의를 내립니다.
​
유클리드 호제법은 a와 b가 정수(Ζ)이고, 조건 a ≥ b, b > r ≥ 0를 만족할 때, a = bq + r가 성립됩니다.
이때, G(a, b) = G(b, r)을 나타내고 있습니다.





















끝.

카테고리: Math