[정수론] - 유클리드 호제법

유클리드 호제법

A = Bq + R

유클리드 호제법 : A와 B의 최대 공약수(Greatest Common Divisor)가 G이면

B와 R의 최대 공약수도 G이다.

 

증명

A = aG

B = bG

로 표현할 수 있고, a와 b는 서로소이다.

 

이 두 식을 위 식에 대입하면

aG = bGq + R

이다.

 

따라서,

R = (a - bq)G

이다.

 

B와 R의 최대 공약수가 G임을 보이기 위해서는 b와 a - bq가 서로소임을 보이면 된다.

 

만약 b와 a - bq가 서로소가 아니라고 가정해보자

b = b'C

a - bq = a'C

 

a - bq에 b = b'C를 대입하면,

a - b'Cq = a'C

a = (b'q + a')C

가 된다.

 

그렇게 되면 a와 b가 C라는 공약수를 갖게 되면서 기존의 서로소라는 가정에 모순되므로 b와 a - bq는 서로소이다.

따라서 B와 R의 최대 공약수는 G이다.

 

위와 같은 유클리드 호제법을 통해 큰 두 수(A, B)를 모듈러 연산을 통해 작은 수로 만들어 최대공약수를 쉽게 구할 수 있다.

최소공배수는 두 수의 곱을 최대 공약수로 나눈 것과 같기 때문에 이 또한 쉽게 구할 수 있다.

알고리즘

def gcd(m,n):
	if m < n:
		m, n = n, m
	if n == 0:
		return m
    if m % n == 0:
		return n
	else:
		return gcd(n, m%n)
        
def lcm(m, n):
	return (m * n) / gcd(m, n)