(1変数xの)Euclidean Algorithm のプログラム


In[1]:=PolyGCD[f_,g_]:=PolyGCD[f,g]=Module[{h,s,if2,rem},
                       h=f;s=g;
                       if2[h1_,s1_]:=if2[h1,s1]=
                       If[s1=!=0,
                       rem=Div[h1,s1][[2]];h=s1;s=rem;if2[h,s]
                       ,h1];
                       if2[h,s]]
		       
		       
	     但し、Div[f_,g_]:=Div[f,g]=Module[{q,r,if,k},
                        q=0;r=f;	    
                        if[q1_,r1_]:=if[q1,r1]=
                        If[r1=!=0&&Exponent[g,x]<=Exponent[r1,x],
                        k=x^Exponent[r1,x]*Coefficient[r1,x,Exponent[r1,x]]/
                          (x^Exponent[g,x]*Coefficient[g,x,Exponent[g,x]]);
                        q=q1+k; r=r1-k*g;if[q,r],
                        {q1,Expand[r1]}];	    
                        if[q,r]]
	       

変数は、xとします。

PolyGCD[多項式、多項式]と入力すると、2つの多項式の最大公約数を出力します。



(Example)

In[2]:=PolyGCD[x^3+2x^2-5x-6, x^2+2x-8]

Out[2]=-6+3x


応用として、以下の2つのプログラムをつくりました。


1: 3つの多項式の最大公約数を求めるプログラム

Poly3GCD[f_,g_,h_]:=Poly3GCD[f,g,h]=PolyGCD[f,PolyGCD[g,h]]


2:fの square-free part を求めるプログラム

Red[f_]:=Red[f]=Simplify[f/PolyGCD[f,D[f,x]]]