CA I - Uebungsblatt 05

Exercise 1 : (Extended euclidian algorithm: Rational numbers)

(a)

Recurrence equation for  the Bézout coeffitients:

from  (Subscript[x, k])=(Subscript[x, k+1])·(Subscript[q, k])+(Subscript[x, k+2])  and  (Subscript[x, k])=(Subscript[s, k])(Subscript[x, 0])+(Subscript[t, k])(Subscript[x, 1 ])we get
(Subscript[x, k+1])·(Subscript[q, k])+(Subscript[x, k+2])=(Subscript[s, k])(Subscript[x, 0])+(Subscript[t, k])(Subscript[x, 1])  and we replace once again (Subscript[x, k])=(Subscript[s, k])(Subscript[x, 0])+(Subscript[t, k])(Subscript[x, 1]) to get

((Subscript[s, k+1])(Subscript[x, 0])+(Subscript[t, k+1])(Subscript[x, 1]))·(Subscript[q, k])+(Subscript[s, k+2])(Subscript[x, 0])+(Subscript[t, k+2])(Subscript[x, 1])=(Subscript[s, k])(Subscript[x, 0])+(Subscript[t, k])(Subscript[x, 1])

sorting the previous equation, we get

((Subscript[s, k+1])(Subscript[q, k])+(Subscript[s, k+2]))·(Subscript[x, 0])+((Subscript[t, k+1])(Subscript[q, k])+(Subscript[t, k+2]))·(Subscript[x, 1])=(Subscript[s, k])(Subscript[x, 0])+(Subscript[t, k])(Subscript[x, 1])

an comparing coefficients gives

(Subscript[s, k+2])=(Subscript[s, k])-(Subscript[q, k])(Subscript[s, k+1]) und (Subscript[t, k+2])=(Subscript[t, k])-(Subscript[q, k])(Subscript[t, k+1])

with the initial values

(Subscript[t, 0])=0 and (Subscript[s, 0])=1 from (Subscript[x, 0])=(Subscript[s, 0])(Subscript[x, 0])+(Subscript[t, 0])(Subscript[x, 1]) and
(Subscript[t, 1])=1 and (Subscript[s, 1])=0 from (Subscript[x, 1])=(Subscript[s, 1])(Subscript[x, 0])+(Subscript[t, 1])(Subscript[x, 1]).

(b)

Clear[ggT];
ggT[x_,y_]:=Module[{temp,s0,s1,t0,t1,x0,x1},
s0=1;s1=0;
t0=0;t1=1;
x0=x;x1=y;
While[x1≠0,
temp=Mod[x0,x1];
q=Quotient[x0,x1];
x0=x1;
x1=temp;
temp=s0-q s1;
s0=s1;
s1=temp;
temp=t0-q t1;
t0=t1;
t1=temp;
];
{x0,{s0,t0}}
]

a=871;b=26;

ggT[a,b]

ExtendedGCD[a,b]

Exercise 2 : (Extended euclidian algorithm: Polynomials with integer coefficients)

<<Algebra`PolynomialExtendedGCD`

PrimitivePolynomial[a_,x_]:=Module[{lcm,gcd,b},
lcm=Apply[LCM,Denominator[CoefficientList[a,x]]];
b=Expand[lcm a];
gcd=Apply[GCD,CoefficientList[b,x]];
{gcd/lcm, Expand[b/gcd]}
]

PrimitivePolynomial[1/6x^6+2/5x^4-1/2x^2-6x,x]

PrimitivePolynomial[6x^6+3x^4-15x^2-9,x]

At first determine the integer α resp. β, which are necessary, to build the polynoms s resp. t with integer coefficients
The multiply the result with their  LCM   (    LCM[α,β] ).

IntegerRepresentation[a_,b_,x_]:=Module[{g,s,t,α,β},
{g,{s,t}}=PolynomialExtendedGCD[a,b,x];
α=1/PrimitivePolynomial[s,x][[1]];
β=1/PrimitivePolynomial[t,x][[1]];
If[IntegerQ[α]&& IntegerQ[β],r=LCM[α,β],r=1];
{Expand[r g] ,{Expand[r s],Expand[r t]}}
]

IntegerRepresentation[Expand[(x^2-5x-5)(x^6-2x^5+4x^4-x^2+2x+1)],Expand[(x^2-5x-5)(3x^5-4x^3+7x^2-x-1)],x]

IntegerRepresentation[Expand[(x-2)(3x^6-x^5-4x^4-x+2)],Expand[(x-2)(3x^5-4x^2+7x-1)],x]

Second and short possibility for exercise 2.

Clear[IntPolyRepresentation];
IntPolyRepresentation[c_,d_,x_]:=Module[{coefflist,denom,factor},
coefflist=CoefficientList[PolynomialExtendedGCD[c,d,x][[2,1;;2]],x];
denom=Flatten[Denominator[coefflist]];
factor=denom/.{y__}->LCM[y];
Expand[PolynomialExtendedGCD[c,d,x]*factor]
]

IntPolyRepresentation[Expand[(x-2)(3x^6-x^5-4x^4-x+2)],Expand[(x-2)(3x^5-4x^2+7x-1)],x]