27
ˇ Ret ˇ ezov ´ e zlomky HL Academy - Chata Lopata 2012 13.2. – 18.2.2012 Emu (Brkos 2012) ˇ Ret ˇ ezov ´ e zlomky 13.2. – 18.2.2012 1 / 27
Retezove zlomky
HL Academy - Chata Lopata 2012
13.2. – 18.2.2012
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 1 / 27
Obsah
1 Uvod
2 Zakladnı pojmy
3 Konecne retezove zlomkySblızene zlomkyEukliduv algoritmus
4 Nekonecne retezove zlomkyKonvergenceIracionalnı cıslaPeriodicke retezove zlomky
5 Aplikace retezovych zlomkuNeurcita rovnice prvnıho stupne
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 2 / 27
Uvod
Motivace
Pohadky tisıce a jedne nociSahrazad pokryvala koberec hedvabnymi ctverciVzdy nejvetsı mozny ctverec, jestlize jich bylo vıc, tak vsechnyPomer delky ku sırce racionalnı cıslo
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 3 / 27
Uvod
Motivace pokracovanı
Obdelnık s rozmery 83x181.2x 83x83, zbyde 83x155x 15x15, zbyde 8x151x 8x8, zbyde 8x71x 7x7, zbyde 1x77x 1x1, pokryto
18183
=83 + 83 + 15
83= 2 +
18315
= 2 +1
5 + 1158
= 2 +1
5 + 11+ 1
87
= 2 +1
5 + 11+ 1
1+ 17
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 4 / 27
Zakladnı pojmy
Zakladnı pojmy
definice
Retezovym zlomkem nazyvame vyraz
a1 +b1
a2 +b2
a3+b3
a4+...
kde ak ,bk pro k = 1,2, . . . mohou byt realna nebo komplexnı cısla.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 5 / 27
Zakladnı pojmy
poznamka
Retezovy zlomek nazvemekonecny, jestlize ma konecny pocet prvku.nekonecny, jestlize ma nekonecny pocet prvku.pravidelny, jestlize vsechny citatele se rovnajı 1 a vsechnyjmenovatele jsou prirozena cısla.
poznamka
Mısto psanı slozitych vyrazu casteji pouzıvame pro retezove zlomkytvar [a1,a2, . . . ,an], cıslum a1,a2, . . . ,an rıkame prvky retezovehozlomku.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 6 / 27
Konecne retezove zlomky Sblızene zlomky
Spocıtame retezove zlomky zepredu
Abychom mohli vytvorit rozumnou teorii, ktera by pokryla i nekonecnezlomky, musıme je umet pocıtat ”zepredu”.
a1 =a1
1=
P1
Q1
a1 +1a2
=a1a2 + 1
a2=
P2
Q2
a1 +1
a2 +1a3
=a1a2a3 + a1 + a3
a2a3 + 1=
P3
Q3
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 7 / 27
Konecne retezove zlomky Sblızene zlomky
Sblızene zlomky
a1 +1
a2 +1
a3+1
a4
=a1a2a3a4 + a1a2 + a1a4 + a3a4 + 1
a2a3a4 + a2 + a4=
P4
Q4
...
a1 +1
a2 +1
a3+1
a4+···+ 1an
=Pn
Qn=
pq
definice
Zlomkum P1Q1, P2
Q2, · · · , Pn
Qnrıkame sblızene zlomky retezoveho zlomku.
Poslednı sblızeny zlomek PnQn
je roven hodnote retezoveho zlomku,kladnemu racionalnımu cıslu p
q .
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 8 / 27
Konecne retezove zlomky Sblızene zlomky
Vlastnosti
vetaPro kazde k ≥ 2 platı nasledujıcı vztahy:
Pk = akPk−1 + Pk−2
Qk = akQk−1 + Qk−2,
pokud formalne polozıme P0 = 1,Q0 = 0.
Dukaz. Matematickou indukcı.
poznamka
Pro obecny retezovy zlomek platı podobne vzorce:Pk = akPk−1 + bkPk−2, Qk = akQk−1 + bkQk−2
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 9 / 27
Konecne retezove zlomky Sblızene zlomky
prıklad
Vypocıtejte sblızene zlomky retezoveho zlomku [2,2,1,1,2,2].
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 10 / 27
Konecne retezove zlomky Sblızene zlomky
prıklad
Vypocıtejte sblızene zlomky retezoveho zlomku [2,2,1,1,2,2].
Resenı. Nejprve sestavıme sblızene zlomky do tabulky.ak a1 a2 a3 · · · an
Pk P1 = a1 P2 = a1a2 + 1 a1a2a3 + a1 + a3 · · · anPn−1 + Pn−2
Qk Q1 = 1 Q2 = a2 a2a3 + 1 · · · anQn−1 + Qn−2
Dle vzorecku sestavıme tabulku pro tento retezovy zlomek.ak 2 2 1 1 2 2Pk 2 5 7 12 31 74Qk 1 2 3 5 13 31
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 11 / 27
Konecne retezove zlomky Eukliduv algoritmus
Eukliduv algoritmus
Dosud jsme hledali vyjadrenı retezoveho zlomku racionalnım cıslem.Ted’ obracene, tj. najdeme k racionalnımu cıslu p
q retezovy zlomek. Ktomu nam poslouzı Eukliduv algoritmus. (Algoritmus se v algebrepouzıva na urcenı nejvetsıho spolecneho delitele.)
p = qa1 + r1
q = r1a2 + r2
r1 = r2a3 + r3
· · ·rn−2 = rn−1an + rn
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 12 / 27
Konecne retezove zlomky Eukliduv algoritmus
· · · celkove dostaneme:
pq= a1 +
1a2 +
1a3+···+ 1
an
jedine mozne vyjadrenıan > 1, nebot’ pro an = 1 dava poslednı rovnost rn−2 = rn−1
⇒ jednoznacne vyjadrenı
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 13 / 27
Konecne retezove zlomky Eukliduv algoritmus
prıklad
Vypocıtejte prvky retezoveho zlomku a1,a2, · · · ,an cısla 7431 .
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 14 / 27
Nekonecne retezove zlomky Konvergence
Nekonecne retezove zlomky
V teto kapitole se budeme zabyvat nekonecnymi pravidelnymiretezovymi zlomky, tedy zlomky ve tvaru [a1,a2,a3, · · · ]. Kazdemunekonecnemu retezovemu zlomku odpovıda nekonecna posloupnostsblızenych zlomku.
definice
Rekneme, ze nekonecny retezovy zlomek konverguje, jestlize existujekonecna limita
limn→∞
Pn
Qn= α,
kde PnQn
jsou sblızene zlomky retezoveho zlomku. Cıslo α nazvemehodnotou retezoveho zlomku.Jestlize tato limita neexistuje, nebo je rovna ±∞, rekneme, ze retezovyzlomek diverguje.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 15 / 27
Nekonecne retezove zlomky Iracionalnı cısla
Iracionalnı cısla
vetaKazde iracionalnı cıslo se da vyjadrit ve tvaru nekonecnehopravidelneho retezoveho zlomku.
prıklad
Vypoctete retezovy zlomek cısla π.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 16 / 27
Nekonecne retezove zlomky Iracionalnı cısla
π = 3 +1α1
α1 =1
π − 3= 7 +
1α2
α2 =π − 3
22− 7π= 15 +
1α3
α3 =22− 7π
106π − 333= 1 +
1α4
α4 =106π − 333355− 113π
= 292 +1α5
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 17 / 27
Nekonecne retezove zlomky Periodicke retezove zlomky
Periodicke retezove zlomky
definicePeriodickym retezovym zlomkem nazyvame vyraz
[a1,a2, · · · ,ak ,ak+1, · · · ,an,ak+1, · · · ]
a budeme ho znacit
[a1,a2, · · · ,ak ,ak+1, · · · ,an].
Ryze periodickym je pak vyraz
[a1,a2, · · · ,ak ,a1,a2, · · · ,ak , · · · ,a1] = [a1,a2, · · · ,ak ].
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 18 / 27
Nekonecne retezove zlomky Periodicke retezove zlomky
veta
Pro retezovy zlomek cısla√
r , r ∈ N,√
r > 1,√
r ∈ I platı√
r = [a1,a2,a3, . . . ,a3,a2,2a1].
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 19 / 27
Nekonecne retezove zlomky Periodicke retezove zlomky
Tabulka odmocnin
√n RZ
√n
√n RZ
√n
√n RZ
√n
√2 [1,2]
√14 [3,1,2,1,6]
√26 [5,10]√
3 [1,1,2]√
15 [3,1,6]√
27 [5,5,10]√5 [2,4]
√17 [4,8]
√28 [5,3,2,3,10]√
6 [2,2,4]√
18 [4,4,8]√
29 [5,2,1,1,2,10]√7 [2,1,1,1,4]
√19 [4,2,1,3,1,2,8]
√30 [5,2,10]√
8 [2,1,4]√
20 [4,2,8]√
31 [5,1,1,3,5,3,1,1,10]√10 [3,6]
√21 [4,1,1,2,1,1,8]
√32 [5,1,1,1,10]√
11 [3,3,6]√
22 [4,1,2,4,2,1,8]√
33 [5,1,2,1,10]√12 [3,2,6]
√23 [4,1,3,1,8]
√34 [5,1,4,1,10]√
13 [3,1,1,1,1,6]√
24 [4,1,8]√
35 [5,1,10]
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 20 / 27
Nekonecne retezove zlomky Periodicke retezove zlomky
definiceKvadraticka iracionalita rıkame vyrazu
p ±√
rq
,
kde p,q ∈ Z, r ∈ N, r 6= 1 a√
r ∈ I. Kazdy takovy vyraz je korenemnejake kvadraticke rovnice.
veta [Lagrangeova]
Kazdy periodicky retezovy zlomek je hodnotou nejake kvadratickeiracionality a naopak kazdou kvadratickou iracionalitu lze vyjadritperiodickym retezovym zlomkem.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 21 / 27
Nekonecne retezove zlomky Periodicke retezove zlomky
prıklad
Vypoctete retezovy zlomek cısla α = 11−√
73 .
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 22 / 27
Nekonecne retezove zlomky Periodicke retezove zlomky
Resenı.
α =11−
√7
3= 2 +
1α1
α1 =3
5−√
7=
5 +√
76
= 1 +1α2
α2 =6√
7− 1= 1 +
√7 = 3 +
1α3
α3 =1√
7− 2=
2 +√
73
= 1 +1α4
α4 =3√
7− 1=
1 +√
72
= 1 +1α5
α5 =2√
7− 1=
1 +√
73
= 1 +1α6
α6 =3√
7− 2= 2 +
√7 = 4 +
1α7
α7 =1√
7− 2= 1 +
1α8
· · ·Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 23 / 27
Aplikace retezovych zlomku Neurcita rovnice prvnıho stupne
Resenı neurcite rovnice prvnıho stupne
definiceRovnici
ax + by = c,
kde a,b, c ∈ Z jsou znama cısla, nazyvame neurcitou rovnicı prvnıhostupne.
Ma nekonecne mnoho resenı.Celocıselna resenı pouze tehdy, jestlize NSD(a,b)|c, muzemepredpokladat, ze jsou nesoudelna.Nalezenı dvojice korenu pomocı retezovych zlomku.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 24 / 27
Aplikace retezovych zlomku Neurcita rovnice prvnıho stupne
Nalezenı dvojice korenu pomocı ret.zl.
1 Obecne resenı rovnice x = x0 − bt , y = y0 + at .2 Najdeme prvky retezoveho zlomku a
b = PnQn
.3 Urcıme predposlednı sblızeny zlomek a dosadıme do vzorce
PnQn−1 − Pn−1Qn = (−1)n.4 Dostavame
x0 = (−1)nQn−1c, y0 = (−1)n−1Pn−1c,
obecne tedy
x = (−1)nQn−1c −Qnt , y = (−1)n−1Pn−1c + Pnt ,
kde t je libovolne cele cıslo.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 25 / 27
Aplikace retezovych zlomku Neurcita rovnice prvnıho stupne
prıklad
Reste rovnici 27x + 17y = 1.
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 26 / 27
Aplikace retezovych zlomku Neurcita rovnice prvnıho stupne
Dıky za pozornost:o)
Emu (Brkos 2012) Retezove zlomky 13.2. – 18.2.2012 27 / 27
