여러분들께 문제를 하나 내겠습니다.

당신에게는 x개의 사과와 21x^2-12x+1개의 바나나가 있습니다.

이때, 당신은 최대한 많은 사람들에게 공평하게 사과와 바나나를 나누어 줄때,

최대 몇명에게 나누어 줄 수 있을까요?

(한번 생각해보세요, 기사를 다 읽으시고 답을 아시면 댓글로 적어주세요)

우리는 이 문제를 풀기 위해, 최대공약수를 사용합니다..

그런데 여러분은 최대공약수가 무엇인지 아시나요?

최대공약수란 공통인 약수중 가장 큰 수를 의미합니다.

이때 두 수 a,b 의 최대공약수를 gcd(a,b)라고 하는데요,

예를들어 6과 8의 최대공약수인 gcd(6,8)는 2겠죠?

그런데 6,8처럼 작은 수들의 최대공약수는 간단할 수 있겠지만

예를 들어 3142342341234126와 3412342342342의 최대공약수를

구하는 것은 어렵고 시간도 많이 들 것입니다.

그렇다면 최대공약수를 쉽고 빠르게 구하는 방법은 없을까요?

우리는 두수의 최대공약수를 빠르게 구하기 위해서

"유클리드 호제법"이라는 것을 사용합니다.

유클리드 호제법의 핵심은

a,b의 최대공약수는 

a와 b를 a로 나눈 나머지의 최대공약수와 같다는 것인데요,

이를 증명할 수 있습니다.

gcd(a,b)=d라 하고 gcd(a,b-a)=e라 하면

a=dx, b=dy, (x,y)=1

그러면, d|d(x-y)=a-b, d|b이므로 d는 a-b, b의 공약수 ->d|e

한편, e|a-b+b=a, e|b이므로 e는 a, b의 공약수->e|d

따라서 d=e

위 증명에 의해

a,b의 최대공약수는 a,b-a의 최대공약수와 같고

이를 반복하면 gcd(a,b)=gcd(a,b를 a로 나눈 나머지)임을 알 수 있습니다.

이제 우리는 최대공약수를 쉽고 빠르게 구할 수 있는 무기를 가지고 있습니다.

그렇다면 본격적으로 다항식들의 최대공약수를 구해볼까요?

한번 x+1과 x^2+2x+2의 최대공약수를 구해볼까요?

x^2+2x+2를 x+1로 나눈 나머지는

x^2+2x+2=(x+1)^2+1임으로

1입니다.

따라서 gcd(x+1,x^2+2x+2)=gcd(x+1,1)=1 입니다.

다시 말해 x값이 무엇이든

두수는 서로소라는 것이죠(서로소는 최대공약수가 1인

두 수를 말합니다)

이제 어떤 두 수나 두 방정식이 나왔을때,

최대공약수를 구하는 방법을 아시겠죠?