Euclid greatest common measure

1)유클리드의 호제법이란?
유클리드 호제법이란 최대공약수를 쉽게 구하는거예요.
예를들어 A = BQ + r
q 는 quoto 인가? 몫을 저렇게 사용하구요 r 은 나머지구요. ^^
이럴때 A 는 피젯수 , B 는 젯수라고 해요. 자, 이제 본론으로들어갑시다.
유클리드 호제법이란 A 와 B 의 최대공약수는
B 와 r 의 최대공약수와 같다는거예요.
예를들어 94 = 6 x 15 + 4
여기서 94와 6의 최대공약수는 2라는 것이죠.
마찬가지로 6과 4의 최대공약수는 2에요
응용으로 4389 와 2299 의 최대공약수는?
여기서 4389 = 2299 x 1 + 2090
2299 와 2090 의 최대공약수
2299 = 2090 x 1 + 209
2090 과 209의 최대공약수는 209 가 되겠네요 ㅋ

2)유클리드 호제법의 기본적인 원리
자연수 A , B 에 대하여 A 를 B 로 나누었을 때의 몫을 q ,
나머지를 r 이라 하자.
A , B 의 최대공약수를 x 라 하면 A = a'x 15 = 3 x 5 이고
최대공약수가 5일때 a'란 3이되겟죠.
B = b'x ( a' , b' 는 *서로소 { 이유는 최대공약수로 곱해졋으니 남은 곱해
지는수들은 더이상 나누어 지지 않아야겟죠} )
*relatively prime : 1 이외에 공약수를 갖지 않는 두 자연수를 말한다.
r = (a' - b'q)x 이유는 A = BQ + R 에서 a'x = (b'x)q + r 이고
r 은 a'x - b'xq = (a' - b'q ) x
따라서 A , B 의 최대공약수 x 는 B와 r 의 공약수다.
B 와 r 의 공약수인 이유는 아시겟죠?
r = ( a' -b'q)x 이고 B = b'x 잖아요 여기서 공통으로 x 가 들어가있네요.
그런데 a' , b ' 이 서로소이면 b' 와 (a'-b'q) 의 최대공약수는 1이므로
x 는 B 와 r 의 최대공약수이다.
따라서 . a,b 의 최대공약수는 b 와 r 의 최대공약수이다

출처 : 네이버지식인