[일반] 다항식 유클리드 알고리즘 최대공약수 구하는데

[익명(121.153)]

인수분해해서 그다음 진행을 어떻게 하는지 알려줄수 있어?
여기서 바로 최대공약수를 구하는것은 아닌것 같아서

[속상한기태씨(soksanghae)]

그냥 자연수에서처럼 다항식 곱해서 나머지 0 나올때까지 반복하면 됨

[익명(121.153)]

근데 저렇게 하는거 맞아?

[sqrt(222.237)]

정수에서 유클리드 알고리즘 쓸 때 각 수를 소인수분해 하나요? 안 하잖아요. 단순히 나눗셈을 해서 몫과 나머지를 구하죠. 다항식도 마찬가지입니다. 각각을 인수분해할 필요가 없습니다. 차수가 더 큰 애를 보다 작은 애로 나눠서 몫과 나머지를 구해주시면 됩니다. A=QB+R이면 gcd(A,B)=gcd(B,R)

[익명(121.153)]

엥 그럼 저거 잘못푼거네....혹시 저거좀 알려줄수 있어? 난 지금까지 인수분해해서 나온숫자 가지고서 최대 공약수 구하는줄 알고서 저렇게 했는데

[sqrt(222.237)]

저거 말고 x³-3x²+3x-1, x²-1로 할게요. x³-3x²+3x-1=(x-3)(x²-1)+4x-4 x²-1=(1/4)(x+1)(4x-4)+0 따라서 gcd(x³-3x²+3x-1,x²-1)=gcd(x²-1,4x-4)=gcd(4x-4,0)=x-1 두 다항식의 최대공약수는 두 다항식을 동시에 나누어 떨어지게 끔하는 차수가 최대인 다항식을 의미합니다.

[sqrt(222.237)]

따라서 x-1,4x-4,-x+1,(1/4)(x-1) 등 '0이 아닌 유리수(가역원)'의 곱은 무시합니다. x²-1=(x+1)(x-1)=((x+1)/2)(2x-2)이므로 x²-1의 약수로 x+1, x-1이라고 할 수도 있지만 동시에 (x+1)/2, 2x-2라고 할 수도 있는 것과 같은 이치입니다.