- nejdříve budeme uvažovat polynomy z
Q[x] v jedné
proměnné
x s racionálními koeficienty
- stupeň polynomu
a(x) označíme jako
deg(a(x))
- pro dva polynomy
a(x), b(x) z
Q[x] , pro
které platí
deg(a(x)) >= deg(b(x)) , definujeme
jejich podíl
quot(a(x),b(x)) a zbytek po dělení
rem(a(x),b(x)) jako polynomy z
Q[x] ,
pro které platí
a(x) = quot(a(x),b(x)) b(x) + rem(a(x),b(x))
- přitom
0 <= deg(rem(a(x),b(x))) < deg(b(x))
- stejně jako pro celá čísla platí pro největší společný dělitel
polynomů (
gcd )
gcd(a(x),b(x)) = gcd(b(x),rem(a(x),b(x)))
- Euklidův algoritmus pro výpočet největšího společného dělitele dvou
polynomů s racionálními koeficienty
- Algoritmus
gcd:=GCDPQ(a(x),b(x))
[a, b jsou polynomy z Q[x]
použité algoritmy:
deg(a) - stupeň polynomu a
rem(a,b) - zbytek po dělení polynomu a polynomem b]
1. if deg(a) < deg(b) then
r:=a;
a:=b;
b:=r;
fi
2. while not(b=0) do
r:=rem(a,b);
a:=b;
b:=r;
do
3. gcd:=a;
- algoritmus vyžaduje řadu výpočtů největšího společného dělitele dvou
celých čísel při výpočtech s racionálními čísly, přičemž celá čísla
mohou být značně velká
- tyto výpočty jsou časově náročné, algoritmus není efektivní
- výpočtů s racionálními čísly se můžeme zbavit tím, že budeme počítat
pouze v oboru polynomů s celočíselnými koeficienty