3. előadás Prímtulajdonság, lnko, Euklideszi algoritmus, lánctörtek

Számítástudomány

Széchenyi István Egyetem

3. előadás Prímtulajdonság, lnko, Euklideszi algoritmus, lánctörtek

Dr. Kallós Gábor

2016–2017 11



Tartalom Prímek és felbonthatatlanok Prímtulajdonság, lnko Kiterjesztett egészek Prímfaktorizáció, a számelmélet alaptétele

Euklideszi algoritmus Maradékos osztás Az algoritmus bemutatása A kiterjesztett algoritmus Hatékonysági elemzés Fibonacci-sorozat

Lánctörtek Racionális és irracionális példák

Feladatok Történeti áttekintés Irodalom 2



Prímek és felbonthatatlanok Prímtulajdonság Vizsgálatunk tárgyai: 1-nél nagyobb egész számok Struktúra: Z (gyűrű, sőt: integritási tartomány, lásd később)

Összetett szám (composite integer): felírható két 1-nél nagyobb egész szám szorzataként Prímszám (valójában: felbonthatatlan): nem írható fel ily módon („Másik” felírás; osztó, többszörös, asszociált, egység, közös osztó, legnagyobb közös osztó (lnko) fogalma)

Nagyon fontos kérdések (már: Euklidesz, Kr. e. 300 k., „Elemek”) Ha adott egy összetett szám, hogyan tudjuk 1-nél nagyobb egész számok szorzatára bontani? Hogyan ismerjük fel a prímeket?

Állítás 1. (Euklidesz): Ha egy prímszám osztója két egész szám szorzatának, akkor osztója kell hogy legyen legalább az egyik egésznek Másként: ha p | ab, akkor p | a vagy p | b (esetleg mindkettő is teljesülhet) Megj.: Ez a prímtulajdonság (Biz. később)

Ez az állítás teljesen nyilvánvalónak tűnik, de mégsem az… Probléma (19. század): kiterjesztett egészek

3



Prímek és felbonthatatlanok Kiterjesztett egészek Tekintsük az a + b 10 alakú számokat Ez a legszűkebb olyan struktúra, amely a Z int. tart. 10 -zel való bővítésével adódik, jelölés: Z ( 10 ) Hasonlóan: a + b 2 alakú számok, Z( 2 ), a + b 8 alakú számok, … Ezek tdk. a + bX alakú számok, ahol X2 már Z-beli

Itt az alapműveletek (+, –, *) nyilván elvégezhetők, és nem vezetnek ki a struktúrából Feladat: Igazoljuk ezt!

Osztás – itt már nem minden „sima ügy” A nevező ugyan gyökteleníthető, de végül nem feltétlenül kapunk egész együtthatókat

Feladatok Mutassuk meg, hogy (12 + 3 10 )/(2 + 10 ) = 1 + 10 Igazoljuk, hogy a 3 + 10 osztója minden a + b 10 alakú számnak! (azaz: egység Z ( 10 ) -ben) *Igazoljuk, hogy 2, 3, 4 + 10 és 4 – 10 felbonthatatlanok Z ( 10 )-ben Segítség: Használjuk a normát, és így vizsgáljuk az oszthatóságot!

A felbonthatatlanokra nem (feltétlenül) teljesül a prímtulajdonság, lásd 7. old. 4



Prímek és felbonthatatlanok Kiterjesztett egészek, feladatok (megoldás szemlélt.)

5



Prímek és felbonthatatlanok A prímtulajdonság egy érdekes alkalmazása Tekintsük az a = b esetet. Ha p | a2, akkor p | a. Így ha p | a2, akkor p2 | a2. Állítás 2.: 2 nem fejezhető ki két egész szám hányadosaként (nem racionális szám) Bizonyítás: Tfh. 2 mégis felírható m/n alakban, ahol m és n egészek, és a törtet már egyszerűsítettük, azaz lnko(m, n) = 1. Négyzetre emelünk: 2 = m2/n2, azaz 2n2 = m2. Így 2 | m2. Az 1. állítás szerint tehát 4 | m2. Ekkor 4 | 2n2, azaz 2 | n2. Ebből újból az 1. állítás szerint 2 | n. Ez ellentmondás, mert így lnko(m, n) ≥ 2 lenne.

