Az euklideszi algoritmusról

Az euklideszi algoritmusról

Az euklideszi algoritmusról Ivanyos Gábor

2012 március 12


Fazekas 196977

Seress Ákos, IG


Elekes György

Tablókép Tanárok a 70-es évekb®l

Surányi László gy¶jteményéb®l


ELTE 197883

Lovász László

Pelikán József


MTA SZTAKI 1983

Turchányi Gyula

iwiw


MTA SZTAKI 1991; BME 1992

Babai László

cs.uhicago.edu

Sántha Miklós

Az euklideszi algoritmusról Algoritmus Mi az?

Algoritmus - mi is az

(számítási) módszer, eljárás



(számítási) módszer, eljárás (számítógépes) program, programrészlet "lényege"



(számítási) módszer, eljárás (számítógépes) program, programrészlet "lényege" Rokonok:

geometriai szerkesztés stratégia játékban, Rubik-kocka kirakása, papírhajtogatás, kijutás labirintusból, stb... konyhai vagy kémiai recept (pl. aranycsinálás) összeszerelési útmutató (pl. bútoré), gyártási eljárás, stb...

Az euklideszi algoritmusról Algoritmus Névadó

Algoritmus - a névadó Abu Dzsafar Muhammed ibn Musza

al-Khwarizmi



Khwarezm:

tartomány

⊂

al-Khwarizmi

Kelet-Perzsia (ma Üzbegisztán)



Khwarezm:

tartomány

⊂

al-Khwarizmi


Élt kb. 780850-ig Bagdadban



Khwarezm:

tartomány

⊂

al-Khwarizmi



Harun al-Rashid uralkodása: 786809



Khwarezm:

tartomány

⊂

al-Khwarizmi



Harun al-Rashid uralkodása: 786809 Egy könyve latin átiratának (12. sz.) címe az els® két szava után: Dixit Algorizmi

=

Al Khwarizmi mondta



Khwarezm:

tartomány

⊂

al-Khwarizmi




=

Al Khwarizmi mondta

Másik cím: Algoritmi de numero Indorum



Khwarezm:

tartomány

⊂

al-Khwarizmi




=

Al Khwarizmi mondta


≈

Al Khwarizmi a hindu számolás m¶vészetér®l



Khwarezm:

tartomány

⊂

al-Khwarizmi




=

Al Khwarizmi mondta


≈

Al Khwarizmi a hindu számolás m¶vészetér®l



Khwarezm:

tartomány

⊂

al-Khwarizmi




=

Al Khwarizmi mondta


≈

Al Khwarizmi a hindu számolás m¶vészetér®l A tízes számrendszerben történ® (hindu eredet¶) számolásról (≈ az iskolában tanult módszerek)

Az euklideszi algoritmusról Algoritmus Az iskolai számolási módszerekr®l

A helyiértékes számábrázolásról

Lehet®vé teszi igen nagy számok leírását



Lehet®vé teszi igen nagy számok leírását és a velük való számolást



Lehet®vé teszi igen nagy számok leírását és a velük való számolást Egy 100 jegy¶ szám akkora, ameddig el sem tudunk számlálni




Az univerzum atomjainak a száma: 1078 és 1082 között




Az univerzum atomjainak a száma: 1078 és 1082 között Az univerzum kora: < 1018 másodperc




Az univerzum atomjainak a száma: 1078 és 1082 között Az univerzum kora: < 1018 másodperc Várható leggyorsabb számítógép 2020-ban: 1018 lebeg®pontos m¶velet/másodperc


Az iskolai módszerek költsége

a, b :

n jegy¶ számok: n

≈ log10 a



a, b : a

+b

n jegy¶ számok: n és a

−b

≈ log10 a

számolása: n -nel arányos



a, b : a

+b


−b

≈ log10 a


számú m¶velet számjegyekkel



a, b : a

+b


−b

≈ log10 a



a · b és a

:b

2

számolása: n -tel arányos



a, b : a

+b


−b

≈ log10 a



a · b és a

:b

2

számolása: n -tel arányos

