Diszkr´ et matematika 2.C szakir´ any
Diszkr´et matematika 2.C szakir´any 7. el˝ oad´as
Nagy G´abor
[email protected] [email protected] compalg.inf.elte.hu/∼nagy Komputeralgebra Tansz´ ek
2015. ˝ osz
2015. ˝ osz
1.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga Defin´ıci´o Legyen R egys´egelemes integrit´asi tartom´any. Ha a 0 6= f ∈ R[x] polinom nem egys´eg, akkor felbonthatatlannak (irreducibilisnek) nevezz¨ uk, ha ∀a, b ∈ R[x]-re f = a · b =⇒ (a egys´eg ∨ b egys´eg) . Ha a 0 6= f ∈ R[x] polinom nem egys´eg, ´es nem felbonthatatlan, akkor felbonthat´onak (reducibilisnek) nevezz¨ uk.
Megjegyz´es Ut´obbi azt jelenti, hogy f -nek van nemtrivi´alis szorzat-el˝o´all´ıt´asa (olyan, amiben egyik t´enyez˝o sem egys´eg).
2.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
Polinomok felbonthat´os´aga ´ ıt´as All´ Legyen (R; ∗, ◦) gy˝ ur˝ u 0 ∈ R nullelemmel. Ekkor ∀r ∈ R eset´en 0 ◦ r = r ◦ 0 = 0.
Bizony´ıt´as 0 ◦ r = (0 ∗ 0) ◦ r = (0 ◦ r ) ∗ (0 ◦ r ) =⇒ 0 = 0 ◦ r . A m´asik ´all´ıt´as bizony´ıt´asa ugyan´ıgy.
´ ıt´as All´ Test nulloszt´omentes.
Bizony´ıt´as Legyen (F ; ∗, ◦) test 0 ∈ F nullelemmel, ´es 1 ∈ F egys´egelemmel. Indirekt tfh. l´eteznek a, b ∈ F nem-nulla elemek, amikre a ◦ b = 0. Ekkor b = 1 ◦ b = a−1 ◦ a ◦ b = a−1 ◦ 0 = 0, ami ellentmond´as.
2015. ˝ osz
3.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga ´ ıt´as All´ Legyen (F ; +, ·) test. Ekkor f ∈ F [x] pontosan akkor egys´eg, ha deg (f ) = 0.
Bizony´ıt´as ⇐= Ha deg (f ) = 0, akkor f nem-nulla konstans polinom: f (x) = f0 . Mivel F test, ez´ert l´etezik f0−1 ∈ F , amire f0 · f0−1 = 1, ´ıgy f t´enyleg egys´eg. =⇒ Ha f egys´eg, akkor l´etezik g ∈ F [x], amire f · g = 1, ´es ´ıgy deg (f ) + deg (g ) = deg (1) = 0 (Mi´ert?), ami csak deg (f ) = deg (g ) = 0 eset´en lehets´eges.
4.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga ´ ıt´as All´ Legyen (F ; +, ·) test, ´es f ∈ F [x]. Ha deg (f ) = 1, akkor f -nek van gy¨oke.
Bizony´ıt´as Ha deg (f ) = 1, akkor fel´ırhat´ o f (x) = f1 x + f0 alakban, ahol f1 6= 0. Azt szeretn´enk, hogy l´etezzen c ∈ F , amire f (c) = 0, vagyis f1 c + f0 = 0. Ekkor f1 c = −f0 (Mi´ert?), ´es mivel l´e tezik f1−1 ∈ F , amire f1 · f1−1 = 1 (Mi´ert?), ez´ert c = −f0 · f1−1 = − ff01
gy¨ ok lesz.
Megjegyz´es Ha (R; +, ·) nem test, akkor egy R f¨ ol¨ otti els˝ ofok´ u polinomnak nem felt´etlen¨ ul van gy¨oke, pl. 2x − 1 ∈ Z[x].
5.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga ´ ıt´as All´ Legyen (F ; +, ·) test, ´es f ∈ F [x]. Ha deg (f ) = 1, akkor f felbonthatatlan.
Bizony´ıt´as Legyen f = g · h. Ekkor deg (g ) + deg (h) = deg (f ) = 1 (Mi´ert?) miatt deg (g ) = 0 ∧ deg (h) = 1 vagy deg (g ) = 1 ∧ deg (h) = 0. El˝obbi esetben g , ut´obbiban h egys´eg a kor´abbi ´all´ıt´as ´ertelm´eben.
Megjegyz´es Teh´at nem igaz, hogy egy felbonthatatlan polinomnak nem lehet gy¨oke.
6.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga ´ ıt´as All´ Legyen (F ; +, ·) test, ´es f ∈ F [x]. Ha 2 ≤ deg (f ) ≤ 3, akkor f pontosan akkor felbonthat´o, ha van gy¨ oke.
Bizony´ıt´as ⇐= Ha c gy¨oke f -nek, akkor az f (x) = (x − c)g (x) egy nemtrivi´alis felbont´as (Mi´ert?). =⇒ Mivel 2 = 0 + 2 = 1 + 1, illetve 3 = 0 + 3 = 1 + 2, ´es m´as ¨osszegk´ent nem ´allnak el˝o, ez´ert amennyiben f -nek van nemtrivi´alis felbont´asa, akkor van els˝ofok´ u oszt´oja. A kor´abbi ´all´ıt´as alapj´an ennek van gy¨oke, ´es ez nyilv´an f gy¨oke is lesz.
7.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga T´etel f ∈ C[x] pontosan akkor felbonthatatlan, ha deg (f ) = 1.
Bizony´ıt´as ⇐= Mivel C a szok´asos m˝ uveletekkel test, ez´ert kor´abbi ´all´ıt´as alapj´an teljes¨ ul. =⇒ Indirekt tfh. deg (f ) 6= 1. Ha deg (f ) < 1, akkor f = 0 vagy f egys´eg, teh´at nem felbonthatatlan, ellentmond´asra jutottunk. deg (f ) > 1 eset´en az algebra alapt´etele ´ertelm´eben van gy¨oke f -nek. A gy¨okt´enyez˝ot kiemelve az f (x) = (x − c)g (x) alakot kapjuk, ahol deg (g ) ≥ 1 (Mi´ert?), vagyis egy nemtrivi´alis szorzat-el˝ o´all´ıt´ast, ´ıgy f nem felbonthatatlan, ellentmond´asra jutottunk.
8.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga T´etel f ∈ R[x] pontosan akkor felbonthatatlan, ha deg (f ) = 1, vagy deg (f ) = 2, ´es f -nek nincs (val´ os) gy¨ oke.
Bizony´ıt´as ⇐= Ha deg (f ) = 1, akkor kor´abbi ´all´ıt´as alapj´an f felbonthatatlan. Ha deg (f ) = 2, ´es f -nek nincs gy¨ oke, akkor f nem ´all el˝o k´et els˝ofok´ u polinom szorzatak´ent (Mi´ert?), vagyis csak olyan k´ett´enyez˝os szorzat-el˝o´all´ıt´asa lehet, melyben az egyik t´enyez˝ o foka 0, teh´at egys´eg. =⇒ Ha f felbonthatatlan, akkor nem lehet deg (f ) < 1. (Mi´ert?) Ha f felbonthatatlan, ´es deg (f ) = 2, akkor tfh. van gy¨oke. Ekkor az ehhez tartoz´o gy¨okt´enyez˝ o kiemel´es´evel egy nemtrivi´alis felbont´as´at kapjuk f -nek (Mi´ert?), ami ellentmond´as.
9.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga Bizony´ıt´as folyt. Tfh. deg (f ) ≥ 3. Az algebra alapt´etele ´ertelm´eben f -nek mint C f¨ol¨otti polinomnak van c ∈ C gy¨ oke. Ha c ∈ R is teljes¨ ul, akkor a gy¨okt´enyez˝o kiemel´es´evel f egy nemtrivi´alis felbont´as´at kapjuk (Mi´ert?), ami ellentmond´as. oke, hiszen Mivel f ∈ R[x], ez´ert c is gy¨ f (c) =
deg (f )
deg (f )
deg (f )
X
X
X
j=0
fj (c)j =
j=0
fj · c j =
j=0
fj c j =
deg (f )
X
fj c j = f (c) = 0 = 0.
j=0
Legyen g (x) = (x − c)(x − c) = x 2 − 2 Re(c) + |c|2 ∈ R[x]. f -et g -vel marad´ekosan osztva l´etezik q, r ∈ R[x], hogy f = qg + r . r = 0, mert deg (r ) < 2, ´es r -nek gy¨ oke c ∈ C \ R. alis felbont´ as, ez pedig ellentmond´ as. Vagyis f = qg , ami egy nemtrivi´
10.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga Defin´ıci´o f ∈ Z[x]-et primit´ıv polinomnak nevezz¨ uk, ha az egy¨ utthat´oinak a legnagyobb k¨oz¨os oszt´oja 1.
Lemma (Gauss) Ha f , g ∈ Z[x] primit´ıv polinomok, akkor fg is primit´ıv polinom.
Bizony´ıt´as Indirekt tfh. fg nem primit´ıv polinom. Ekkor van olyan p ∈ Z pr´ım, ami osztja fg minden egy¨ utthat´ oj´at. Legyen i, illetve j a legkisebb olyan index, amire p6 |fi , illetve p6 |gj (Mi´ert vannak ilyenek?). Ekkor fg -nek az (i + j) index˝ u egy¨ utthat´ oja f0 gi+j + . . . + fi gj + . . . + fi+j g0 , ´es ebben az o¨sszegben p nem oszt´oja fi gj -nek, de oszt´ oja az ¨ osszes t¨obbi tagnak (Mi´ert?), de akkor nem oszt´ oja az ¨ osszegnek, ami ellentmond´as.
11.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga ´ ıt´as All´ Minden 0 6= f ∈ Z[x] polinom fel´ırhat´ o f = df ∗ alakban, ahol 0 6= d ∈ Z, ∗ ´es f ∈ Z[x] egy primit´ıv polinom.
Bizony´ıt´as Ha f -b˝ol az egy¨ utthat´ok legnagyobb k¨ oz¨ os oszt´ oj´at kiemelj¨ uk, ´es azt d-nek v´alasztjuk, akkor megkapjuk a megfelel˝ o el˝ o´all´ıt´ast.
Megjegyz´es Az el˝o´all´ıt´as l´enyeg´eben (el˝ ojelekt˝ ol eltekintve) egy´ertelm˝ u, ´ıgy f ∗ f˝oegy¨ utthat´oj´at pozit´ıvnak v´alasztva egy´ertelm˝ u.
12.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga Lemma Minden 0 6= f ∈ Q[x] polinom fel´ırhat´ o f = af ∗ alakban, ahol 0 6= a ∈ Q, ∗ ´es f ∈ Z[x] egy primit´ıv polinom.
Bizony´ıt´as ´Irjuk fel f egy¨ utthat´oit eg´esz sz´amok h´anyadosaik´ent. Ha v´egigszorozzuk f -et az egy¨ utthat´oi nevez˝ oinek c szorzat´aval, majd kiemelj¨ uk a kapott Z[x]-beli polinom egy¨ utthat´ oinak d legnagyobb k¨ oz¨ os oszt´oj´at, akkor megkapjuk a megfelel˝o el˝ o´all´ıt´ast a = d/c-vel.
Megjegyz´es Az el˝o´all´ıt´as l´enyeg´eben egy´ertelm˝ u: ha f ∗ f˝ oegy¨ utthat´oj´at pozit´ıvnak v´alasztjuk, akkor egy´ertelm˝ u.
13.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga T´etel (Gauss t´etele Z[x]-re) Ha egy f ∈ Z[x] el˝o´all´ıthat´ o k´et nem konstans g , h ∈ Q[x] polinom szorzatak´ent, akkor el˝o´all´ıthat´ o k´et nem konstans g ∗ , h∗ ∈ Z[x] polinom szorzatak´ent is.
Bizony´ıt´as Tfh. f = gh, ahol g , h ∈ Q[x] nem konstans polinomok. Legyen f = df ∗ , ahol d ∈ Z, ´es f ∗ ∈ Z[x] primit´ıv polinom, aminek a f˝ oegy¨ utthat´oja pozit´ıv. Ha fel´ırjuk g -t ag ∗∗ , h-t pedig bh∗∗ alakban, ahol g ∗∗ , h∗∗ ∈ Z[x] primit´ıv polinomok, amiknek a f˝ oegy¨ utthat´oja pozit´ıv, akkor azt kapjuk, hogy df ∗ = f = gh = abg ∗∗ · h∗∗ . Mivel Gauss lemm´aja szerint g ∗∗ · h∗∗ is primit´ıv polinom, tov´abb´a f el˝o´all´ıt´asa primit´ıv polinom seg´ıts´eg´evel l´enyeg´eben egy´ertelm˝ u, ez´ert f ∗ = g ∗∗ h∗∗ , ∗∗ ∗∗ ∗ ´es d = ab, vagyis f = dg h , ´es p´eld´aul g = dg ∗∗ , h∗ = h∗∗ v´alaszt´assal kapjuk f k´ıv´ant felbont´as´at.
14.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
Polinomok felbonthat´os´aga K¨ovetkezm´eny f ∈ Z[x] pontosan akkor felbonthat´ o Z f¨ ol¨ ott, amikor felbonthat´o Q f¨ol¨ott.
Bizony´ıt´as =⇒ A Z f¨ol¨ otti felbont´as egyben Q f¨ ol¨ otti felbont´as is. ⇐= A Gauss-t´etelb˝ol k¨ovetkezik az ´all´ıt´as.
2015. ˝ osz
15.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga T´etel (Sch¨onemann-Eisenstein) Legyen f (x) = fn x n + fn−1 x n−1 + . . . + f1 x + f0 ∈ Z[x], fn 6= 0 legal´abb els˝ofok´ u primit´ıv polinom. Ha tal´alhat´ o olyan p ∈ Z pr´ım, melyre p6 |fn , p|fj , ha 0 ≤ j < n, p 2 6 |f0 , akkor f felbonthatatlan Z f¨ ol¨ ott.
Bizony´ıt´as Tfh. f = gh. Mivel p nem osztja f f˝ oegy¨ utthat´ oj´at, ez´ert sem a g , sem a h f˝oegy¨ utthat´oj´at nem osztja (Mi´ert?). Legyen m a legkisebb olyan index, amelyre p6 |gm , ´es o a legkisebb olyan index, amelyre p6 |ho . Ha k = m + o, akkor X p 6 |fk =
gi hj ,
i+j=k
mivel p osztja az ¨ osszeg minden tagj´ at, kiv´eve azt, amelyben i = m ´es j = o.
16.
Polinomok
Diszkr´ et matematika 2.C szakir´ any
2015. ˝ osz
Polinomok felbonthat´os´aga Bizony´ıt´as folyt. ´Igy m + o = deg (f ), ahonnan m = deg (g ) ´es o = deg (h). Viszont m ´es o nem lehet egyszerre pozit´ıv, mert akkor p 2 |f0 = g0 h0 teljes¨ ulne. ´Igy az egyik polinom konstans, ´es ha nem lenne egys´eg, akkor f nem lenne primit´ıv.
Megjegyz´es A felt´etelben fn ´es f0 szerepe felcser´elhet˝ o.
Megjegyz´es A t´etel nem haszn´alhat´o test f¨ ol¨ otti polinom irreducibilit´as´anak bizony´ıt´as´ara, mert testben nem l´eteznek pr´ımek, hiszen minden nem-nulla elem egys´eg.
17.