Feladatok Igazoljuk, hogy a 3 és az 5 négyzetgyöke nem írható fel két egész szám hányadosaként! Igazoljuk, hogy ha n nem teljes négyzet poz. egész szám, akkor n gyöke nem lehet racionális!

*Keressünk olyan (relatív prím) egész számokat, amelyek hányadosa jól közelíti a pi-t az e-t vagy a 2-t! (Pl. 6 tizedesre)

Másik érdekes alkalmazás: pitagoraszi számhármasok, x2 + y2 = z2 Állítás 3.: Tetszőleges a, b egész számokra, amelyek közül az egyik páros, a másik páratlan úgy, hogy 0 < b < a és lnko(a, b) = 1, (a2 – b2, 2ab, a2 + b2) pitagoraszi számhármas. Továbbá minden pitagoraszi számhármas felírható ily módon. Bizonyítás (vázlat): a) Az ilyen számok jók. b) A jó számok mind ilyen alakúak. 6



Prímek és felbonthatatlanok Definíció: egy pozitív egész szám prímek szorzatára történő felbontását (prím)faktorizációnak nevezzük ak a1 a2 n = p ⋅ p ⋅ K ⋅ p 1 2 k (Jelölés: prímek k db, hatványok k db) Definíció: ha lnko(a, b) = 1, akkor azt mondjuk, hogy a és b relatív prímek (alternatív def.: nincs közös prím a faktorizációjukban) Tétel 1. (a számelmélet alaptétele): (Z Z-ben) a számok prímek szorzatára történő felbontása (faktorizációja) sorrendtől (és egységektől) eltekintve egyértelmű Pl.: 30 = 2⋅3⋅5 vagy 30 = (–1)⋅5⋅3⋅2⋅(–1) De: a kiterjesztett egészek körében ez a tétel nem érvényes (!) Pl.: 6 = 2⋅3 = (4 + 10 ) ⋅ (4 –

10 )

Feladatok Keressük meg az összes pitagoraszi számhármast x, y ≤ 50-ig! Írjunk programot valamely általunk kedvelt programnyelven egy intervallum relatív prím elempárjainak a meghatározására/megszámoltatására! Keressünk olyan példákat az a + b 2 alakú számok és az a + b 8 alakú számok között, ahol nem teljesül a számelmélet alaptétele! (Szorzat, ahol sérül a prímtulajdonság.) Próbáljunk meg faktorizálni néhány 20-50 jegyű (véletlenül választott) számot! 7



Prímek és felbonthatatlanok Relatívprímes feladat – VBA megvalósítás

8



Prímek és felbonthatatlanok (Eml. – a számelmélet alaptétele: a prímfaktorizáció sorrendtől (és egységektől) eltekintve egyértelmű) Bizonyítás (alaptétel): Belátjuk, hogy ha található egy olyan egész, amelynek a faktorizációja nem egyértelmű, akkor van egy valódi osztója, amelynek a fakt.ja nem egyértelmű. Stb., így végül visszavezethető lenne a probléma egy prím nem egyért. faktorizációjára, ez pedig ellentmondás (az ő osztói csak 1 és önmaga). Legyen tehát n ilyen egész. Ekkor n = p1 ⋅ p2 ⋅ … ⋅ pr = q1 ⋅ q2 ⋅ … ⋅ qs, (i) ahol a prímek nem feltétlenül különbözők, de a 2. felbontás nem csak az első átrendezése. Ekkor q1 | n, azaz q1 osztója a pi-k szorzatának. Az 1. állítás ismételt alkalmazásával található legalább egy olyan pi, amelyre q1 | pi. Feltehető, hogy q1 | p1 (ha kell, átrendezzük a pi-ket). Mivel p1 prím, ezért q1 = p1. Eszerint n / q1 = p2 ⋅ p3 ⋅ … ⋅ pr = q2 ⋅ q3 ⋅ … ⋅ qs. (ii) Mivel az (i) felbontások különbözőek voltak, ezért az (ii) felbontásoknak is különbözőeknek kell lenniük. Így n / q1 valódi osztója n-nek úgy, hogy faktorizációja nem egyértelmű. 9