(vannak elvileg gyorsabb szorzó-osztó módszerek; ezek csak nagyon nagy számokra jobbak a gyakorlatban )

Az euklideszi algoritmusról Euklidesz Elemek

Az euklideszi algoritmus - lel®hely Euklidesz: Elemek (Sztoicheia) (Alexandria, kb. i.e. 300)



Az Elemek 7. (és 11.) könyvében szerepel az eukl. alg.



Az Elemek 7. (és 11.) könyvében szerepel az eukl. alg. Jó on-line kiadás: David Joyce "fordítása": http://aleph0.clarku.edu/∼djoyce/java/elements/elements.html

(a kép forrása: Bill Casselman:

http://www.math.ubc.ca/∼cass/Euclid/papyrus/papyrus.html)

Az euklideszi algoritmusról Euklidesz A legnagyobb közös osztó

A legnagyobb közös osztó

Legnagyobb közös osztó tényez®

∼

a legnagyobb közösen kiemelhet®




Deníció:

∼





Deníció:

legyenek a, b

∼


>0

egészek




Deníció: lnko(a, b )

legyenek a, b

=a

∼


>0

egészek

legnagyobb olyan d

>0

egész, amelyre d |a és d |b .

Kiszámolható törzstényez®s felbontás segítségével




Deníció: lnko(a, b )

legyenek a, b

=a

∼


>0

egészek

legnagyobb olyan d

>0

egész, amelyre d |a és d |b .

Kiszámolható törzstényez®s felbontás segítségével Ez rossz esetben igen lassú

Az euklideszi algoritmusról Euklidesz Nagy N törzstényez®s felbontása nehéz

Nagy

N törzstényez®s felbontása nehéz (?) Érdemi rész: valódi osztó keresése


Nagy


M |N esetén tovább M és N /M felbontásával


Nagy


M |N esetén tovább M és N /M felbontásával Naiv módszer:

√

N -ig próbálkozás (osztás):


Nagy



√

N -ig próbálkozás (osztás): √ 200-nál több jegy¶ N -re N > 10100 , ennyi

Naiv módszer:

id®nk nincs!


Nagy



√

N -ig próbálkozás (osztás): √ 200-nál több jegy¶ N -re N > 10100 , ennyi id®nk nincs! Nem ismert (log N )1000 -nel arányos idej¶ módszer sem Naiv módszer:


Nagy



√


Feltételezett nehézség kihasználása: RSA titkosírás


Nagy



√



2007-ig díjak kit¶zve nagy konkrét N-ek felbontására


Nagy



√



2007-ig díjak kit¶zve nagy konkrét N-ek felbontására Felbontó projektek: számítógépek önkéntes hálózatán+szuperszámítógépeken


Nagy



√



2007-ig díjak kit¶zve nagy konkrét N-ek felbontására Felbontó projektek: számítógépek önkéntes hálózatán+szuperszámítógépeken 2009-es rekord: 235 jegy¶ szám felbontása (két kb. 120 jegy¶ prímszám szorzata)


Az lnko a legjobb felbontó algoritmusokban

a munka nehéz része: keressünk olyan N -nél kisebb M -et, amelyre lnko(N , M )

>1




>1

a próbálgatásnál sokkal okosabb és gyorsabb módszerek vannak "szerencsés" M keresésére




>1

a próbálgatásnál sokkal okosabb és gyorsabb módszerek vannak "szerencsés" M keresésére "szerencsés" M birtokában az euklideszi algoritmussal kiszámoljuk lnko(N , M )-et




>1

a próbálgatásnál sokkal okosabb és gyorsabb módszerek vannak "szerencsés" M keresésére "szerencsés" M birtokában az euklideszi algoritmussal kiszámoljuk lnko(N , M )-et lnko(M , N ) valódi osztója N -nek

Az euklideszi algoritmusról Az euklideszi algoritmus Az algoritmus

Az euklideszi algoritmus alapötlete

Legyenek a és b egészek.

Észrevétel:

Ha d közös osztója a-nak és b -nek, akkor d közös

osztója a-nak és b

± a-nak.




Észrevétel:



± a-nak.

Biz.: Tegyük fel, hogy b

= db0 ,

a

= da0 .

Ekkor b

± a = d (b 0 ± a 0 ).




Észrevétel:



± a-nak.


= db0 ,

Következmény: {a és b

a

= da0 .

közös osztói}

Ekkor b

= {a

és b

± a = d (b 0 ± a 0 ). −a

közös osztói}




Észrevétel:



± a-nak.


= db0 ,

Következmény: {a és b Következmény:

a

= da0 .

közös osztói}

lnko(a, b )

Ekkor b

= {a

= lnko(a, b − a).

és b

± a = d (b 0 ± a 0 ). −a

közös osztói}


Az euklideszi algoritmus - elegáns változat Tudjuk:

b

>a

esetén lnko(a, b )

= lnko(a, b − a)



b

>a

esetén lnko(a, b )

= lnko(a, b − a)

Ciklus: Feltételek: 0

≤a≤b

egészek



b

>a

esetén lnko(a, b )

= lnko(a, b − a)

Ciklus: Feltételek: 0 (1) Ha a

= 0,

≤a≤b

egészek

akkor kész; az eredmény b .



b

>a

esetén lnko(a, b )

= lnko(a, b − a)


= 0,

(2) Legyen b

≤a≤b

egészek


←− b − a



b

>a

esetén lnko(a, b )

= lnko(a, b − a)


= 0,

(2) Legyen b (3) Ha a

≤a≤b


←− b − a

> b,

egészek

akkor a

←→ b



b

>a

esetén lnko(a, b )

= lnko(a, b − a)


= 0,


≤a≤b


←− b − a

> b,

egészek

akkor a

Újra (1)-t®l.

←→ b


Az euklideszi algoritmus - elegáns változat


= 0,


≤a≤b


←−

> b,

egészek

b

−a

akkor a

Újra (1)-t®l.

←→ b


Az euklideszi algoritmus - eredeti változat


= 0,

←→ b

egészek


(2') Ameddig b (3') a

≤a≤b

≥ a,

Újra (1)-t®l.

legyen b

←−

b

−a


Az eredeti változat lassú lehet

(2') Ameddig b

≥ a,

legyen b

←−

b

−a



(2') Ameddig b

≥ a,

legyen b

←−

b

−a

El®fordulhat, hogy a sokkal kisebb lesz, mint b



(2') Ameddig b

≥ a,

legyen b

←−

b

−a

El®fordulhat, hogy a sokkal kisebb lesz, mint b Például a

≈

√

b és b 200 jegy¶



(2') Ameddig b

≥ a,

legyen b

←−

b

−a


≈

√

b és b 200 jegy¶ 100 kivonás lenne Ekkor kb. b /a ≈ 10



(2') Ameddig b

≥ a,

legyen b

←−

b

−a


≈

√

b és b 200 jegy¶ 100 kivonás lenne Ekkor kb. b /a ≈ 10 Ez reménytelenül sok!


Az euklideszi algoritmus - eredeti változat


= 0,

←→ b

egészek

akkor kész; az eredmény a.

(2') Ameddig b (3') a

≤a≤b

≥ a,

Újra (1)-t®l.

legyen b

←−

b

−a


Az euklideszi algoritmus - maradékos osztással


= 0,

(2) Legyen b (3') a

←→ b

≤a≤b

egészek


←− b%a

Újra (1)-t®l.

(b%a = b − abb/ac)

Az euklideszi algoritmusról Az euklideszi algoritmus Elemzés

Az euklideszi algoritmus elemzése Jelölés:

a` , b` az "a, b " értéke

`

lépés után.

(Mostantól a, b az eredeti (a bemen®) a, b -t jelöli!)




`

lépés után.


a0

= a,

b0

=b




`

lépés után.


a0

= a,

b0

Feltétel:

=b < a` ≤ b`

0




`

lépés után.


a0

= a,

b0

=b

Feltétel: 0 < a` ≤ b` Egy lépés eredménye:

a`+1




`

lépés után.


a0

= a,

b0

=b


a`+1

= b` %a`




`

lépés után.


a0

= a,

b0

=b


a`+1

= b` %a` < a` ,




`

lépés után.


a0

= a,

b0

=b

Feltétel: 0 < a` ≤ b` Egy lépés eredménye: a`+1

< a` ,

a`+1

= b` %a` < a` ,

tehát el®bb-utóbb véget ér

b`+1

= a` .




`

lépés után.


a0

= a,

b0

=b


< a` ,

a`+1

= b` %a` < a` ,


Két lépés után (ha a`+1 6= 0): a`+2

b`+1

= a` .




`

lépés után.


a0

= a,

b0

=b


< a` ,

a`+1

= b` %a` < a` ,



=

b`+1 %a`+1

b`+1

= a` .




`

lépés után.


a0

= a,

b0

=b


< a` ,

a`+1

= b` %a` < a` ,



=

b`+1 %a`+1

=

a` %a`+1

b`+1

= a` .




`

lépés után.


a0

= a,

b0

=b


< a` ,

a`+1

= b` %a` < a` ,



=

b`+1 %a`+1

=

a` %a`+1

≤

a`

− a`+1

b`+1

= a` .




`

lépés után.


a0

= a,

b0

=b


< a` ,

a`+1

= b` %a` < a` ,



Tehát a`+2

≤ a` − a`+1 ,

=

b`+1 %a`+1

=

a` %a`+1

≤

a`

− a`+1

b`+1

= a` .




`

lépés után.


a0

= a,

b0

=b


< a` ,

a`+1

= b` %a` < a` ,

b`+1



Tehát a`+2

≤ a` − a`+1 ,

=

b`+1 %a`+1

=

a` %a`+1

≤

a`

azaz a`

− a`+1

≥ a`+1 + a`+2 .

= a` .


Az euklideszi algoritmus elemzése

El®z® oldalról: a`

≥ a`+1 + a`+2 .



El®z® oldalról: a` Innen a`

≥ a`+1 + a`+2 .

≥ a`+1 + a`+2 ≥ a`+2 + a`+2 = 2a`+2 ,




≥ a`+1 + a`+2 .

≥ a`+1 + a`+2 ≥ a`+2 + a`+2 = 2a`+2 ,

Azaz: a`+2

≤

1 2 a` .




≥ a`+1 + a`+2 .

≥ a`+1 + a`+2 ≥ a`+2 + a`+2 = 2a`+2 ,

Azaz: a`+2

≤

1 2 a` .

a` két lépésben felez®dik (vagy még kisebb lesz)




≥ a`+1 + a`+2 .

≥ a`+1 + a`+2 ≥ a`+2 + a`+2 = 2a`+2 ,

Azaz: a`+2

≤

1 2 a` .

a` két lépésben felez®dik (vagy még kisebb lesz) 1 Ebb®l: a2` ≤ ` a0 . 2




≥ a`+1 + a`+2 .

≥ a`+1 + a`+2 ≥ a`+2 + a`+2 = 2a`+2 ,

Azaz: a`+2

≤

1 2 a` .

a` két lépésben felez®dik (vagy még kisebb lesz) 1 Ebb®l: a2` ≤ ` a0 . 2 Innen: a ciklus lefutásainak száma

≤ 2 · log2 a = konstans · log10 a




≥ a`+1 + a`+2 .

≥ a`+1 + a`+2 ≥ a`+2 + a`+2 = 2a`+2 ,

Azaz: a`+2

≤

1 2 a` .

a` két lépésben felez®dik (vagy még kisebb lesz) 1 Ebb®l: a2` ≤ ` a0 . 2 Innen: a ciklus lefutásainak száma

≤ 2 · log2 a = konstans · log10 a

Összköltség:

(log10 a)3 -nel

arányos


Pontosabb elemzés: a Fibonacci-számok Tudjuk:

a`+2

≤ a` − a`+1 ,


Pontosabb elemzés: a Fibonacci-számok Tudjuk: a`

a`+2

≤ a` − a`+1 ,

≥ a`+1 + a`+2

azaz



a`+2

≤ a` − a`+1 ,

azaz

≥ a`+1 + a`+2

Leglassabban csökken, ha egyenl®ség teljesül:

a`

= a`+1 + a`+2



a`+2

≤ a` − a`+1 ,

azaz

≥ a`+1 + a`+2


a`

= a`+1 + a`+2

a Fibonacci-sorozat rekurziója, csak fordítva indexelve



a`+2

≤ a` − a`+1 ,

azaz

≥ a`+1 + a`+2


a`

= a`+1 + a`+2

a Fibonacci-sorozat rekurziója, csak fordítva indexelve Fibonacci-számok: F1

= 1,

F2

= 2,



a`+2

≤ a` − a`+1 ,

azaz

≥ a`+1 + a`+2


a`

= a`+1 + a`+2

a Fibonacci-sorozat rekurziója, csak fordítva indexelve Fibonacci-számok: F1

= 1,

F2

= 2,

F`

= F`−2 + F`−1 (` > 2)



a`+2

≤ a` − a`+1 ,

azaz

≥ a`+1 + a`+2


a`

= a`+1 + a`+2

a Fibonacci-sorozat rekurziója, csak fordítva indexelve Fibonacci-számok: F1 Belátható, hogy a`

= 1, 1

F2

≤ F`+1 a0 .

= 2,

F`

= F`−2 + F`−1 (` > 2)

Az euklideszi algoritmusról Lánctörtek Lánctörtfejtés

Lánctörtbe fejtés Elemek 11. könyv: Euklideszi algoritmus tetsz®leges 0 (1) b

←− b − a · bb/ac

(2) Ha b

= 0,

< a ≤ b-re

akkor kész.

(3) Különben b

←→ a

és folytatjuk (1)-t®l



←− b − a · bb/ac

(2) Ha b

= 0,

< a ≤ b-re

akkor kész.

(3) Különben b

γ = b/a-val

←→ a




←− b − a · bb/ac

(2) Ha b

= 0,

< a ≤ b-re

akkor kész.

(3) Különben b

←→ a


γ = b/a-val (1)

γ ←− {γ}

(2) Ha

γ = 0,

(3) Különben

akkor kész

γ ←− 1/γ



Lánctörtbe fejtés

Az el®z® eljárás átszervezve és tartalommal megtöltve

(1) (*)

γ = bγc + {γ}

(2) Ha

feljegyezzük

{γ} = 0,

bγc-t

akkor kész

(3) Különben folytatjuk

γ

helyett 1/{γ}-val

Az euklideszi algoritmusról Lánctörtek

sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

1

+


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

1

+

1

γ1


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

1

+

1

γ1

1

=1+ 2

+


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

1

+

1

γ1

1

=1+ 2

+

1

γ2


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

1

+

1

γ1

1

=1+ 2

+

1

γ2

1

=1+ 2

1

+ 2

+


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

1

+

1

γ1

1

=1+ 2

+

1

γ2

1

=1+ 2

1

+ 2

+

1

γ3


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

=

1

1

+

1

γ1

1

=1+ 2

+

1

γ2

1

+ 2

1

+ 2

1

+ 2

+

1

γ4

1

=1+ 2

1

+ 2

+

1

γ3


sqrt (2)

Példa:

√

√

2

2 lánctört alakja

=γ =

=

1

1

+

1

γ1

1

=1+ 2

+

1

γ2

1

+ 2

2

2

1

+ 2

+

+

1

γ4

1

γ3 1

2

1

+

2

=1+

1

+

1

=1+

1

+ 2

1

+ 2

+

1 2

+ ···


√

sqrt (2)

2 lánctört alakja - bizonyítás Trükk:

√

2 helyett 1

+

√

2-re bizonyítunk.


√

sqrt (2)


√

Legyen x

2 helyett 1

+

√

2-re bizonyítunk. 1

=2+ 2

1

+ 2

1

+ 2

+

1 2

+ ···


√

sqrt (2)


√

Legyen x

2 helyett 1

+

√


=2+ 2

1

+ 2

1

+ 2

Be kéne látni, hogy x

+

=1+

1 2

√

+ ···

2.


√

sqrt (2)


√

Legyen x

2 helyett 1

+

√


=2+ 2

1

+ 2

1

+ 2


Észrevétel: x

+

=1+

= 2 + x1 ,

1 2

√

+ ···

2.


√

sqrt (2)


√

Legyen x

2 helyett 1

+

√


=2+ 2

1

+ 2

1

+ 2


amib®l x

2

=1+

= 2 + x1 , = 2x + 1.

Észrevétel: x

+

1 2

√

+ ···

2.


√

sqrt (2)

2 lánctört alakja - bizonyítás x olyan pozitív szám, amelyre x

2

= 2x + 1


√

sqrt (2)


x

2

2

= 2x + 1

− 2x + 1 = 2

(x − 1)2 = 2 √ x −1=± 2 √ x =1± 2

1

−

√

2 negatív, tehát


√

sqrt (2)


x

2

2

= 2x + 1

− 2x + 1 = 2

(x − 1)2 = 2 √ x −1=± 2 √ x =1± 2

1

x

=1+

√

2.

−

√

2 negatív, tehát

Az euklideszi algoritmusról Lánctörtek Periodicitás

Véges és periodikus lánctörtek γ

lánctörtalakja véges

⇔γ

racionális




Periodikus lánctört:

⇔γ √

2 vagy pl.

1

1+

racionális

1

2+

1

3+

1

4+

1

3+

1

4+ 3+

1 4 + ···




Periodikus lánctört:

⇔γ √

2 vagy pl.

1

1+

racionális

1

2+

1

3+

1

4+

1

3+

1

4+ 3+

Tétel: γ

1 4 + ···

lánctörtalakja periodikus

⇔γ

pozitív kvadratikus

szám: egy racionális együtthatós másodfokú egyenlet pozitív gyöke


√

Közelítés

2 közelítése csonkított lánctörtekkel

√

1

+

1 2

2

≈ 1.41421

=

3 2

= 1.50000


√

Közelítés


√

1

2

≈ 1.41421

1

+ 2

+

1 2

=

7 5

= 1.40000


√

Közelítés


√

1

2

≈ 1.41421

1

+ 2

=

1

+ 2

+

1 2

17 12

≈ 1.41666


√

Közelítés


√

1

2

≈ 1.41421

1

+ 2

=

1

+ 2

1

+ 2

+

1 2

41 29

≈ 1.41379


√

Közelítés

2 közelítése csonkított lánctörtekkel √

1

2

≈ 1.41421

1

+ 2

=

1

+ 2

=

=≈ 1.41428

1

+ 2

Nicsak:

70

1

+ 2

99 70

99

+

1 2

297 210 és 210x297mm: az A4-es lap mérete

Az euklideszi algoritmusról Lánctörtek Aranymetszés

A leglassabban közelít® lánctört

1

+

1 1

=

2 1

=2



1

1

+ 1

+

1 1

=

3 2

= 1.5



1

1

+ 1

=

1

+ 1

+

1 1

5 3

≈ 1.66666



1

1

+ 1

=

1

+ 1

1

+ 1

+

1 1

8 5

= 1.60000



1

1

+ 1

=

1

+ 1

1

+ 1

1

+ 1

+

1 1

13 8

= 1.62500



1

1

+ 1

=

1

+ 1

1

+ 1

1

+ 1

1

+ 1

+

1 1

21 13

≈ 1.61538



1

1

+ 1

=

1

+ 1

1

+ 1

1

+ 1

1

+ 1

1

+ 1

+

1 1

34 21

≈ 1.61905



1

1

+ 1

=

1

+ 1

1

+ 1

1

+ 1

1

+ 1

1

+ 1

1

+ 1

+

1 1

55 34

≈ 1.61765



1

1

+ 1

=

1

+ 1

1

+ 1

1

+ 1

1

+ 1

1

+ 1

1

+ 1

1

+ 1

+

1 1

89 55

≈ 1.61818


Arany téglalap φ

1

1

φ−1

1

φ

1

=

1 φ−1


e

Az

lánctört alakja

e szám lánctört-alakja e

1

=2+ 1

1

+ 2

1

+ 1

1

+ 1

1

+ 4

1

+ 1

1

+ 1

1

+ 6

1

+ 1

1

+ 1

+

1 8

+ ...

Az euklideszi algoritmusról Kiegészítések A Fibonacci-spirál

A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál


A Fibonacci-spirál

Az euklideszi algoritmusról Kiegészítések A kiegészített euklideszi algoritmus

Az lnko egy fontos tulajdonsága Tétel:

Legyenek 0

{ax + by

< a, b

egészek. Ekkor

alakú számok (x , y egészek)}

= {lnko(a, b)

többszörösei} .



Legyenek 0

{ax + by

< a, b

egészek. Ekkor


Biz.: ⊆ könny¶:

= {lnko(a, b)

ha d osztója a, b -nek, akkor ax

többszörösei} .

+ by -nak

is.



Legyenek 0

{ax + by

egészek. Ekkor


Biz.: ⊆ könny¶: ⊇,

< a, b

= {lnko(a, b)


azaz lnko(a, b ) el®áll ax

+ by

alakban:

többszörösei} .

+ by -nak

is.



Legyenek 0

{ax + by

egészek. Ekkor



< a, b

= {lnko(a, b)



+ by

többszörösei} .

+ by -nak

is.

alakban:

Azért, mert az euklideszi algoritmus során örökl®dik, hogy a közbüls® értékek (a` , b` ) ax

+ by

alakúak.



Legyenek 0

{ax + by

egészek. Ekkor



< a, b

= {lnko(a, b)



+ by

többszörösei} .

+ by -nak

is.

alakban:

Azért, mert az euklideszi algoritmus során örökl®dik, hogy a közbüls® értékek (a` , b` ) ax

+ by

alakúak.

Kiegészített euklideszi algoritmus:

Az eukl. algoritmust

kiegészítjük a közbüls® számok (a` , b` ) el®állításával ax alakban.

+ by


Példa:

a = 8, b = 13

8x + 13 · 0


Példa:

a = 8, b = 13

8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13

8x + 13 · 2 8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13

8x + 13 · 3 8x + 13 · 2 8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13

8x + 13 · 4 8x + 13 · 3 8x + 13 · 2 8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13

8x + 13 · 5 8x + 13 · 4 8x + 13 · 3 8x + 13 · 2 8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13

8x + 13 · 6 8x + 13 · 5 8x + 13 · 4 8x + 13 · 3 8x + 13 · 2 8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6 8x + 13 · 5 8x + 13 · 4 8x + 13 · 3 8x + 13 · 2 8x + 13 · 1 8x + 13 · 0


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6 8x + 13 · 5 8x + 13 · 4 8x + 13 · 3 8x + 13 · 2 8x + 13 · 1


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6 8x + 13 · 5 8x + 13 · 4 8x + 13 · 3 8x + 13 · 2


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6 8x + 13 · 5 8x + 13 · 4 8x + 13 · 3


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6 8x + 13 · 5 8x + 13 · 4


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6 8x + 13 · 5


Példa:

a = 8, b = 13 8x + 13 · 7 8x + 13 · 6


Példa:

a = 8, b = 13 8x + 13 · 7


Példa:

a = 8, b = 13

Az euklideszi algoritmusról Kiegészítések Az euklideszi játék

Az euklideszi játék (ColeDavie 1969)

Adott két egész hosszúságú madzag és 2 játékos, akik felváltva lépnek.




Egy lépés: a hosszabbik madzagból levágjuk a rövidebb egy többszörösét legalább 1-szeresét azért még maradjon valamennyi





Vesztes: kap).

aki nem tud lépni (azaz aki két egyforma madzagot





Vesztes:

aki nem tud lépni (azaz aki két egyforma madzagot

kap).

Kérdés:

a kezdeti hosszúságoktól függ®en a kezd®nek mikor

van nyer® stratégiája?

Az euklideszi algoritmusról

Recommend Documents