Tính GCD của hai đa thức

Question

Tôi muốn biết phương pháp anh ấy sử dụng ở đây để tìm gcd của$x^{49}-x$ và $x^6-3$ trong $\mathbb{F}_7[x]$. Có vẻ như anh ta không sử dụng thuật toán Euclide mà sử dụng sự giảm thiểu bằng cách thay thế$x^6=3$ trong $x^{49}-x$. Tôi muốn hiểu tại sao và cách nó hoạt động. Cảm ơn trước.

Answer 1

Bước đầu tiên của thuật toán Euclid mang lại $q,r\in\Bbb{F}_7[x]$ như vậy mà $$x^{49}-x=q\cdot(x^6-3)+r,$$ với $\deg r<6$và $\gcd(x^{49}-x,x^6-3)$ phân chia $r$. Giảm mod$x^6-3$ sau đó cho thấy rằng $$r\equiv x^{49}-x\pmod{x^6-3}.$$ Tất nhiên chúng ta có thể giảm $x^{49}-x$ mod $x^6-3$ Bằng cách thay thế $x^6$ với $3$, năng suất $$r\equiv x^{49}-x\equiv(x^6)^8\cdot x-x\equiv x\pmod{x^6-3}.$$ Như $\deg r<6$ Điêu nay cho thây răng $r=x$. Nó theo sau đó$\gcd(x^{49}-x,x^6-3)$ phân chia $x$, từ đó nó nhanh chóng theo sau rằng $\gcd$ bằng $1$.

Answer 2

Một lập luận khác là $x^6-3$là tối giản trong$\Bbb F_7[x]$và $x^{7^2}-x$tách hoàn toàn thành các thừa số tuyến tính và bậc hai. Đặc biệt,$x^{49}-x$ không có yếu tố nào là bất khả xâm phạm về mức độ $6$.

Chỉnh sửa: Xem câu hỏi này .