Re: Polynomial GCD as Linear Combination
- To: mathgroup at smc.vnet.net
- Subject: [mg38368] Re: [mg38319] Polynomial GCD as Linear Combination
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Fri, 13 Dec 2002 04:09:11 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Youneed touse the package Algebra`ExtendedPolynomialGCD. However,
because of a bug inthis package you need to use a fix. Recently I
provided such a fix in response to another posting on the same topic.
Daniel Lichblau sent me another own, that ought to be better, but I
tried it on your example and got errors. So I am sending my own again.
In[1]:=
<< "Algebra`PolynomialExtendedGCD`"
(Loaded the package)
In[2]:=
MyPolynomialExtendedGCD[a_, b_, p_] :=
With[{gcd = PolynomialGCD[a, b, Modulus -> p]},
{gcd, 1}*PolynomialMod[(PolynomialExtendedGCD[##1,
Modulus -> p] & ) @@ Cancel[{a, b}/gcd,
Modulus -> p], p]]
(my bug fix)
In[3]:=
f[x_] := x^5 + 4*x^4 + 6*x^3 + 6*x^2 + 5*x + 2
In[4]:=
g[x_] := x^4 + 3*x^2 + 3*x + 6
(your polys)
In[5]:=
MyPolynomialExtendedGCD[f[x], g[x], 7]
Out[5]=
{2 + 5*x + 4*x^2 + x^3, {5, 1 + 2*x}}
(the answer, same as yours).
Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/
On Thursday, December 12, 2002, at 03:33 PM, flip wrote:
> Hello,
>
> Can Mathematica do the following? (I provided answers that I did by
> hand).
>
> 1. Find the GCD of
>
> f[x_] := x^5 + 4x^4 + 6x^3 + 6x^2 + 5x +2,
> g[x_] := x^4 + 3x^2 + 3x +6
>
> Answer: gcd (f(x), g(x)) = x^3 + 4x^2 + 5x + 2
>
> over the field Z7? (I think the answer is easy and is yes).
>
> 2. Write the GCD above as a linear combination of the given
> polynomials?
>
> Answer: 5*(x^5 + 4x^4 + 6x^3 + 6x^2 + 5x +2) + (2x + 1)*(x^4 + 3x^2 +
> 3x +6)
>
> This one I am not sure about (I guess we can do it piece-meal, but is
> there
> a slick function to do it?).
>
> Thank you, Flip
>
> Please remove "_alpha" to send me email.
>
>
>
>
>