Calculation of GCD of two polynomials

Question

I want to know the method he used here to find the gcd of $x^{49}-x$ and $x^6-3$ in $\mathbb{F}_7[x]$. It seems that he is not using Euclidean algorithm but rather uses the reduction by replacing $x^6=3$ in $x^{49}-x$. I want to understand why and how it works. Thanks in advance.

Answer 1

The first step of the Euclidean algorithm yields $q,r\in\Bbb{F}_7[x]$ such that $$x^{49}-x=q\cdot(x^6-3)+r,$$ with $\deg r<6$, and $\gcd(x^{49}-x,x^6-3)$ divides $r$. Reducing mod $x^6-3$ then shows that $$r\equiv x^{49}-x\pmod{x^6-3}.$$ Of course we can reduce $x^{49}-x$ mod $x^6-3$ by replacing $x^6$ with $3$, yielding $$r\equiv x^{49}-x\equiv(x^6)^8\cdot x-x\equiv x\pmod{x^6-3}.$$ As $\deg r<6$ this shows that $r=x$. It follows that $\gcd(x^{49}-x,x^6-3)$ divides $x$, from which it quickly follows that the $\gcd$ equals $1$.

Answer 2

Another argument is that $x^6-3$ is irreducible in $\Bbb F_7[x]$, and $x^{7^2}-x$ splits completely into linear and quadratic factors. In particular, $x^{49}-x$ has no factor irreducible of degree $6$.

Edit: See this question.