Feladat: 3.44.
F2 [x]-ben dolgozunk. a) Számítsuk ki a

p(x)=1+ x2 + x3 + x4 + x7 + x11 + x12 , q(x)=1+ x2 + x3 + x5 + x8 + x9 + x13 + x15 + x16 .

polinomok legnagyobb közös osztóját és b) fejezzük azt ki a(x)p(x)+b(x)q(x) alakban ( a(x),b(x)∈ F2 [x]).
 

Megoldás: 3.44
a) Számoljunk euklideszi algoritmussal! A polinomok helyett csak az együtthatók sorozatát írjuk fel:

q=p·10011+1101011010; p=1101011010·1001+100010111; 1101011010=100010111·11+1100011; 100010111=1100011·111+111110; 1100011=111110·10+11111; 111110=11111·10+0.

A legnagyobb közös osztó az 11111 sorozatnak megfelelő polinom, azaz x4 + x3 + x2 +x+1.

b) Az euklideszi algoritmus alapján visszafelé sorban kifejezhetjük a maradékokat. Egyszerűsíti a leírást, hogy a ,, +" és a ,, -" művelet F2 -ben ugyanaz. Pl.

11111=1100011+111110·10= =1100011+(100010111+1100011·111)·10= =100010111+1100011·1111=… …=100111011111p+10000100q,

azaz

x4 + x3 + x2 +x+1=( x11 + x8 + x7 + x6 + x4 + x3 + x2 +x+1)p+( x7 + x2 )q.