Prímek és felbonthatatlanok Segédállítás 1.: Legyenek a és b egészek, és legyen g = lnko(a, b). Ekkor találhatók olyan s és t egészek, hogy g = s ⋅ a + t ⋅ b. Példák Legyen a = 21, b = 6; ekkor g = 3 és 3 = 1 ⋅ 21 + (–3) ⋅ 6. De más s és t egészek is jók, hiszen 3 = (–1) ⋅ 21 + 4 ⋅ 6.

Feladat: Más lnko példákkal mutassuk meg, hogy az s és t egészek többféle módon is megválaszthatók! (A segédáll. felhasználásával igazolható az euklideszi állítás) Bizonyítás (Állítás 1. – eml.: ha p | ab, akkor …): Legyen p olyan prím, ami osztója a ⋅ b-nek. Ha p | a, akkor készen vagyunk. Ha nem, akkor lnko(p, a) = 1, hiszen 1 az egyetlen pozitív egész, amely osztja p-t. A segédáll. alapján található olyan s és t, hogy 1 = s ⋅ p + t ⋅ a. Ebből b = s ⋅ p ⋅ b + t ⋅ a ⋅ b. Mivel p | a ⋅ b, ezért mindkét tagot osztja a jobb oldalon, azaz a bal oldalt is. Így tehát ha p nem osztója a-nak, akkor osztója kell, hogy legyen b-nek.

Érdekesség: Az 1. állítást a kevésbé nyilvánvaló segédállítás segítségével igazoltuk 10



Maradékos osztás, euklideszi algoritmus Az 1. segédállításra adható egy elegáns bizonyítás, amely konstruktív is A módszer az euklideszi algoritmus Ez sok faktorizációs és prímtesztelési módszer alapja/része

Maradékos osztás Adott a és 0 ≠ b egészekhez léteznek q, r egészek úgy, hogy a = b ⋅ q + r, ahol 0 ≤ r < |b|, és lnko(a, b) = lnko(b, r).

Bizonyítás (Segédállítás 1. – eml.: g = lnko(a, b)-hez találhatók olyan s és t egészek …): Feltesszük, hogy a és b pozitív. Mint fent, legyen: a = q1 ⋅ b + r1, ahol 0 ≤ r1 < b. (i) Ha r1 = 0, akkor b | a, így az lnko maga b, és válasszuk s = 0-t, t = 1-et. Ha nem, akkor b-t osztjuk maradékosan r1-gyel: b = q2 ⋅ r1 + r2, ahol 0 ≤ r2 < r1. (ii) Ha r2 = 0, akkor megállunk. Ha nem, akkor folytassuk úgy, hogy r1-gyet osztjuk maradékosan: r1 = q3 ⋅ r2 + r3, ahol 0 ≤ r3 < r2. (iii) Az eljárást addig folytatjuk, amíg a maradék 0 nem lesz. (Ez előbb-utóbb biztosan bekövetkezik.) 11



Maradékos osztás, euklideszi algoritmus Bizonyítás (Segédállítás 1.: g = lnko(a, b)-hez találhatók olyan s és t egészek …) (folyt.) Az utolsó két egyenlet: rk – 2 = qk ⋅ rk – 1 + rk, ahol 0 ≤ rk < rk – 1, rk – 1 = qk + 1 ⋅ rk + 0. Az utolsó nem 0 maradék, rk a keresett lnko. Ennek igazolásához lépkedjünk visszafelé: Az utolsó egyenletből rk | rk – 1. Az azelőttiből, mivel rk | rk és rk | rk – 1, ezért rk | rk – 2. … (iii)-ből, mivel rk | r3 és rk | r2, ezért rk | r1. (ii)-ből rk | b, és (i)-ből rk | a. Így rk valóban a és b közös osztója. Legyen d egy másik közös osztó. Mivel d | a és d | b, ezért (i) miatt d | r1. Hasonlóan haladva lefelé, kapjuk, hogy d | r2, r3, …, rk – 1, rk, és így d ≤ rk, azaz rk valóban az lnko. Végül megkeressük s-et és t-t, amivel előáll rk = s ⋅ a + t ⋅ b. (i)-ből r1 = 1 ⋅ a – q1 ⋅ b, itt az együtthatók egészek. (ii)-ből r2 = b – q2 ⋅ r1 = b – q2 ⋅ (a – q1 ⋅ b) = …, az együtthatók egészek. Hasonlóan folytatva lefelé, minden ri felírható a és b egész együtthatókkal képzett szorzatösszegeként. Ezzel a segédállítást beláttuk.

