두 다항식의 GCD가 $1$.

Question

다음 문제를 해결하려고 노력했습니다.

GCD 찾기 $4x^5+7x^3+2x^2+1$ 과 $3x^3+x+1$ 에 $\mathbb{Q}[x]$.

비슷한 문제를보고 친구들과 이야기함으로써 $1$. 그러나 유클리드 알고리즘을 사용하거나 긴 나눗셈을 사용하는 것과 같이 불쾌한 분수를 거치지 않고는 이것을 표시하는 방법을 찾을 수 없습니다. 아니야$1$? 그렇다면 불쾌한 분수 외에 더 간단하고 우아한 방법이 있습니까?

Answer 1

쓰다 $f(x), g(x)$두 다항식에 대해. 둘 다 원시적이므로 Gauss의 기본형에 의해 축소 불가능한 분해$\mathbb{Q}[x]$ 원시 비 환원 다항식으로 구성됩니다. $\mathbb{Z}[x]$. 따라서 그들의 gcd$h(x) = \gcd(f(x), g(x))$정수 계수가 있습니다. 선행 계수 검사$h(x)$ 모닉이어야합니다. 이는 학위를 가질 수 없음을 의미합니다. $3$ (그러면 다음과 같을 것입니다. $g(x)$ 나눌 수없는 $h(x)$ 에 $\mathbb{Z}[x]$), 그래서 $\deg h(x) \le 2$.

이것은 $h(x)$ 가치를 가질 수있다 $1$ 정수 값 $x$ 동일하지 않고 최대 두 번 $1$ (이후 $h(x) - 1$ 기껏해야 $2$뿌리). 그래서 우리가 찾을 수 있다면$3$ 정수 값 $x_1, \dots x_4$ 그런 $\gcd(f(x_i), g(x_i)) = 1$ (이것들은 $\gcd$s 이제 일반 정수), 이것은 $h(x) = 1$.

이제 다음을 계산합니다.

• $\gcd(f(0), g(0)) = \gcd(1, 1) = 1$
• $\gcd(f(-1), g(-1)) = \gcd(-8, -3) = 1$
• $\gcd(f(1), g(1)) = \gcd(14, 5) = 1$

그래서 $h(x) = 1$.

---

두 번째 접근 방식은 $g(x)$이성근 정리를 사용 하고 작업 하는 것은 어렵지 않습니다.$\bmod 2$; 그것은 다음과 같다$h(x) = 1$ 또는 $g(x)$, 그리고 우리는 $h(x) = g(x)$ 위.