Algebros paskaitos informatikams. Rimantas Grigutis

5 paskaita. Dalumas su liekana. BDD. Tarpusavyje pirminiai polinomai. Neredukuojami polinomai. Skirtingo laipsnio polinomu̧ išskyrimas.

Panašiai kaip ir sveiku̧ju̧ skaičiu̧ žiede, taip ir polinomu̧ virš kūno žiede yra teisinga dalumo su liekana teorema.

Teorema( dalumas su liekana). Tegu f (x) , g (x) ∈ K [x] , g (x) ≠ 0. Tada egzistuoja vienintėliai polinomai q (x) ir r (x) su kuriais teisinga lygybė f = gq+r, čia deg r (x) < deg g (x) .

I̧rodymas.Egzistavimas. Matematinė indukcija pagal n = deg f (x) .

1. Indukcijos bazė: n = 0, t.y. f (x) = a ∈ K. Galimi du atvejai:

(i) deg g (x) = 0, t.y. g (x) = b ≠ 0. Tada f = g · \frac{a}{b} +0 ir -∞ = deg 0 < deg g = 0.

(ii) deg g (x) > 0. Tada f = g · 0 +f ir 0 = deg f < deg g.

2. Indukcijos prielaida. Tegu teiginys yra teisingas visiems polinomams, kuriu̧ laipsnis < n.

3. Indukcijos teigini̧ i̧rodysime n - ojo laipsnio polinomui f (x) . Tegu polinomo f vyriausias koeficientas yra a_{n}, o polinomo g laipsnis yra m, o vyriausias koeficientas b_{m}. galimi du atvejai:

(i) n < m. Tada f (x) = g (x) · 0 + f (x) ir n = deg f (x) < deg g (x) = m. (ii) n ≥ m. Tada polinomo f_{1} (x) = f (x) − \frac{a_{n}}{b_{m}} x^{n−m}g (x) laipsnis yra < n ir

pagal indukcijos prielaida̧ turime, kad egzistuoja tokie polinomai q_{1} (x) ir r (x) iš K [x] , kad f_{1} (x) = g (x) · q (x) + r (x) , deg r (x) < deg g (x) . Tada

f (x) = g (x) · (\frac{a_{n}}{b_{m}} x^{n−m} + q_{1} (x)) g (x) + r (x) , deg r (x) < deg g (x) .

Vienatinumas. Tegu f (x) = g (x) · p (x) + s (x) , deg s (x) < deg g (x) . Tada

0 = g (x) · (q (x) − p (x)) + (r (x) − s (x))
g (x) · (q (x) − p (x)) = (s (x) − r (x))

ir

deg g (x) + deg (q (x) − p (x)) = deg (s (x) − r (x)) .

Tai i̧manoma tik tuo atveju, kai q (x) − p (x) = s (x) − r (x) = 0. I̧rodyta.

Apibrėžimas. Tegu f (x) , g (x) ∈ K [x] , g (x) ≠ 0. Didžiausio laipsnio polinomas d (x) ∈ K [x], kurio vyriausias koeficientas yra lygus 1, vadinamas polinomu̧ f ir g bendru didžiausiu dalikliu, jeigu

1. f⋮d, g⋮d.

2. Jeigu f⋮d_{1}, g⋮d_{1}, čia d_{1} (x) ∈ K [x] , tai d⋮d_{1}. Bendro didžiausio daliklio žymuo: d (x) = BDD(f (x) , g (x)) = (f (x) , g (x)) .

Teorema. Su visais f, g ∈ K [x] , f ≠ 0, g ≠ 0 egzistuoja tokie polinomai a_{0} (x) , b_{0} (x) ∈ K [x] , kad (f (x) , g (x)) = f (x) a_{0} (x) + g (x) b_{0} (x) .

I̧rodymas paliekamas skaitytojui.

Euklido algoritmas BDD skaičiavimui. Turime du polinomus f (x) , g (x) ∈ K [x] , g ≠ 0.Rašysime dalybos su liekana teorema̧

