Re: gcd

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Aug 08, 2019 at 10:20:03AM +0900, macsyma wrote:
> Dear All,
> 
> The greatest common divisor of P and Q defined in
> http://macsyma.starfree.jp/temp/PQ.gp
> is a polynomial with degree 35.(these are in composite form f(x^35))
> 
> But It seems that PARI's gcd(P,Q) does not return the result.

PARI is not well suited to compute gcd of multivariate polynomials.

One potential solution (depending on what you are really interest in)
is to replace c5 and c7 by the corresponding algebraic number in some
common number field:

P7=subst(c7^6+c7^5+c7^4+c7^3+c7^2+c7+1,c7,t);
P5=subst(c5^4+c5^3+c5^2+c5+1,c5,t);
[R,C7,C5,k]=polcompositum(P7,P5,3);
PP=subst(liftall(P),c5,C5)*Mod(1,R);
QQ=subst(liftall(Q),c7,C7)*Mod(1,R);
gcd(PP/content(PP),QQ/content(QQ))
%7 =
54098900643836970629137299009596789341*x^35+Mod(2872446119479658916588913582482059985573713596*t^23+26435186657427183753833170752179602180442683072*t^22+54639264795202655812546436835114762522161042128*t^21+188978855318753758325939335476262484772613939556*t^20+319253166669777594095834880900131060138827681660*t^19+752935251698241802762291653198954808537615951586*t^18+1012935777513302137586745040857735898743703652402*t^17+1943298588304896491658956714793795344072332658832*t^16+2383762437977372897477155030479552487883770971220*t^15+3144045345115102538358670998901027590419296486670*t^14+3910129004666338244977738098577916076173903255216*t^13-2359368617511577058701821106256850382476417351228*t^12+1133706386370379741231092319520631928128065712056*t^11-198204982430809855403369048130126007617196514652*t^10+15195274070241045647762888009437617664775182910196*t^9+37408196205393020478799470962382373456851663864182*t^8+6613195388789164087113598309507747781020100158818*t^7+19676106751798461326131109823960848157043499480826*t^6-3999729806695850139128854130852496120677127907172*t^5-18222110346873488119142019284083640612347629202026*t^4-1760969243385578873291369114518283657844885538730*t^3+2722116629689597393011587622350503714985782092150*t^2+677594034452348980057155994208630454602673744080*t-41687479133619865411596374761005401808511830766,t^24+2*t^23+8*t^22+14*t^21+35*t^20+50*t^19+95*t^18+129*t^17+166*t^16+250*t^15-20*t^14+20*t^13-66*t^12+466*t^11+1866*t^10+1011*t^9+1096*t^8+240*t^7-688*t^6-597*t^5+88*t^4+97*t^3+9*t^2-2*t+1)

Cheers,
Bill.