정수에 대한 유클리드 호제법

---

a >= b이고 a를 b로 나눈 나머지를 r 이라고 하자

 

유클리드 호제법의 가장 핵심은 다음과 같다.

 

a, b의 최대공약수를 (a, b)

b, r의 최대공약수를 (b ,r) 이라고 하면

(a, b) = (b, r) 이 성립한다.

---

예를 들어,

 

(48, 18)  = (18, 12) = (12 , 6) = (6, 0) = 6 

 

처럼 쓸 수 있다.

 

즉 , 뒤의 자리가 0이 될 때 까지 연산을 진행한다.

---

만약 두 수가 서로소라면

 

(17, 13) = (13, 4) = (4, 1) = (1, 0)  = 1 

 

다음과 같이 나타남을 알 수 있다. 

서로소 또한 결과가 잘 나타남을 알 수 있다.

---

이제 유클리드 호제법을 코드로 나타내면 다음과 같다.

 

def gcd(m, n):

    if m < n :

        m,n = n, m

    if n == 0:

        return m

    if m % n == 0:

        return n

    return gcd(n, m%n)