Tegu a_{0} = f ir a_{1} = g. Tada

a_{0} = a_{1}q_{1} + a_{2}  deg a_{2} < deg a_{1}
a_{1} = a_{2}q_{2} + a_{3}  deg a_{3} < deg a_{2}
⋯  ⋯
a_{k−2} = a_{k−1}q_{k−1} + a_{k} deg a_{k} < deg a_{k−1}
a_{k−1} = a_{k}q_{k}.

Sveikieji skaičiai sudaro mažėjančia̧ seka̧ deg a_{1} > deg a_{2} > deg a_{3} > ⋯ > deg a_{k} > deg a_{k+1} > 0. Tada (a, b) = a_{k}.

Apibrėžimas. Du polinomai f, g ∈ K [x] vadinami tarpusavyje pirminiais, jeigu (f, g) = 1.

Teorema. Polinomai f, g ∈ K [x] yra tarpusavyje pirminiai tada ir tik tada, kada egzistuoja tokie a (x) , b (x) ∈ K [x] , kad f · a + g · b = 1.

I̧rodymas. Teiginys iš kairės i̧ dešinȩ yra teisingas pagal apibrėžima̧. Tegu dabar f · a + g · b = 1 ir (f, g) = d. Tada

1 =\underbrace{\underbrace{f · a}_{dalijasi iš d} + \underbrace{g · b}_{dalijasi iš d}}_{dalijasi iš d},

t,y. 1 dalijasi iš d ir todėl d = 1.

I̧rodyta.

Teiginys(tarpusavyje pirminiu̧ polinomu̧ savybė). Tegu f_{1}, ..., f_{m} ir g_{1}, ..., g_{n} yra dvi tokios polinomu̧ sekos, kad (f_{i}, g_{j}) = 1 su visais 1 ≤ i ≤ m, 1 ≤ j ≤ n. Tada (f_{1} ⋯ f_{m}, g_{1} ⋯ g_{n}) = 1.

Be i̧rodymo.

Dabar pateiksime teigini̧, kurio analogo sveiku̧ju̧ skaičiu̧ žiede nėra.

Teiginys. Jeigu f ir g yra tarpusavyje pirminiai polinomai virš kūno K, tai jie neturi bendru̧ šaknu̧ jokiame kūno K plėtinyje, t.y. tokiame kūne L, kad L ⊇ K.

I̧rodymas.[..........]

Apibrėžimas. Teigiamo laipsnio polinomas f (x) ∈ K [x] vadinamas neredukuojamu polinomu virš kūno K, jeigu jis turi tik šiuos daliklius: a, a · f (x) , čia a ∈ K .

Teiginys. Bet kuris teigiamo laipsnio polinomas iš K [x] dalijasi iš kurio nors neredukuojamo polinomo virš K.

Teorema. Yra be galo daug neredukuojamu̧ polinomu̧ virš bet kurio kūno.

I̧rodymas. I̧rodysime prieštaros būdu. Sakykime, egzistuoja baigtinis neredukuojamu̧ polinomu̧ kiekis: p_{1}, p_{2}, ..., p_{m}. Polinomas f = p_{1}p_{2} ⋯ p_{m} + 1 dalijasi iš neredukuojamo polinomo, taigi egzistuoja toks i, 1 ≤ i ≤ m, kad f⋮p_{i}. Tada

1 =\underbrace{\underbrace{f}_{dalijasi iš p_{i}} − \underbrace{p_{1}p_{2} ⋯ p_{m}}_{dalijasi iš p_{i}}}_{dalijasi iš p_{i}} ,

t.y. 1⋮p_{i}, o tai prieštarauja neredukuojamo polinomo apibrėžimui(deg p_{i} > 0). I̧rodyta.

Teiginys( neredukuojamu̧ polinomu̧ savybė). Tegu f_{1}, ..., f_{m} yra tokia polinomu̧ iš K [x] seka, kad polinomas f_{1}···f_{m} dalijasi iš neredukuojamo polinomo p (x) ∈ K [x] . Tada egzistuoja toks j, 1 ≤ j ≤ m, kad f_{j} dalijasi iš p.

