유클리드 호제법(최대공약수, 최소공배수)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

일반적인 GCD(최대공약수), LCD(최소공배수) 구하는 방법

유클리드 호제법(Euclidean Algorithm)

두 양의 정수 a,b (a>b)에 대하여 a=bq+r(0≤r<b)라 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다.

=>    gcd(a, b)=gcd(b, r)

r=0이라면, a,b의 최대공약수는 b가 된다.

 

 

(증명)

 

gcd(a,b) = k      a=nk      b=mk

a=bq+r

nk=mkq+r

r=(n-mq)k

 

m과 n-mq 서로소라면 k는 최대공약수 (공통인수가 있다면 k는 최대공약수가 아님)

 

(귀류법) 가정 [ m과 n-mq 서로소가 아니다. ]

m = xG    n-mg = yG

n-(xG)q = yG

n = (xq+y)G

 

n과 m은 서로소임, but "G"라는 공통인자 존재

n = (xq+y)"G"    m = x"G"

∴ m과 n-mq는 서로소이다.

 

a = nk    b = mk    r=(n-mq)k

gcd(a,b) = gcd(b,r) = k

 

 

 

:D