12



Maradékos osztás, euklideszi algoritmus Példa a = 1239, b = 168: 1239 = 7 ⋅ 168 + 63, 168 = 2 ⋅ 63 + 42, 63 = 1 ⋅ 42 + 21, 42 = 2 ⋅ 21 + 0. lnko(1239, 168) = 21. 63 = 1239 – 7 ⋅ 168, 42 = 168 – 2 ⋅ 63 = 168 – 2 ⋅ (1239 – 7 ⋅ 168) = – 2 ⋅ 1239 + 15 ⋅ 168 21 = 63 – 42 = (1239 – 7 ⋅ 168) – (– 2 ⋅ 1239 + 15 ⋅ 168) = 3 ⋅ 1239 – 22 ⋅ 168 Így s = 3, t = – 22.

Az euklideszi algoritmus segítségével a lkkt is meghatározható az lkkt(a, b) = a ⋅ b / lnko(a, b) képlettel Feladatok Igazoljuk ezt az egyenlőséget! Segítség: Használjuk a prímtényezős felírásokat

Megj. (a szélsőségesebb esetek kezeléséhez): lnko(0, 0) = 0, lnko(a, 0) = |a|, lnko(a, b) = lnko(|a|, |b|) Hasonlóan a lkkt-re is 13



Maradékos osztás, euklideszi algoritmus Az algoritmus alap változata

Feladatok Néhány kisebb számmal játsszuk végig az algoritmus lépéseit! (pl. a = 30, b = 18) Mi történik akkor, ha az induláskor b > a? … ha az egyik szám negatív? … ha mindkét szám negatív? … ha az egyik szám 0? … ha mindkét szám 0?

Miért nem teljes faktorizációval számolunk lnko-t (iskolapéldáktól eltekintve, általában)? 14



Maradékos osztás, euklideszi algoritmus Az algoritmus kiterjesztett változata (Donald E. Knuth)

Megjegyzések Elég lenne s és t (c1 és c2) közül csak az egyik meghatározása, mert a másik g = s ⋅ a + t ⋅ b-ből már számolható Az algoritmus működését az garantálja, hogy c1, c2 és d1, d2 mindig kielégíti az a ⋅ c1 + b ⋅ c2 = c és a ⋅ d1 + b ⋅ d2 = d egyenleteket

Feladatok Néhány kisebb számmal játsszuk végig az algoritmus lépéseit! (pl. a = 30, b = 18)

15



Maradékos osztás, euklideszi algoritmus Maple-ben

16



Maradékos osztás, euklideszi algoritmus Matlabban (csak kb. 2^52-ig, utána: Symbolic Math Toolbox)

17



Euklideszi algoritmus – hatékonysági vizsgálat Hatékonysági elemzés (Z Z-ben) (Részletesen lásd: Gács–Lovász és Gathen–Gerhard) Legrosszabb eset: Mikor (milyen számokra) hajtódik végre a legtöbb maradékos osztási lépés? Kulcslépés: a kiterjesztett algoritmusban c div d Ha itt minden hányados 1; azaz: a Fibonacci-számok esetén *Az osztási lépések ℓ száma (f, g) = (fn + 1, fn) Fibonacci-számok esetén l = n − 1 ≈ log Φ 5 g − 1 ≈ 1,441 log g + Ο(1)

Osztási lépések száma és műv. igénye *Az osztási lépések átlagos száma rögzített g és változó f esetén l≈

12(ln 2) 2

log g ≈ 0,584 log g

