Diszkr´ et matematika 1. estis k´ epz´ es
Diszkr´et matematika 1. estis k´epz´es 6. el˝ oad´as
M´erai L´aszl´ o di´ai alapj´an Komputeralgebra Tansz´ ek
2015. ˝ osz
2015. ˝ osz
1.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Legnagyobb k¨oz¨os oszt´o Defin´ıci´o Az a ´es b sz´amoknak a d sz´am kit¨ untetett k¨ oz¨ os oszt´ oja (legnagyobb k¨oz¨os oszt´oja), ha d | a, d | b, tov´abb´a c | a ´es c | b eset´en c | d. Figyelem! Itt a ,,legnagyobb” nem a szok´asos rendez´esre utal: Figyelem! 12-nek ´es 9-nek legnagyobb k¨ oz¨ os oszt´ oja lesz a −3 is. A legnagyobb k¨oz¨os oszt´ o csak asszoci´alts´ag erej´eig egy´ertelm˝ u.
Defin´ıci´o Legyen (a, b) = lnko(a, b) a nemnegat´ıv kit¨ untetett k¨ oz¨os oszt´o!
Defin´ıci´o Az a ´es b sz´amoknak az m sz´am kit¨ untetett k¨ oz¨ os t¨ obbsz¨or¨ose (legkisebb k¨oz¨os t¨obsz¨or¨ose), ha a | m, b | m, tov´abb´a a | c ´es b | c eset´en m | c. Legyen [a, b] = lkkt(a, b) a nemnegat´ıv kit¨ untetett k¨ oz¨os t¨obbsz¨or¨os!
2.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
3.
Legnagyobb k¨oz¨os oszt´o kisz´amol´asa, euklideszi algoritmus T´etel B´armely k´et eg´esz sz´amnak l´etezik legnagyobb k¨ oz¨ os oszt´oja, ´es ez meghat´arozhat´o az euklideszi algoritmussal.
Bizony´ıt´as Ha valamelyik sz´am 0, akkor a legnagyobb k¨ oz¨ os oszt´ o a m´asik sz´am. uk el a k¨ ovetkez˝ o oszt´asokat: Tfh a, b nem-nulla sz´amok. V´egezz¨ a = bq1 + r1 ,
0 < r1 < |b|,
b = r1 q2 + r2 ,
0 < r2 < r1 ,
r1 = r2 q3 + r3 ,
0 < r3 < r2 ,
.. . rn−2 = rn−1 qn + rn ,
0 < rn < rn−1 ,
rn−1 = rn qn+1 .
Ekkor az lnko az utols´o nem-nulla marad´ek: (a, b) = rn . Itt a = r−1 , b = r0 .
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Euklideszi algoritmus helyess´ege Bizony´ıt´as (folyt.) a = bq1 + r1 ,
0 < r1 < |b|,
b = r1 q2 + r2 ,
0 < r2 < r1 ,
r1 = r2 q3 + r3 ,
0 < r3 < r2 ,
.. . rn−2 = rn−1 qn + rn ,
0 < rn < rn−1 ,
rn−1 = rn qn+1 .
Az algoritmus v´eges sok l´ep´esben v´eget ´er: |b| > r1 > r2 > . . . . o: rn | rn−1 ⇒ rn | rn−1 qn + rn = rn−2 ⇒ . . . ⇒ Az rn marad´ek k¨oz¨os oszt´ ⇒ rn | b ⇒ rn | a. Az rn marad´ek a legnagyobb k¨ oz¨ os oszt´ o: legyen c | a, c | b ⇒ c | a − bq1 = r1 ⇒ c | b − r1 q2 = r2 ⇒ . . . ⇒ c | rn−2 − rn−1 qn = rn .
4.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
5.
Legnagyobb k¨oz¨os oszt´o kisz´amol´asa, euklideszi algoritmus
P´elda Sz´am´ıtsuk ki (172, 62) ´ert´ek´et! i -1 0 1 2 3 4 5
ri 172 62 48 14 6 2 0
qi – – 2 1 3 2 3
ri−2 = – – 172 = 62 = 48 = 14 = 6=
A legnagyobb k¨oz¨os oszt´ o: (172, 62) = 2
ri−1 qi + ri
62 · 2 + 48 48 · 1 + 14 14 · 3 + 6 6·2+2 2·3+0
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Legnagyobb k¨oz¨os oszt´o kisz´amol´asa rekurzi´oval T´etel Legyen a 6= 0. Ha b = 0, akkor (a, b) = a. Ha b 6= 0, akkor (a, b) = (|b|, a mod |b|).
Bizony´ıt´as Ha b = 0, akkor a t´etel nyilv´anval´ o. Mivel (a, b) = (|a|, |b|), feltehet˝o, hogy a, b > 0. Ha b 6= 0, osszuk el marad´ekosan a-t b-vel: a = b · q + (a mod b). Ez az euklideszi algoritmus els˝ o sora.
P´elda Sz´am´ıtsuk ki (172, 62) ´ert´ek´et! (a, b)
a mod |b|
(172, 62) (62, 48) (48, 14) (14, 6) (6, 2)
48 14 6 2 0
A legnagyobb k¨ oz¨ os oszt´o: (172, 62) = 2.
6.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
Legnagyobb k¨oz¨os oszt´o, tov´abbi ´eszrev´etelek Hasonl´o m´odon defini´alhat´ o t¨ obb sz´am legnagyobb k¨ oz¨os oszt´oja is: (a1 , a2 , . . . , an ).
´ ıt´as All´ B´armely a1 , a2 , . . . , an eg´esz sz´amokra l´etezik (a1 , a2 , . . . , an ) ´es (a1 , a2 , . . . , an ) = ((. . . (a1 , a2 ), . . . , an−1 ), an ).
´ ıt´as All´ B´armely a, b, c eg´esz sz´amokra (ca, cb) = c(a, b).
2015. ˝ osz
7.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
B˝ov´ıtett euklideszi algoritmus T´etel Tetsz˝oleges a, b eg´esz sz´amok eset´en l´eteznek x, y eg´eszek, hogy (a, b) = x · a + y · b.
Bizony´ıt´as Legyenek qi , ri az euklideszi algoritmussal megkapott h´anyadosok, marad´ekok. Legyen x−1 = 1, x0 = 0 ´es i ≥ 1 eset´en legyen xi = xi−2 − qi xi−1 . Hasonl´oan legyen y−1 = 0, y0 = 1 ´es i ≥ 1 eset´en legyen yi = yi−2 − qi yi−1 . Ekkor i ≥ 1 eset´en xi a + yi b = ri . (Biz.: HF, indukci´ oval) Speci´alisan xn a + yn b = rn = (a, b).
2015. ˝ osz
8.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
B˝ovitett euklideszi algoritmus Algoritmus: ri−2 = ri−1 qi + ri , Algoritmus: x−1 = 1, x0 = 0, xi = xi−2 − qi xi−1 , Algoritmus: y−1 = 0, y0 = −1, yi = yi−2 − qi yi−1 .
P´elda Sz´am´ıtsuk ki (172, 62) ´ert´ek´et, ´es oldjuk meg a 172x + 62y = (172, 62) egyenletet! i -1 0 1 2 3 4 5
rn 172 62 48 14 6 2 0
qn – – 2 1 3 2 3
xi 1 0 1 −1 4 −9 –
yi 0 1 −2 3 −11 25 –
ri = 172xi + 62yi 172 = 172 · 1 + 62 · 0 62 = 172 · 0 + 62 · 1 48 = 172 · 1 + 62 · (−2) 14 = 172 · (−1) + 62 · 3 6 = 172 · 4 + 62 · (−11) 2 = 172 · (−9) + 62 · 25 –
A fel´ır´as: 2 = 172 · (−9) + 62 · 25, x = −9, y = 25.
9.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Felbonthatatlanok, pr´ımek Eml´ ekeztet˝ o: f felbonthatatlan: csak trivi´alis oszt´ oi vannak: ε, ε · f Eml´ ekeztet˝ o: t´ıpus´ u oszt´ ok (ahol ε egy egys´eg). Eml´ ekeztet˝ o: p pr´ım: p | ab ⇒ p | a vagy p | b. Eml´ ekeztet˝ o: Ha p pr´ım, akkor p felbonthatatlan. Az eg´esz sz´amok k¨or´eben a ford´ıtott ir´any is igaz:
T´etel Minden felbonthatatlan sz´am pr´ımsz´am.
Bizony´ıt´as Legyen p felbonthatatlan, ´es legyen p | ab. Tfh. p - b. Ekkor p ´es b relat´ıv pr´ımek. A b˝ov´ıtett euklideszi algoritmussal kaphatunk x, y eg´eszeket, hogy px + by = 1. Innen pax + aby = a. Mivel p oszt´oja a bal oldalnak, ´ıgy oszt´oja a jobb oldalnak is: p | a.
10.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Sz´amelm´elet alapt´etele T´etel Minden nem-nulla, nem egys´eg eg´esz sz´am sorrendt˝ ol ´es asszoci´altakt´ol eltekintve egy´ertelm˝ uen fel´ırhat´ o pr´ımsz´amok szorzatak´ent.
Bizony´ıt´as Csak nemnegat´ıv sz´amokra. ´ aban ha n L´ etez´ es: Indukci´oval: n = 2, n = 3 eset´en igaz (pr´ımek). Altal´ pr´ım, akkor k´eszen vagyunk, ha nem, akkor szorzatra bomlik nemtrivi´alis m´odon. A t´enyez˝ok m´ar felbonthat´ ok indukci´ o alapj´an. Egy´ ertelm˝ us´ eg: Indukci´ oval: n = 2, n = 3 eset´en igaz (felbonthatatlanok). Tfh. n = p1 p2 · · · pk = q1 q2 · · · q` , ahol p1 , p2 , . . . , pk , q1 , q2 , . . . , q` pr´ımek, ´es n a legkisebb olyan sz´am, aminek k´et l´enyegesen k¨ ul¨onb¨oz˝ o el˝ o´all´ıt´asa van. p1 osztja a bal oldalt ⇒ osztja a jobb oldalt, feltehet˝o p1 = q1 . Egyszer˝ us´ıtve: n0 = p2 · · · pk = q2 · · · q` . Indukci´o alapj´an ez m´ar egy´ertelm˝ u.
11.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Sz´amelm´elet alapt´etele Defin´ıci´o Egy n nem-nulla eg´esz sz´am kanonikus alakja: ` Y piαi , ahol p1 , p2 ,. . . , p` k¨ n = ±p1α1 p2α2 · · · p`α` = ± ul¨onb¨oz˝o pozit´ıv i=1
pr´ımek, α1 , α2 ,. . . , α` pozit´ıv eg´eszek.
K¨ovetkezm´eny (HF) Legyenek n, m > 1 pozit´ıv eg´eszek: n = p1α1 p2α2 · · · p`α` , m = p1β1 p2β2 · · · p`β` , (ahol most αi , βi ≥ 0 nemnegat´ıv eg´eszek!). Ekkor min{α1 ,β1 } min{α2 ,β2 } min{α` ,β` } (n, m) = p1 p2 · · · p` , max{α ,β } max{α2 ,β2 }
1 1 [n, m] = p1 p2 (n, m) · [n, m] = n · m.
max{α` ,β` }
· · · p`
,
12.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Oszt´ok sz´ama Defin´ıci´o Egy n > 1 eg´esz eset´en legyen τ (n) az n pozit´ıv oszt´ oinak sz´ama.
P´elda τ (6) = 4, oszt´ok: 1, 2, 3, 6;
τ (96) = 12, oszt´ ok: 1, 2, 3, 4, 6, 8, . . .
T´etel Legyen n > 1 eg´esz, n = p1α1 p2α2 · · · p`α` kanonikus alakkal. Ekkor τ (n) = (α1 + 1) · (α2 + 1) · · · (α` + 1).
Bizony´ıt´as n lehets´eges oszt´oit u ´gy kapjuk, hogy a d = p1β1 p2β2 · · · p`β` kifejez´esben az o¨sszes βi kitev˝o v´egigfut a {0, 1, . . . , αi } halmazon. ´Igy ez a kitev˝o αi + 1-f´elek´eppen v´alaszthat´ o.
P´elda τ (2 · 3) = (1 + 1) · (1 + 1) = 4;
τ (25 · 3) = (5 + 1) · (1 + 1) = 12.
13.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Pr´ımekr˝ol T´etel (Euklidesz) V´egtelen sok pr´ım van.
Bizony´ıt´as Indirekt tfh. csak v´eges sok pr´ım van. Legyenek ezek p1 , . . . , pk . Tekints¨ uk az n = p1 · · · pk + 1 sz´amot. Ez nem oszthat´o egyetlen p1 , . . . , pk pr´ımmel sem, ´ıgy n pr´ımt´enyez˝ os felbont´as´aban kell szerepelnie egy u ´jabb pr´ımsz´amnak.
T´etel (Dirichlet, NB) Ha a, d eg´esz sz´amok, d > 0, (a, d) = 1, akkor v´egtelen sok ak + d alak´ u pr´ım van.
14.
Elemi sz´ amelm´ elet
Diszkr´ et matematika 1. estis k´ epz´ es
2015. ˝ osz
Pr´ımekr˝ol x Pr´ımsz´ amt´ etel: x-ig a pr´ımek sz´ama ∼ . (Sok pr´ım van!) ln x Pr´ımek sz´ama: x 10 100 1000 10000
pr´ımek sz´ama 4 25 168 1229
x/ ln x 4, 33 21, 71 144, 76 1085, 73
Eratoszthen´ esz szit´ aja: Keress¨ uk meg egy adott n-ig az ¨osszes pr´ımet. Soroljuk fel 2-t˝ol n-ig az eg´esz sz´amokat. Ekkor 2 pr´ım. A 2 (val´odi) t¨obbsz¨or¨osei nem pr´ımek, ezeket h´ uzzuk ki. A k¨ ovetkez˝o (ki nem h´ uzott) sz´am 3 szint´en pr´ım. A 3 (val´ odi) t¨ obbsz¨ or¨ osei nem pr´ımek, ezeket h´ uzzuk ki. . . √ Ism´etelj¨ uk az elj´ar´ast n-ig. A ki nem h´ uzott sz´amok mind pr´ımek.
15.
