두 다항식의 GCD 계산

Question

나는 그가 여기 에서 gcd를 찾기 위해 사용한 방법을 알고 싶습니다.$x^{49}-x$ 과 $x^6-3$ 에 $\mathbb{F}_7[x]$. 그는 유클리드 알고리즘을 사용하지 않고 대신 감소를 사용하여$x^6=3$ 에 $x^{49}-x$. 왜 그리고 어떻게 작동하는지 이해하고 싶습니다. 미리 감사드립니다.

Answer 1

유클리드 알고리즘의 첫 번째 단계는 $q,r\in\Bbb{F}_7[x]$ 그런 $$x^{49}-x=q\cdot(x^6-3)+r,$$ 와 $\deg r<6$, 및 $\gcd(x^{49}-x,x^6-3)$ 분할 $r$. 모드 줄이기$x^6-3$ 그런 다음 보여줍니다 $$r\equiv x^{49}-x\pmod{x^6-3}.$$ 물론 우리는 줄일 수 있습니다 $x^{49}-x$ 모드 $x^6-3$ 교체하여 $x^6$ 와 $3$, 항복 $$r\equiv x^{49}-x\equiv(x^6)^8\cdot x-x\equiv x\pmod{x^6-3}.$$ 같이 $\deg r<6$ 이것은 보여줍니다 $r=x$. 그것은 다음과 같습니다$\gcd(x^{49}-x,x^6-3)$ 분할 $x$, 그로부터 신속하게 $\gcd$ 같음 $1$.

Answer 2

또 다른 주장은 $x^6-3$이다 기약 에서가$\Bbb F_7[x]$, 및 $x^{7^2}-x$선형 및 2 차 요인으로 완전히 분할됩니다. 특히,$x^{49}-x$ 학위를 줄일 수없는 요인이 없습니다 $6$.

편집 : 이 질문을 참조하십시오 .