Be i̧rodymo.

Pateiksime teigini̧, kurio analogo sveiku̧ju̧ skaičiu̧ žiede nėra.

Teiginys. Jeigu neredukuojamas virš kūno K polinomas p (x) ∈ K [x] ir polinomas f (x) ∈ K [x] turi bendra̧ šakni̧ x_{0} kuriame nors kūno K plėtinyje

L ⊃ K, x_{0} ∈ L, tai f (x) ⋮p (x) .

I̧rodymas. Iš sa̧lygos matome, kad (f (x) , p (x)) ≠ 1, nes ir f (x) , ir p (x)

dalijasi iš (x − x_{0}) . Polinomas p (x) yra neredukuojamas, todėl f (x) ⋮p (x) . I̧rodyta.

Teorema( kanoninis polinomo skaidinys). Su kiekvienu teigiamo laipsnio polinomu f (x) ∈ K [x] egzistuoja tokie neredukuojami virš kūno k polinomia p_{1}, p_{2}, ..., p_{s} (tarp ju̧ gali būti sutampančiu̧), kad f = a·p_{1} ·p_{2} ·· · ··p_{s}, čia a− polinomo f koeficientas prie x^{n}, kai n = deg f. ( Šiame skaidinyje sutraukȩ panašius daugiklius turėsime kanonini̧ polinomo f skaidini̧: f = a · p_{i_{1}}^{k_{1}} · p_{i_{2}}^{k_{2}} ⋯ p_{i_{s}}^{k_{s}}, p_{i} ≠ p_{j}.)

Be i̧rodymo.

Gri̧žkime prie neredukuojamu̧ polinomu̧ virš realiu̧ju̧ skaičiu̧ kūno R ir virš kompleksiniu̧ skaičiu̧ kūno C. Fundamentalioji algebros teorema teigia:

Fundamentalioji algebros teorema. Bet kokia algebrinė lygtis a_{n}x^{n} +⋯+ a_{1}x + a_{0} = 0 , n ≥ 1 su kompleksiniais koeficientais a_{i} ∈ C (0 ≤ i ≤ n) turi mažiausiai viena̧ sprendini̧ x_{0} ∈ C.

Be i̧rodymo.

Matome, kad n− ojo laipsnio polinomas virš kopleksiniu̧ skaičiu̧ kūno C turi lygiai n šaknu̧. Tokiu atveju sakome, kad C yra algebriškai uždaras kūnas.

Akivaizdu, kad neredukuojami polinomai virš C yra tik pirmojo laipsnio polinomai x − a, a ∈ C.

Lema. 1. Tegu polinomas f (x) = a_{n}x^{n} + ⋯ + a_{1}x + a_{0} ∈ C [x] ir f̄(x) =

ā_{n}x^{n} + ⋯ + ā_{1}x + ā_{0}. Tada \overline{f (z)} = f̄\binom{}{z̄} .

2. Tegu polinomas f (x) = a_{n}x^{n} + ⋯ + a_{1}x + a_{0} ∈ R [x] . Tada

\overline{f (z)} = f \binom{}{z̄} .

Neredukuojamus polinomus virš realiu̧ju̧ skaičiu̧ kūno R aprašo tokia teorema.

Teorema. Neredukuojami polinomai virš realiu̧ju̧ skaičiu̧ kūno R yra arba pirmojo laipsnio polinomai x−a, a ∈ R, arba tokie kvadratiniai trinariai x^{2} +px+q, kad p^{2} − 4q < 0.

I̧rodymas. I̧rodysime, kad neredukuojamas virš R polinomas f (x) ∈ R [x] yra arba f (x) = x − a, arba toks f (x) = x^{2} + px + q, kad p^{2} − 4q < 0 (aišku, kad šie polinomai yra neredukuojami virš R). I̧ polinoma̧ f (x) galima žiūrėti ir kaip i̧ polinoma̧ virš C. Tada polinomas f (x) turi kompleksinȩ šakni̧ α = a + ib ( C− algebriškai uždaras kūnas): f (α) = 0. Galimi du atvejai.