π2 *Egy osztási lépés (q és r meghatározása) O((λ(a) – λ(b)) ⋅ λ(b)) (szó) műveletet igényel, ahol a > b, és λ(a), λ(b) az a és b számok hossza a gépi repr.ban (pl. λ(a) = [log(a)/64] + 1)

Módosítás a kiterjesztett algoritmusra s és t meghatározására is megadható alkalmas korlát, ami nem „rontja le” az eddigieket

Tétel: Legyen λ(f) = n, λ(g) = m. Ekkor a hagyományos és a kiterjesztett euklideszi algoritmus O(nm) műveletigénnyel hajtható végre. Ha az információt nem tartalmazó tagoktól megszabadulunk, akkor a műv.igény levihető O(n·log2n)-re. Feladat: Hasonlítsuk össze a szükséges osztási lépések számát két Fibonacci-számra és két hasonló nagyságú választott (nem Fibonacci) számra! 18



Fibonacci-sorozat Feladat (Fibonacci, Leonardo Pisano): „Hány pár nyúl származhat egy évben egyetlen (frissen született) pártól, ha minden pár havonta egy új párnak ad életet, amely a 2. hónaptól kezdve lesz tenyészképes, és egy ivadék sem pusztul el?” Megoldás: Az 1. hónapban 0, a 2. hónapban 1, a 3. hónapban 1, a 4. hónapban 1 + 1 = 2, az 5. hónapban 1 + 1 + 1 = 3, a 6. hónapban 1 + 1 + 1 + 2 = 5, … új nyúlpár születik.

A nyúlpárok száma az n. hónapban: az (n – 1). hónapban élő nyúlpárok száma + az (n – 2). hónapban élő nyúlpárok száma (ezek utódai születnek meg) Fibonacci-sorozat: 1, 1, 2, 3, 5, 8, 13, 21, 34, … fn = fn – 1 + fn – 2, ahol f1 = f2 = 1. n−2 Feladatok Igazoljuk, hogy f n = 1 + ∑ f i i =1

Útmutató: Fejtsük ki rekurzívan a képletben a bal oldali tagot!

n

2 *Szemléletesen ellenőrizzük, majd igazoljuk, hogy érvényes ∑ f i = f n f n +1 i =1

Útmutató: Ez fn = fn + 1 – fn – 1-ből adódik, végigszorozzuk a bal oldallal, majd kifejtjük

19



Fibonacci-sorozat Rutin Maple-ben

20



Fibonacci-sorozat VBA rutin

21



Fibonacci-sorozat Generátorfüggvénnyel

22



Euklideszi algoritmus és lánctörtek Az euklideszi algoritmus fenti a = q1 ⋅ b + r1, ahol 0 ≤ r1 < b, b = q2 ⋅ r1 + r2, ahol 0 ≤ r2 < r1, r1 = q3 ⋅ r2 + r3, ahol 0 ≤ r3 < r2, ... rk – 2 = qk ⋅ rk – 1 + rk, ahol 0 ≤ rk < rk – 1, rk – 1 = qk + 1 ⋅ rk + 0 lépéseit írjuk át a következő módon: a / b = q1 + r1 / b, b / r1 = q2 + r2 / r1, r1 / r2 = q3 + r3 / r2, … rk – 2 / rk – 1 = qk + rk / rk – 1, rk – 1 / rk = qk + 1. Helyettesítsünk be az egymást követő egyenletekbe: a / b = q1 + 1 / (q2 + r2 / r1) stb. Ezzel igazoltuk a következőt: a 1 = q1 + Állítás: Az a/b racionális szám a fenti megadás szerint felírható b 1 q2 + 1 alakban. Ezt a formát lánctört alaknak nevezzük. q3 + ... qk +1 Példa 1239 1 1 1 59 a = 1239, b = 168:

168

=7+

2+

=7+

1 1+

1 2

1 2+ 3/ 2

=7+

8/3

=

8

23



Lánctörtek Feladat: Állítsuk elő egy általunk kedvelt környezetben néhány racionális szám lánctörtes alakját! Eml. (előző példánk):

Szemléltetés Excelben

