Timeline for Gcd of polynomials over a finite field
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 21, 2016 at 4:16 | comment | added | KConrad | @ToddLeason, indeed you're right. I had not read the end of that line initially. | |
| May 20, 2016 at 17:04 | comment | added | Emil Jeřábek | Sorry, I have skipped a step, but anyway the calculation as indicated in the answer is correct. Your first comment seemed to argue that the answer is incorrect, whereas your last comment only says that alternatives are available, right? Notice that if you stop early with $n=m$, you effectively still have to perform the missing step reducing one of the coefficients to zero, or in other words, you have to find whether the constant coefficients are the same, so that you know whether the polynomials are coprime. Going all the way down to zero just requires less exceptions. | |
| May 20, 2016 at 16:55 | comment | added | KConrad | @EmilJeřábek, following the calculation as written in the solution (where starting with exponent pair $(n,m)$ with $n \geq m$ we get exponent pair $(m,n-m)$ at the next step) I would write the calculation as $\gcd(x^9-1,x^6-1) = \gcd(x^3-1,x^6-1) = \gcd(x^3-1,x^3-1) = x^3-1$. Of course for a general algorithm you could have instead changed the end to $\gcd(x^3-1,x^3-1) = \gcd(x^3-1,0) = x^3-1$, but my point was that in practice one might end the algorithm early in the way I indicated. | |
| May 20, 2016 at 15:50 | comment | added | Emil Jeřábek | @KConrad: The induction goes $\gcd(x^9-1,x^6-1)=\gcd(x^6-1,x^3-1)=\gcd(x^3-1,x^0-1)$ at which point we stop and observe $\gcd(x^3-1,0)=x^3-1$. This is just like the usual Euclid’s algorithm. | |
| May 20, 2016 at 15:37 | comment | added | Todd Leason | @KConrad: Isn't your 2nd comment already addressed by the first line in the answer ? | |
| May 20, 2016 at 15:31 | comment | added | KConrad | Note also that this solution shows it is irrelevant for the coefficients to be in a finite field; any coefficient field works. | |
| May 20, 2016 at 15:29 | comment | added | KConrad | Clarify the "proceed by induction until..." part, since the exponents might not ever become $0$. Consider starting with $x^6 - 1$ and $x^9-1$, which have gcd $x^3-1$. More generally, $\gcd(x^m-1,x^n-1) = x^{\gcd(m,n)}-1$. | |
| May 20, 2016 at 15:19 | history | answered | Tom De Medts | CC BY-SA 3.0 |