Diszkrét matematika 2


1 Diszkrét matematika november Diszkrét matematika előadás Fancsali Szabolcs Levente nudniq Komputeralgebra Tanszék nove...

0 downloads 30 Views 334KB Size

Recommend Documents


No documents


Diszkr´ et matematika 2.

Diszkr´et matematika 2. 9. el˝ oad´as

Fancsali Szabolcs Levente [email protected] www.cs.elte.hu/∼ nudniq Komputeralgebra Tansz´ ek

2018. november 23.

2018. november 23.

1.

Diszkr´ et matematika 2.

2018. november 23.

Polinomok felbonthat´os´aga Defin´ıci´o Legyen R egys´egelemes integrit´asi tartom´any, ´es legyen 0 6= f ∈ R[x] polinom nem egys´eg. Ezt az f nemnulla polinomot pontosan akkor nevezz¨ uk felbonthatatlannak (irreducibilisnek), 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). A konstans nulla polinomot sem felbonthatatlannak, sem felbonthat´onak nem nevezz¨ uk.

2.

Diszkr´ et matematika 2.

2018. november 23.

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.

3.

Diszkr´ et matematika 2.

2018. november 23.

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 = − ff10

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] polinomnak nincs eg´esz gy¨oke. ´ eml´ekezz¨ (Es unk, hogy R[x]-beli polinomnak csak R-beli gy¨okeit defini´altuk. . . )

4.

Diszkr´ et matematika 2.

2018. november 23.

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.

5.

Diszkr´ et matematika 2.

2018. november 23.

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.

6.

Diszkr´ et matematika 2.

2018. november 23.

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. Az algebra alapt´etel´et itt haszn´altuk, de nem bizony´ıtottuk!

7.

Diszkr´ et matematika 2.

2018. november 23.

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 (test f¨ ol¨ otti els˝ ofok´ u polinom...) alapj´an f felbonthatatlan. Ha deg (f ) = 2, ´es f -nek nincs gy¨ oke, akkor kor´abbi ´all´ıt´as (test f¨ol¨otti m´asodfok´ u polinom...) alapj´an f felbonthatatlan. =⇒ Ha f felbonthatatlan, akkor nem lehet deg (f ) < 1. (Mi´ert?) Ha f felbonthatatlan, ´es deg (f ) = 2, akkor nem lehet gy¨oke. (Mi´ert?) De m´eg nem vagyunk k´esz! M´eg nem l´attuk, hogy ne lehetne kett˝on´el magasabb fok´ u egy R felett irreducibilis polinom. . .

8.

Diszkr´ et matematika 2.

2018. november 23.

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. Legyen most c ∈ C \ R gy¨ oke f -nek, ´es tekints¨ uk a g (x) = (x − c)(x − c) = x 2 − 2 Re(c)x + |c|2 ∈ R[x] polinomot. 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. Vagyis f = qg , ami egy nemtrivi´alis felbont´as, ez pedig ellentmond´as.

Megjegyz´es Ha f ∈ R[x]-nek c ∈ C gy¨ oke, akkor c is gy¨ oke, hiszen deg (f )

f (c) =

X j=0

deg (f ) j

fj (c) =

X j=0



deg (f )

fj ·

cj

=

X j=0

fj

cj

=



deg (f )

X j=0

fj

cj 

= f (c) = 0 = 0.

9.

Diszkr´ et matematika 2.

2018. november 23.

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 ¨osszegben 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.

10.

Diszkr´ et matematika 2.

2018. november 23.

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.

11.

Diszkr´ et matematika 2.

2018. november 23.

Polinomok felbonthat´os´aga ´ ıt´as All´ 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.

12.

Diszkr´ et matematika 2.

2018. november 23.

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.

13.

Diszkr´ et matematika 2.

2018. november 23.

Polinomok felbonthat´os´aga K¨ovetkezm´eny f ∈ Z[x] primit´ıv polinom 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.

14.

Diszkr´ et matematika 2.

2018. november 23.

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 o ¨sszeg minden tagj´ at, kiv´eve azt, amelyben i = m ´es j = o.

15.

Diszkr´ et matematika 2.

2018. november 23.

Polinomok felbonthat´os´aga Megjegyz´esek - A felt´etelben fn ´es f0 szerepe felcser´elhet˝ o. - 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.

16.

Diszkr´ et matematika 2.

2018. november 23.

Racion´alis gy¨okteszt T´etel Legyen f (x) = fn xn + fn−1 x n−1 + . . . + f1 x + f0 ∈ Z[x], fn 6= 0 primit´ıv polinom. Ha f

p q

= 0, p, q ∈ Z, (p, q) = 1, akkor p|f0 ´es q|fn .

Bizony´ıt´as 0=f

  p q n

= fn

 n

p + fn−1 q n−1

0 = fn p + fn−1 qp

 n−1 p q

+ . . . + f1

  p q

+ f0

/ · qn

+ . . . + f1 q n−1 p + f0 q n

p|f0 q n , mivel az o ¨sszes t¨ obbi tagnak oszt´ oja p, ´es ´ıgy (p, q) = 1 miatt p|f0 . q|fn p n , mivel az o ¨sszes t¨ obbi tagnak oszt´ oja q, ´es ´ıgy (p, q) = 1 miatt q|fn .

Megjegyz´es f primit´ıvs´ege nem sz¨ uks´eges felt´etel, csak praktikus. (Mi´ert?)

17.

Diszkr´ et matematika 2.

2018. november 23.

A racion´alis gy¨okteszt alkalmaz´asa ´ ıt´as All´ √

2 6∈ Q.