1) Jeigu α ∈ R, tai f (x) ⋮ (x − α) ir kadangi f− neredukuojamas, tai f (x) = x − α.

2) Jeigu α ∉ R, tai α ∈ C ir ᾱ ≠ α. Turime f (α) = 0 ⇒ \overline{f (α)} =^{Lema} f \binom{}{ᾱ} = 0,

t.y polinomas f turi mažiausiai dvi šaknis α ir ᾱ. Tada f (x) ⋮ (x − α) (x − ᾱ) . Pastebėsime, kad (x − α) (x − ᾱ) = x^{2} −x (α + ᾱ)+α·ᾱ = x^{2} −2ax+(a^{2} + b^{2}) ∈ R [x] ir D = 4a^{2}−4a^{2}−4b^{2} = −4b^{2} < 0, taigi (x − α) (x − ᾱ) yra neredukuojamas polinomas virš R. Tada f (x) = (x − α) (x − ᾱ) = x^{2} − 2ax + (a^{2} + b^{2}) .

I̧rodyta.

Skirtingo laipsnio dauginamu̧ju̧ išskyrimas.

Apibrėžimas. Tegu f (x) ∈ K [x] . Elementas c ∈ K yra poinomo f (x) k− kartotinė šaknis, jeigu f (x) = (x − c)^{k} · f_{1} (x) , f_{1} (c) ≠ 0. Jeigu k = 1, tai sakome, kad c yra paprastoji polinomo f šaknis.

Apibrėžimas. Jeigu kūno K elementu̧ sekoje {1, 1 + 1, 1 + 1 + 1, ...} nėra 0, tai sakome, kad kūno K charakteristika yra lygi 0, o jeigu skaičius p yra mažiausias toks, kad \underbrace{1 + 1 + ⋯ + 1}_{p kartu̧}= 0 sakome, kad kūno K charakteristika yra

lygi p.

Teiginys. Jeigu x_{0} yra polinomo f (x) ∈ K [x] papratastoji šaknis, tai f′ (x_{0}) ≠ 0.

I̧rodymas.[.........]

Teiginys. Jei polinomo f (x) ∈ K [x] šaknies kartotinumas yra lygus k, ir k nesidalija iš kūno K charakteristikos, tai išvestinės f′ (x) šaknies c kartotinumas lygus k − 1.

I̧rodymas.[.........]

Paskutinius teiginius galime apibendrinti. Tegu kūno K charakteristika yra lygi 0, o polinomo f ∈ K [x] kanoninis skaidinys virš K yra a·p_{1}^{k_{1}}·p_{2}^{k_{2}} ⋯ p_{s}^{k_{s}}, p_{i} ≠ p_{j}.

Teiginys. Tegu polinomo f neredukuojamo daliklio p_{i} ∈ K [x] kartotinumas yra lygus 1( k_{i} = 1). Tada šio polinomo nėra išvestinės f′ kanoniniame skaidinyje .

I̧rodymas.[.........]

Teiginys. Tegu polinomo f neredukuojamo daliklio p_{i} ∈ K [x] kartotinumas yra lygus k_{i}. Tada polinomo p_{i} kartotinumas išvestinės f′ kanoniniame skaidinyje yra lygus k_{i} − 1 .

I̧rodymas.[.........]

Paskutiniojo teiginio pagalba polinoma̧ f galima suskaidyti dauginamaisiais taip: f = aF_{r_{1}} (x) ⋯ F_{r_{l}} (x) , kad polinomo F_{r_{i}} kanoniniame skaidinyje visu̧ neredukuojamu̧ polinomu̧ kartotinumas yra lygus r_{i} ( r_{i} ≠ r_{j}, kai i ≠ j). Tai ir yra skirtingo laipsnio dauginamu̧ju̧ išskyrimas.