1239 1 = 7+ 1 168 2+ 1+

=7+ 1 2

1 2+

1 3/ 2

=7+

1 59 = 8/3 8

24



Lánctörtek A lánctörtes előállítás irracionális számokra is értelmezhető, bár ekkor a felírás nem lesz véges Minden irr. számhoz létezik olyan lánctört, amelynek kezdeti részlettörtjei olyan sorozatot alkotnak, amely a számhoz tart

Az algoritmus (lánctörtbe alakítás) Legyen b0 = [x] (egészrész), x1 = {x} (törtrész), ahol x = b0 + x1 Ha x1 ≠ 0, akkor legyen b1 = [1/x1], x2 = {1/x1}, ahol x = b0 + x1 = b0 + 1/(b1 + x2) Ha x2 ≠ 0, akkor legyen b2 = [1/x2], x3 = {1/x2} ... Ha xn ≠ 0, akkor legyen bn = [1/xn], és xn + 1 = {1/xn} helyett legyen 0/1

A lánctört visszaalakítása egyszerű törtté Írjuk az xk törtrészeket a visszaalakítási sorozatban xk = pk/qk alakba! A pn + 1 = 0 és qn + 1 = 1 értékekből kiindulva a közös nevezőre hozás a pk = qk + 1, qk = bkqk + 1 + pk + 1, k = n, n − 1, …, 1, 0 sorozatot eredményezi, amelynek végén a q0/p0 hányados adja x tört alakú közelítését

Feladatok Állítsuk elő néhány irracionális szám lánctört alakját (vizsgáljunk meg híres konstansokat is: 2 , e, pi)! Találunk szabályosságokat? *Mi lehet a szabályosságok oka? 25



Lánctörtek A pi lánctörtes alakja (közelítés)

26



Lánctörtek A

2

és az e lánctörtes alakja

27



Lánctörtek Nevezetes számok lánctörtes alakja A G2 = G + 1 egyenlet G = 1+ 5 megoldására: 1 + / 1, 1, 1, 1, … / 2 2 : 1 + / 2, 2, 2, 2, … / 3: 1 + / 1, 2, 1, 2, 1, 2, … / 3 2 : 1 + / 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, 3, 2, 1, 3, 4, … / e: 2 + / 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, … / tg(1): 1 + / 1, 1, 3, 1, 5, 1, 7, 1, 9, 1, 11, 1, … / pi: 3 + / 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, … /

Állítás: Ha egy valós szám lánctörtes kifejtése valahonnan periodikus (eventually periodic), akkor ez a szám egy másodfokú polinom gyöke Az állítás megfordítása is igaz (Lagrange, 1770) (Igazolásokat lásd: Knuth)

Magasabb fokú algebrai számok és transzcendens számok általában nem mutatnak szabályosságot Kivétel pl.: e (és vele „szoros” kapcsolatban levő számok, lásd: Knuth)

*Feladat: Írjunk programot nevezetes konstansok lánctörtkifejtésének több ezer/tízezer jegyig történő meghatározására! Próbáljunk szabályosságokat keresni!

28



Lánctörtek Megvalósítás a Matlab és a Maple rendszerekben

29



Lánctörtek Megvalósítás a Matlab és a Maple rendszerekben (folyt.)

30



További érdekes feladatok* A pitagoraszi számhármasok feladatának általánosítása a Waring-problémakör Állítás: Létezik n-től független g(n) egész szám, hogy bármely n előáll legfeljebb g(n) darab n-edik hatvány összegeként Tétel: Minden n szám előáll legfeljebb 4 négyzetszám összegeként

Pl. g(3) = 9, g(4) = 19, g(5) = 37 stb. Írjunk programot néhány g(n) érték tapasztalati meghatározására és végezzünk ilyen vizsgálatokat! Illusztráció: Kis n értékekre lényegében triviális előállításokat kapunk harmadik hatványok összegeként 2 = 13 + 13 3 = 13 + 13 + 13 …