Bizony´ıt´as Tekints¨ uk az x 2 − 2 ∈ Z[x] polinomot. Ennek a qp alak´ u gy¨ okeire (p, q ∈ Z, (p, q) = 1) teljes¨ ul, hogy p|2 ´es q|1, ´ıgy a lehets´eges racion´alis gy¨ okei ±1 ´es ±2.

18.

Diszkr´ et matematika 2.

2018. november 23.

V´eges testek Tekints¨ uk valamely p pr´ımre a Zp testet, tov´abb´a egy f (x) ∈ Zp [x] felbonthatatlan f˝ opolinomot. Vezess¨ uk be a g (x) ≡ h(x) (mod f (x)), ha f (x)|g (x) − h(x) rel´aci´ ot. Ez ekvivalenciarel´aci´ o, ez´ert meghat´aroz egy oszt´alyoz´ast Zp [x]-en. Minden oszt´alynak van deg (f )-n´el alacsonyabb fok´ u reprezent´ansa (Mi´ert?), ´es ha deg (g ), deg (h) < deg (f ), tov´abb´a g ´es h ugyanabban az oszt´alyban van, akkor egyenl˝ oek (Mi´ert?). Teh´at deg (f ) = n eset´en bijekci´ ot l´etes´ıthet¨ unk az n-n´el kisebb fok´ u polinomok ´es az oszt´alyok k¨ oz¨ ott, ´ıgy p n darab oszt´aly van. Az oszt´alyok k¨ oz¨ ott ´ertelmezhetj¨ uk a term´eszetes m´ odon a m˝ uveleteket. Ezeket v´egezhetj¨ uk az n-n´el alacsonyabb fok´ u reprezent´ansokkal: ha a szorzat foka nem kisebb, mint n, akkor az f (x)-szel vett oszt´asi marad´ekot vessz¨ uk.

19.

Diszkr´ et matematika 2.

2018. november 23.

V´eges testek f 6 |g eset´en a b˝ ov´ıtett euklideszi algoritmus alapj´an d(x) = u(x)f (x) + v (x)g (x). Mivel f (x) felbonthatatlan, ez´ert d(x) = d konstans polinom, ´ıgy multiplikat´ıv inverze lesz g (x)-nek.

v (x) d

T´etel (NB) Az ekvivalenciaoszt´alyok halmaza a rajta ´ertelmezett ¨ osszead´assal ´es szorz´assal testet alkot.

Megjegyz´es Tetsz˝ oleges p pr´ım ´es n pozit´ıv eg´esz eset´en l´etezik p n elem˝ u test, mert l´etezik n-ed fok´ u felbonthatatlan polinom Zp -ben.

Megjegyz´es V´eges test elemsz´ama pr´ımhatv´any, tov´abb´a az azonos elemsz´am´ u testek izomorfak.

20.

Diszkr´ et matematika 2.

2018. november 23.

V´eges testek P´elda Tekints¨ uk az x 2 + 1 ∈ Z3 [x] felbonthatatlan polinomot (Mi´ert az?). A legfeljebb els˝ ofok´ u polinomok: 0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2. Az o¨sszead´as m˝ uveleti t´abl´aja: +

0

1

2

x

x+1

x+2

2x

2x+1

2x+2

0 1 2 x x+1 x+2 2x 2x+1 2x+2

0 1 2 x x+1 x+2 2x 2x+1 2x+2

1 2 0 x+1 x+2 x 2x+1 2x+2 2x

2 0 1 x+2 x x+1 2x+2 2x 2x+1

x x+1 x+2 2x 2x+1 2x+2 0 1 2

x+1 x+2 x 2x+1 2x+2 2x 1 2 0

x+2 x x+1 2x+2 2x 2x+1 2 0 1

2x 2x+1 2x+2 0 1 2 x x+1 x+2

2x+1 2x+2 2x 1 2 0 x+1 x+2 x

2x+2 2x 2x+1 2 0 1 x+2 x x+1

P´eld´aul: Z 2x + 2 + 2x + 1 = 4x + 3 =3 x

21.

Diszkr´ et matematika 2.

2018. november 23.

V´eges testek P´elda folyt. ·

0

1

2

x

x+1

x+2

2x

2x+1

2x+2

0 1 2 x x+1 x+2 2x 2x+1 2x+2

0 0 0 0 0 0 0 0 0

0 1 2 x x+1 x+2 2x 2x+1 2x+2

0 2 1 2x 2x+2 2x+1 x x+2 x+1

0 x 2x 2 x+2 2x+2 1 x+1 2x+1

0 x+1 2x+2 x+2 2x 1 2x+1 2 x

0 x+2 2x+1 2x+2 1 x x+1 2x 2

0 2x x 1 2x+1 x+1 2 2x+2 x+2

0 2x+1 x+2 x+1 2 2x 2x+2 x 1

0 2x+2 x+1 2x+1 x 2 x+2 1 2x

P´eld´aul: Z (2x + 2)(2x + 1) = 4x 2 + 6x + 2 =3 x 2 + 2 = (x 2 + 1) + 1

Feladat: Legyen F9 = Z3 [x]/(x 2 + 1). Mik lesznek a z 2 + 1 ∈ F9 [z] polinom gy¨ okei?

22.

Diszkr´ et matematika 2.

2018. november 23.

Polinomok felbonthat´os´aga, V´eges testek

Eddig tartott a kilencedik kis t´emak¨ or. Ebb˝ ol a t´emak¨ orb˝ ol 2018. november 30. 9:15-9:30 k¨oz¨ott lesz k´et vill´amk´erd´es, ´es egy´ uttal a m´asodik nagy t´emak¨ orb˝ol (algebrai strukt´ ur´akb´ ol ´es polinomokb´ ol) egy bizony´ıt´ast is fogok k´erdezni.

23.

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 TIXPDF.COM - All rights reserved.