유클리드 호제법에 대한 나의 이해

유클리드 알고리즘=큰숫자들의 최대공약수를 빠르게 구하기 위해 만들어짐

 

설명에 들어가기 전에 알아야 할것

1. 0의 약수는 모든수이다

 0/모든수=0...0이다 따라서 모든수가 0의 약수이다

 

2. 두수 A,B의 최대공약수가 G일때 A=Ga, B=Gb이다 이때 a,b는 서로소다

만약에 a,b가 서로소가 아니라고 가정을 해보자

a와 b에 공통된 인수 m이생겼다 그럴경우 최대공약수 G는 더이상 최대공약수라고 할수없어진다

따라서 최대공약수 G가 있을때 a,b는 서로소이다

 

gcd는 최대공약수를 뜻다는 영어 약자이다

gcd함수는 gcd내부에 있는 두수의 최대공약수를 구한다

예를들어 gcd(15,10)=5이다

 

gcd의 성질에 대해 알아보자A/B=B*Q+r일떄(Q몫, r나머지)gcd(A,B)=gcd(B,r)이다

 

이유

A=B*Q+r을 변형해보자

Ga=GbQ+r,

G(a-bQ)=r이다

gcd(A,B)=G이다

gcd(Gb, G(a-bQ))이다 

이때 b,와 a-bQ가 서로소일까?

서로소가 아니라고 먼저 가정해보았다

b=lm, a-bQ=ln이다

이때 A=GlmQ+Gln B=Glm

최소공약수는 G라는 원래 설정이 모순이 되어 성립하지않는다 따라서 거짓이다

따라서

gcd(Gb, G(a-bQ))의 최소공약수는 G

즉 gcd(A,B)=gcd(B,r)이다

 

유클리드 알고리즘 사용법

0<=r<B<A 이기때문에 점점 진행될수록 gcd안의 숫자는 작아진다

그렇게 작아지다가 결국 최종적으로는

(b,r)이기때문에

(어떤수, 0)의 형태가 나올것이다

앞서 말한것처럼 0의 약수는 모든수이다 따라서 

gcd(어떤수,0)=어떤수