7 = 13 + 13 + 13 + 13 + 13 + 13 + 13 8 = 13 + 13 + 13 + 13 + 13 + 13 + 13 + 13 = 23 9 = 13 + 13 + 13 + 13 + 13 + 13 + 13 + 13 + 13 = 23 + 13 10 = 23 + 13 + 13 11 = 23 + 13 + 13 + 13 …

15 = 23 + 13 + 13 + 13 + 13 + 13 + 13 + 13 16 = 23 + 13 + 13 + 13 + 13 + 13 + 13 + 13 + 13 = 23 + 23 …

24 = 23 + 23 + 23 31



Történeti áttekintés Euklidesz Nagy görög matematikus, Kr. e. 300 körül, főműve az „Elemek” (13 könyv, geometria, aritmetika) Algoritmus: 7. könyvben (nagyon vsz., hogy már előtte is ismert volt) Ez az első „modern” algoritmus (amely lényegében ma is használatos)

Lánctörtek Már az ókori görögöknél ismertek, sőt, először így definiálták az irracionális (valós) számokat A lánctörtes e-kifejtés tulajdonságait Euler igazolta 1731-ben

A pi fontos tulajdonságainak igazolása Irracionális – Lambert (1766) [Hermite (1873) – e transzcendens] Transzcendens – Lindemann (1882; azaz: a kör nem négyszögesíthető) Nem Liouville-szám – Mahler (1953)

(Egyéb nevezetes számok irracionalitásának igazolása 2 , 3 stb.: már az ókori görögöknél 3

2 : kockakettőzés, déloszi probléma)

Bár az ókori görögök mély tudással rendelkeztek az irrac. számokról, a modern elméletet csak a 19. században dolgozták ki (Dedekind) 32



Történeti áttekintés Fibonacci Itáliai matematikus (12–13. sz.), fontos műve a Liber Abaci (Könyv az abakuszról), ebben összegyűjtött és általa kiegészített aritmetikai és algebrai ismereteket ír le

Az euklideszi alg. hatékonyságának vizsgálata a Fibonacci-sor első gyakorlati alkalmazása volt Pierre Fermat 17. századi francia matematikus és fizikus (csak „szabadidős” matematikus) Kúpszeletek elmélete, szép számelméleti tételek Fermat-prímek (lásd köv. slidesor)

„Nagy Fermat-tétel”: xn + yn = zn-nek n ≥ 3-ra nincs 0-tól különböző megoldása Igazolás: „lapszéli jegyzeten” n = 4: Fermat n = 3: Euler n = 5: Dirichlet (1825) n ≤ 100: Kummer (1847-) … (!)

Waring-problémakör (1700-as évek 2. fele: Lagrange – minden egész szám előáll legfeljebb 4 négyzetszám összegeként) 1700-as évek vége: Waring észrevette a szabályosságot (akkor: sejtés) Hilbert igazolta általánosan 1909-ben Külön köszönet: Pusztai P. és dr. Szörényi M. kollégáimnak

33



Ajánlott irodalom David M. Bressoud: Factorization and Primality Testing, Springer, New York, 1989 Geddes, Czapor, Labahn: Algorithms for Computer Algebra (6th pr./ed.), Kluwer Acad. Press, Boston, 1999 Joachim Gathen, Jürgen Gerhard: Modern Computer Algebra (3rd ed.), Cambridge Univ. Press, 2013 Donald E. Knuth: A számítógép-programozás művészete 2. (2. kiadás), Műszaki Könyvkiadó, Budapest, 1994 Gács Péter, Lovász László: Algoritmusok, Tankönyvkiadó, Budapest, 1978– (több kiadás) Gerőcs László: A Fibonacci-sorozat általánosítása, Tankönyvkiadó, Budapest, 1988 Szörényi Miklós, Kallós Gábor: Mérnöki számítások, jegyzet és órai segédanyagok (Excel és Matlab rész), SZE, 2013–2014 Sain Márton: Matematika-történeti ábécé, Tankönyvkiadó, Budapest, 1974 Maple User Manual, Maplesoft, 2013 Matlab Symbolic Math Toolbox User’s Guide, MathWorks, 2013 34

3. előadás Prímtulajdonság, lnko, Euklideszi algoritmus, lánctörtek

Recommend Documents