Breuken - Brak - Gebroken. Kettingbreuken

Breuken - Brak - Gebroken Kettingbreuken

Voorwoord Kettingbreuken is een boekje dat bedoeld is voor HAVO- en VWO leerlingen met wiskunde in hun profiel. Aan het einde van elk hoofdstuk is een aantal oefeningen opgenomen, om de leerstof beter te begrijpen. Uitwerkingen van de oefeningen staan achterin. Bij dit boekje hoort een website met extra ondersteuning, bereikbaar via www.rgomiddelharnis.nl menu leerlingen - vaklokalen - wiskunde. Kettingbreuken zijn, zoals de naam al zegt, in de eerste plaats gewoon breuken. Dit zijn getallen van de vorm pq , waarbij p en q gehele getallen zijn (q 6= 0). Onder gehele getallen verstaan we de natuurlijke getallen 1, 2, 3, · · · , het getal 0 en de negatieve gehele getallen −1, −2, −3, · · · . Kettingbreuken is een onderdeel van de getaltheorie. Wie meer wil lezen over getaltheorie raad ik aan: Getaltheorie voor Beginners - Frits Beukers (Epsilon Uitgaven, Utrecht- ISBN: 90-5041-049-9). In hoofdstuk 1 wordt gekeken naar de decimale ontwikkeling van getallen. Ook worden de breuken met hun eigenschappen nauwkeurig bekeken. De basis wordt gelegd voor de eigenschappen van kettingbreuken. In hoofdstuk 2 worden de eindige kettingbreuken met hun eigenschappen bekeken. Belangrijke zaken als convergenten en kettingbreukalgoritme worden behandeld. Ook volgt er een toepassing bij de oplossing van ax + by = c. In hoofdstuk 3 volgen de oneindige kettingbreuken. Na eigenschappen als benaderingseigenschappen en periodiciteit volgen enkele toepassingen zoals het rekenen aan kalenders, de gulden snede en kettingbreuken met negatieve wijzergetallen. In hoofdstuk 4 staat een toepassing van de kettingbreuken; de vergelijking van Pell. Ten slotte volgen er eindopdrachten waarin o.a. in een computerpracticum gerekend wordt aan kettingbreuken. Mijn dank gaat uit naar prof. dr. Frits Beukers voor de begeleiding bij de totstandkoming van dit boekje. Tevens dank ik NWO voor de gelegenheid via LiO (leraar in onderzoek) dit boekje te schijven

Lennart de Jonge Stellendam, juli 2006

i

Inhoudsopgave 1 Decimale ontwikkeling 1.1 Getallen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Periodieke breuken . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Oefeningen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Eindige kettingbreuken 2.1 Representatie . . . . . . . . . . . . . . . . . . . 2.2 Convergenten . . . . . . . . . . . . . . . . . . . 2.3 Euclidisch algoritme en Kettingbreuk algoritme 2.4 Geheeltallige oplossingen van ax + by = c . . . 2.5 Oefeningen . . . . . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

1 1 2 6

. . . . .

7 7 8 11 14 16

3 Oneindige kettingbreuken 3.1 Representatie . . . . . . . . . 3.2 Benaderingseigenschappen . . 3.3 Periodiciteit en symmetrieën 3.4 Kalender . . . . . . . . . . . . 3.5 Sectio divina . . . . . . . . . 3.6 Oefeningen . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

17 17 18 20 22 24 25

4 De 4.1 4.2 4.3 4.4

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

27 27 28 30 31

vergelijking van Pell Diophantische vergelijkingen Pell nader bekeken . . . . . Knikkers . . . . . . . . . . . Oefeningen . . . . . . . . .

. . . .

5 Eindopdrachten 33 5.1 De Slag bij Hastings . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 Computer practicum . . . . . . . . . . . . . . . . . . . . . . . . . 34 6 Verder werken 37 6.1 Vermoeden van Zaremba . . . . . . . . . . . . . . . . . . . . . . . 37 6.2 Elementaire functies . . . . . . . . . . . . . . . . . . . . . . . . . 38 7 Uitwerkingen van de oefeningen

ii

41

Hoofdstuk 1

Decimale ontwikkeling 1.1

Getallen

Er zijn verschillende manieren om getallen te representeren. Dit boekje gaat over kettingbreuken. Voordat we in detail naar kettingbreuken gaan kijken, richten we ons eerst op decimale breuken. Het huidige systeem om getallen te noteren stamt uit de Indische en Arabische tijd en staat bekend als het decimale systeem. Met bijvoorbeeld 1234 bedoelen we het getal 1 · 103 + 2 · 102 + 3 · 101 + 4 · 100 . Voor 1600 werd voor het rekenen met niet-gehele getallen normaal gesproken gewerkt met algemene breuken, gebaseerd op handige noemers. Er waren wel gestandaardiseerde methoden die met 60-tallige breuken werkten, maar over het algemeen was het moeilijk om aan de breuk te zien in hoeverre die het gewenste niet-gehele getal werkelijk benaderde. Decimale breuken werden al wel gebruikt, maar alleen om te kunnen worteltrekken. In het dagelijks leven werkte men niet met decimale breuken. In 1586 schreef Simon Stevin zijn beroemde werk De Thiende, waarin hij het algemeen gebruik van breuken op basis van het tientallig stelsel beschreef. Hij gebruikte daarvoor nog niet de notatie met een decimale punt of decimale komma zoals wij dat nu doen, maar een notatie waar achter elk cijfer in een cirkel de (negatieve) macht van 10 kwam te staan die er op dat cijfer van toepassing was. Wat wij nu als 6, 87 (d.w.z. 6 · 100 + 8 · 10−1 + 7 · 10−2 ) schrijven, schreef Simon Stevin als 6(0)8(1)7(2). We hebben gezien dat de deling van twee gehele getallen soms een geheel getal oplevert. Meestal is dit echter niet het geval. De breuken 12 = 0, 5 en 12849 50000 = 0, 25698 zijn voorbeelden van gebroken getallen met een eindige decimale ontwikkeling. We kennen ook getallen met een oneindige decimale ontwikkelingen. Het getal pi, π = 3, 141592653589793238462643383 · · · heeft door de jaren heen vele mensen geboeid. De decimale ontwikkeling van pi is zo willekeurig dat wiskundigen vermoeden dat de decimale ontwikkeling 1

2

HOOFDSTUK 1. DECIMALE ONTWIKKELING

van pi niet te onderscheiden is van een willekeurige rij cijfers. Een eindig rijtje cijfers komt op den duur even vaak in pi voor als dat je zou verwachten in een willekeurige rij. Niemand heeft dit echter tot nu toe kunnen bewijzen. Het onthouden van de eerste zoveel decimalen van pi is een sport op zich. Maar in ons computertijdperk is dit een nogal nutteloze bezigheid geworden. Tegenwoordig tover je met een simpele druk op de knop vele duizenden decimalen op je scherm tevoorschijn. Op het internet vind je verschillende pi-clubs. De leden van de 1000-club beweren 1000 decimalen van pi uit hun hoofd te kennen. Maar als bewijs hoeven ze slechts duizend of meer decimalen per email op te sturen. De tegenhanger van de 1000-club is de 2-club, die bestaat uit mensen die beweren niet eens twee decimalen van pi te kunnen onthouden! Als je lid wilt worden van zo’n pi-club, dan kan de volgende zin je op weg helpen (tel de letters in de woorden). How I want a drink, alcoholic of course, after the heavy lectures involving quantum mechanics! Meer informatie over Pi is te lezen in het zebra deeltje over dit onderwerp.1 .

1.2

Periodieke breuken

Een eindige decimale breuk is een breuk met als noemer een macht van 10, . Decimale breuken worden niet als breuk geschreven bijvoorbeeld 0, 123 = 123 103 maar als een rij cijfers. Niet alle breuken zijn als een (volledige) decimale breuk te schrijven. Zo is bijvoorbeeld 13 = 0, 3333333333333 · · · . We noteren dit als 0, 3. Zo’n breuk noemen we een repeterende (decimale) breuk. Elk rationaal getal (een getal van de vorm pq , met q 6= 0) kan als een, al dan niet repeterende, breuk worden geschreven. Op het eerste gezicht zijn niet alle decimale ontwikkelingen van breuken periodiek. Bijvoorbeeld 14 = 0, 25. Toch kun je 0, 25 zien als een periodieke ontwikkeling, door 14 te schrijven als 0, 2500000 · · · . Je zou kunnen zeggen dat dit getal vanaf de derde decimaal een periodiek aantal nullen heeft. Een ander voorbeeld is 373 = 0, 88809523809523809 · · · = 0, 88809523 420 We zien dat het rijtje getallen 809523 steeds wordt herhaald maar pas begint na de eerste twee decimalen 8. We noemen 809523 de periode en omdat dit rijtje bestaat uit 6 cijfers zeggen we dat de periodelengte gelijk is aan 6. Dat de decimale ontwikkelingen van een breuk pq niet meteen vanaf het decimaalteken periodiek is (zuiver periodiek) komt omdat de noemer q factoren 2 of 5, of beide bevat. 1

De geschiedenis en de wiskunde van het getal π, F. Beukers, ISBN 90-5041-062-6

3

1.2. PERIODIEKE BREUKEN

De decimalen van een breuk kun je ook zonder rekenmachine bepalen. We laten dit zien aan de hand van 37 . Stel we schrijven de decimalen van 37 als a1 , a2 , a3 , · · · . Dus 3 = 0, a1 a2 a3 · · · 7 2 Vermenigvuldigen we 37 met 10, dan krijgen we 30 7 = 4 + 7 . Ook geldt dat 30 7 = a1 , a2 a3 a4 · · · . Vergelijken we beide uitdrukkingen dan zien we dat a1 = 4. Laten we het gehele deel weg en vermenigvuldigen de rest 27 weer met 10, dan 6 10 · 27 = 20 7 = 2 + 7 dus a2 = 2. Wanneer we dit proces van de ontstane rest vermenigvuldigen met 10 en het gehele deel afsplitsen voortzetten, krijgen we a3 = 8, a4 = 5, a5 = 7 en a6 = 1. Nu krijgen we als ’rest’ weer 37 . Het proces begint dan weer opnieuw. De decimale ontwikkeling van 37 is dus periodiek en de periode is 428571. Stelling 1.2.1 Als de noemer van een vereenvoudigde breuk geen factoren 2 of 5 bevat, dan is de decimale ontwikkeling van die breuk zuiver periodiek. Bewijs: Om deze stelling voor alle breuken aan te tonen, gaan we net zo te werk als we met 37 gedaan hebben. Alleen nemen we nu pq in plaats van 37 . We schrijven: pq = 0, a1 a2 a3 · · · met 0 < p < q en 0 ≦ ai ≦ 9. q bevat geen factoren 2 of 5. Door vermenigvuldiging links en rechts met 10 krijgen we voor 0 ≦ ai ≦ 9 en 0 < ri < q: 10 · p a1 · q + r1 = = a1 + q q 10 · r1 a2 · q + r2 = = a2 + q q .. .

r1 q r2 q

De op deze wijze gegenereerde rij a1 , a2 , a3 , · · · leveren de decimalen van de breuk pq . Omdat 0 < ri < q, voor alle i, moet er op een gegeven moment een ri zijn die al een keer geweest is. Stel rk = rl , met k < l. Dus: 10 · p a1 · q + r1 = = a1 + q q 10 · r1 a2 · q + r2 = = a2 + q q .. . 10 · rk−1 rk = ak + q q .. . 10 · rl−1 rl = al + q q

r1 q r2 q

4


Omdat rl = rk zal het rijtje resten rl+1 , rl+2 , · · · hetzelfde zijn als het rijtje resten rk+1 , rk+2 , · · · . Dus de breuk is periodiek met periodelengte m = l − k. Om aan te tonen dat de breuk ook zuiver periodiek is, moeten we aantonen dat de rij resten die vooraf gaan aan rk en rl gelijk zijn aan elkaar. Bekijk 10·rk−1 10·rl−1 hiervoor het verschil van = ak + rqk en = al + rql . Dan geldt dat q q 10·(rk−1 −rl−1 ) q

= ak − al dus een geheel getal. D.w.z. q deelt 10 · (rk−1 − rl−1 ) en omdat q geen factoren 2 of 5 bevat, deelt q dus rk−1 − rl−1 . Hieruit volgt dat rk−1 = rl−1 . Dit wil zeggen dat de voorgangers van rk en rl ook aan elkaar gelijk zijn en daar weer de voorgangers van, etc. Zet dit proces voort tot rm = p. Er geldt dan dat a1 = am+1 dus de breuk is zuiver periodiek met periode lengte m. 2 We zullen nu preciezer bekijken wat er gebeurt als de noemer wel factoren 2 of 5 bevat. Eerst maar weer een voorbeeld: 13 13 = = 0, 3714285 35 5·7 Door vermenigvuldiging met 10 ontstaat: 130 25 5 =3+ = 3 + = 3, 714285 35 35 7 en 57 is volgens de vorige stelling zuiver periodiek. Delen door 10 geeft links 13 onze oorspronkelijke 13 35 en rechts verschuift alles 1 plaats naar rechts. Dus 35 is niet zuiver periodiek (gemengd periodiek). Stel de onvereenvoudigbare breuk

p q

bevat factoren 2 of 5 in de noemer, dus:

2a

p · 5b · s

voor a, b ∈ Z>0 . Vermenigvuldig nu met 10k , waarbij k gelijk is aan de grootste exponent a of b. De factoren 2 of 5 zijn na vereenvoudiging weg uit de noemer. k Dat wil zeggen dat de decimale ontwikkeling van 10q ·p zuiver periodiek is. Dek

len we door 10k dan verschuiven de decimalen van 10q ·p naar rechts over een afstand k ten opzichte van het decimaalteken. De ontwikkeling is dus gemengd periodiek.

Het op deze manier uitrekenen van de decimalen van een breuk levert nog een aardigheid op. We nemen het getal 7 en bepalen de decimalen van het getal 17 . Laten we eens kijken naar de som van de cijfers in de periode. Bij 17 = 0, 142857 gaat het dus om 1+4+2+8+5+7 = 27. Deze som is ook gelijk aan 4 12 ×6, waarbij 6 = 7 − 1, dus één minder dan de noemer 7. Het blijkt dat S = 4 12 × (p − 1) een formule is om de som van de cijfers in de periode van 1p te bepalen, wanneer de noemer een priemgetal is met periodelengte p − 1. Zo’n formule is handig

5

1.2. PERIODIEKE BREUKEN

wanneer de periodelengte groot wordt, zoals bij 1 = 0,0103092783505154639175257731958762886597 97 9381443298969072164948453608247422680412 3711340206185567 Het is duidelijk dat het bepalen van de som van de 96 cijfers in de periode niet prettig is om met de hand uit te rekenen. We laten de rekentechniek zien aan de hand van het eenvoudige voorbeeld van 17 , zodat we het ook kunnen toepassen 1 op lastigere voorbeelden, zoals 97 . De ontwikkeling van de decimalen van 17 ziet er als volgt uit: 10 = 1 × 7 + 3 30 = 4 × 7 + 2 20 = 2 × 7 + 6 60 = 8 × 7 + 4 40 = 5 × 7 + 5 50 = 7 × 7 + 1 Tellen we nu de getallen aan de linker- en rechter kant van het =-teken op, dan krijgen we: 10 × (1 + 2 + 3 + 4 + 5 + 6) = (1 + 4 + 2 + 8 + 5 + 7) × 7 + (1 + 2 + 3 + 4 + 5 + 6) Dus:

(1 + 4 + 2 + 8 + 5 + 7) × 7 = 9 × (1 + 2 + 3 + 4 + 5 + 6)

Nu geldt volgens de somformule van een rekenkundige rij (C.F. Gauss) dat (1 + 2 + 3 + 4 + 5 + 6) = 6×7 2 . Dus we krijgen: 6×7 2 Tenslotte delen we links en rechts door 7, dan krijgen we: 9×6 1+4+2+8+5+7 = = 27 2 (1 + 4 + 2 + 8 + 5 + 7) × 7 = 9 ×

We kunnen dit voor een willekeurig priemgetal p doen, waarvan de periodelengte van 1p gelijk is aan p − 1. Er volgt dat voor de som Sp van de cijfers uit de periode geldt 9(p − 1) Sp = 2 In opgave 1.3.4 wordt deze formule afgeleid. Controleer nu zelf dat voor

1 97

geldt

0 + 1 + 0 + 3 + 0 + 9 + ··· + 7 =

9 × 96 = 432 2

6

1.3


Oefeningen

Oefening 1.3.1 Schrijf het getal 37, 246 als som van machten van 10. Oefening 1.3.2 Beredeneer waarom 0, 101001000100001000001 · · · een irrationaal getal is. Oefening 1.3.3 Schrijf elk van de getallen 17 , 27 , · · · , 67 als decimale breuk. Wat valt er op aan de decimalen? Oefening 1.3.4 Schrijf 1p = 0, a1 a2 a3 · · · ap−1 , met p een willekeurig priemgetal waarvan de periodelengte van 1p gelijk is aan p − 1. Leidt de formule af voor de som Sp van de cijfers in de periode. Oefening 1.3.5 Welke breuken met noemer 24 geven (na herleiding) een eindig decimale breuk, welke een zuiver repeterende breuk en welke een gemengd repeterende breuk? In de volgende opgave gaan we bewijzen dat het blok 142857 steeds herhaald wordt in de decimale ontwikkeling van 1/7. Oefening 1.3.6 Bepaal de som van de meetkundige reeks 1 + x + x2 + x3 + x4 + · · · , welke geldt voor alle x ∈ R met |x| < 1. Bepaal nu de ontwikkeling van 1061−1 , door in de meetkundige reeks beide zijden met x te vermenigvuldigen en vervolgens voor x = 10−6 in te vullen. Laat zien dat

1 7

=

142857 106 −1

en dat dus het blok 142857 wordt herhaald.

Oefening 1.3.7 Bepaal het gemiddelde van de cijfers in de periode van 1p , met p een priemgetal en de lengte van de periode van 1p gelijk aan p − 1. Oefening 1.3.8 Onderzoek voor enkele willekeurige priemgetallen p, dus niet met periodelengte p − 1, of het gemiddelde van de cijfers uit de periode van 1p gelijk is aan het gemiddelde wanneer wel de periodelengte p − 1 is.

Hoofdstuk 2

Eindige kettingbreuken 2.1

Representatie

Sinds de oudheid is al bekend dat reële getallen, behalve via hun decimale ontwikkeling, ook via kettingbreuken kunnen worden weergegeven. Met kettingbreuken kan men optimale rationale benaderingen (dus van de vorm pq met q 6= 0) van reële getallen construeren. Evariste Galois (25 oktober 1811 - 31 mei 1832) is bekend geworden vanwege zijn wiskundige prestaties op jonge leeftijd. Zijn wiskundeknobbel uitte zich op vijftienjarige leeftijd, toen hij de derde klas van het voorbereidend wetenschappelijk onderwijs moest doubleren. Hij kreeg een wiskundedocent die hem in alle opzichte stimuleerde. Galois verslond zijn wiskundeboeken en las ook al meesterwerken uit die tijd: Legendre’s werk over geometrie en Lagrange’s boeken over vergelijkingen, functies en analyse. Een jaar te vroeg besloot Galois toelatingsexamen te doen voor de polytechnische school. Hij werd afgewezen omdat zijn wiskundekennis onvoldoende zou zijn! Zo’n onrechtvaardigheid voor een wiskundig genie. In maart 1829 als 17 jarige scholier - publiceerde Galois zijn eerste artikel in een wiskundig tijdschrift: Bewijs van een theorema over periodiek repeterende breuken. Galois stierf op 20 jarige leeftijd in een duel om een meisje, maar in de nacht voor zijn dood zette hij een revolutionaire theorie op papier, die bekend staat als Galois theorie. Hiernaast staat de brief die Galois vlak voor zijn dood schreef. Links onder het bibliotheekstempel zijn noodkreet:”Je n’ai pas le temps - maar ik heb geen tijd”. 7

8

HOOFDSTUK 2. EINDIGE KETTINGBREUKEN

Een eindige kettingbreuk is een breuk van de vorm: 1

a0 +

1

a1 +

a2 + · · · +

1 an

met a0 ∈ Z en a1 , a2 , · · · , an ∈ N. Omdat deze manier van opschrijven onhandig is en veel ruimte kost kiezen we meestal voor [a0 , a1 , a2 , · · · , an ]. De getallen a0 , a1 , a2 , · · · , an heten de wijzergetallen van de kettingbreuk. Vanzelfsprekend levert berekening van een eindige kettingbreuk een rationaal getal (een breuk) op. Het aardige is dat ook het omgekeerde geldt. Bij elk rationaal getal hoort een kettingbreuk. Hier komen we op terug. De ontwikkeling van een kettingbreuk is bijna uniek. Voorbeeld:

1

[2, 3, 1, 1, 5] = 2 + 3+

1+ 1 3+ =

1

3+

1 1+

=2+

1

=2+

1 1 5

=2+

11 6

=

1 1+

1 6 5

1 11 6 = 2 + 39 3 + 11

89 39

89 = [2, 3, 1, 1, 4, 1], om de eenvoudige reden dat we de 5 van 39 de vorige kettingbreuk ook kunnen schrijven als 5 = 4 + 11 . Op de laatste twee wijzergetallen na zijn de kettingbreukontwikkelingen identiek. Een rationaal getal kan dus op twee manieren geschreven worden als kettingbreuk. Als we eisen dat het laatste wijzergetal groter is dan 1, dan is de ontwikkeling uniek vastgelegd! Algemeen geldt dat [a0 , a1 , · · · , an ] = [a0 , a1 , · · · , an − 1, 1] (zie opgave 2.5.1).

Maar ook geldt:

2.2

Convergenten 143 84 . rest ab

We bepalen de kettingbreuk van breuk. Daarna schrijven we de 1 in ligt, dus dat

1

kan worden. Dus,

b a

Eerst bepalen we het gehele deel van de 1 als b . Merk op dat ab altijd tussen 0 en a

altijd groter is dan 1, zodat het gehele deel weer afgesplitst

9

2.2. CONVERGENTEN

143 1 = 1 + 84 = 1 + 84 59

1 1+

59 25

2+

1+

1

2+

2+

1+

De 7 wijzergetallen zijn dus

143 84

1 9 7

1 1 1

2+

1

2+

1

2+

25 9

1+

1

=

1

1+

=1+

1

1

=1+

1

1+

1

=1+

1

=1+

1

1

2+

1

1+

7 2

1 3+

1 2

= [1, 1, 2, 2, 1, 3, 2].

Als we de kettingbreuk na het derde wijzergetal afbreken krijgen we een bena5 dering van onze breuk 143 84 , dus [1, 1, 2] = 3 . We noemen deze breuk de derde convergent van onze breuk. Zo is de vierde convergent [1, 1, 2, 2] = 12 7 . In het algemeen noemen we de breuk pn = [a0 , a1 , a2 , · · · , an ] qn de n-de convergent van de breuk De 7 convergenten van 1

143 84

2

a = [a0 , a1 , · · · , an , an+1 , · · · , ak ]. b

zijn dus op rij 12 7

5 3

17 10

63 37

143 84

Het op deze manier uitrekenen van de convergenten is veel werk. Je moet namelijk eerst de gehele kettingbreuk uitrekenen. Een recept om de convergenten uit te rekenen op een eenvoudige manier staat in de volgende stelling (zonder bewijs).

Stelling 2.2.1 Stel a0 ∈ Z en a1 , a2 , · · · ∈ N. Bepaal voor n ≥ −2 de getallen pn , qn als volgt,

p−2 = 0, q−2 = 1, Er geldt dus:

p−1 = 1, q−1 = 0,

p0 = a0 , q0 = 1,

pn an pn−1 + pn−2 = qn an qn−1 + qn−2

···, ···,

pn = an pn−1 + pn−2 , · · · qn = an qn−1 + qn−2 , · · ·

10


We kijken nog eens naar de kettingbreuk ontwikkeling van 143 84 . De wijzergetallen zijn [1, 1, 2, 2, 1, 3, 2]. De convergenten kunnen we berekenen met het volgende schema, n an pn qn

-2

-1

0 1

1 0

0 1 1 1

1 1 2 1

2 2 5 3

3 2 12 7

4 1 17 10

5 3 63 37

6 2 143 84

De p-waarde in de kolom met n = 6 krijg je door het bijbehorende wijzergetal (2) te vermenigvuldigen met de vorige p-waarde en de daarop voorgaande pwaarde erbij op te tellen. Dus 143 = 2 · 63 + 17 ofwel p6 = a6 · p5 + p4 . Evenzo geldt voor q6 = 84 = 2 · 37 + 10. Elke kolom p’s en q’s ontstaat dus door het wijzergetal met de voorgaande kolom te vermenigvuldigen en de daarop voorgaande kolom erbij op te tellen. We kijken wederom naar het voorbeeld 143 84 en bekijken twee opeenvolgende convergenten uit de rij. Bijvoorbeeld 53 en 12 7 . Merk op dat het verschil tussen 5 · 7 en 3 · 12 gelijk is aan 1. Dit is ook zo met bijvoorbeeld 17 · 37 en 10 · 63. Algemeen kunnen we zeggen, Stelling 2.2.2 Gegeven de kettingbreuk ab = [a0 , a1 , · · · , an ]. Stel dat pn en qn gegeven worden door het schema uit de voorgaande stelling. Dan geldt voor alle 0 < k ≤ n dat pk qk+1 − qk pk+1 = (−1)k . Om deze eigenschap in te zien, bekijken we het verschil van twee opeenvolgende convergenten. Na gelijknamig maken volgt, pk pk+1 pk qk+1 − pk+1 qk − = qk qk+1 qk qk+1 In de teller staat nu de uitdrukking waarvoor we ons interesseren. Er geldt, pk qk+1 − qk pk+1 = pk (ak+1 qk + qk−1 ) − qk (ak+1 pk + pk−1 ) = = pk qk−1 − pk−1 qk =

= −(pk−1 qk − pk qk−1 ) =

= (−1)2 (pk−2 qk−1 − pk−1 qk−2 ) = .. .

= (−1)k (p0 q1 − p1 q0 ) =

= (−1)k (1 · 1 − a1 · 0) = = (−1)k Hiermee is de stelling bewezen.

2

2.3. EUCLIDISCH ALGORITME EN KETTINGBREUK ALGORITME 11

2.3

Euclidisch algoritme en Kettingbreuk algoritme

We zagen net dat bij elk rationaal getal een kettingbreuk hoort. Bij de berekening van deze kettingbreuken maken we eigenlijk gebruik van een eeuwenoud algoritme om de grootste gemeenschappelijke deler (de ggd) van twee getallen te berekenen (de grootste gemeenschappelijke deler van twee getallen is het grootste getal, dat beide getallen deelt). Dit algoritme heet het Euclidisch algoritme, genoemd naar de beroemde Griekse wiskundige Euclides. In een van zijn boeken beschrijft Euclides dit algoritme en levert ook een bewijs voor de juistheid. Voorbeeld: Bepaal de ggd van 12 en 18. De getallen 12 en 18 hebben een aantal gemeenschappelijke delers: • De delers van 12 zijn: 1, 2, 3, 4, 6 en 12. • De delers van 18 zijn: 1, 2, 3, 6, 9 en 18.

De grootste gemeenschappelijk deler is dus 6. We noteren dan ggd(12, 18) = 6 Nog een voorbeeld: • De delers van 25 zijn: 1, 5 en 25. • De delers van 7 zijn: 1 en 7.

Dus ggd(25, 7) = 1.

Het opzoeken van de delers van twee getallen en de grootste bepalen is voor kleine getallen nog wel te doen. Voor grote getallen is dit natuurlijk veel moeilijker. Het Euclidisch algoritme biedt dan uitkomst. Enkele observaties. Stel a, b ∈ N en a = qb + r met q ∈ N en 0 ≤ r < b, deling met rest. Merk op dat iedere gemeenschappelijke deler van a en b ook een gemeenschappelijke deler van b en r is. Als namelijk d een deler is van a, notatie: d|a, en d|b dan volgt uit r = a−gb dat d|r. Omgekeerd zien we dat iedere gemeenschappelijke deler van b en r ook gemeenschappelijke deler van a en b is. Dus geldt ggd(a, b) = ggd(b, r). We passen dit nu herhaald op ons tweede voorbeeld toe. We vinden, ggd(25, 7) = ggd(7, 25 − 3 · 7) = ggd(7, 4) = = ggd(4, 7 − 1 · 4) = ggd(4, 3) =

= ggd(3, 4 − 1 · 3) = ggd(3, 1) =

= ggd(1, 3 − 3 · 1) = ggd(1, 0) = 1 Iets minder omslachtig opgeschreven, 25 = 3 · 7 + 4

7 =1·4+3 4 =1·3+1 3=3·1

12


Met behulp van dit algoritme kunnen we een kettingbreuk van 25 7 vinden. Hiervoor herschrijven we de laatste berekeningen. Deel de eerste regel door 7, de tweede door 4 en de laatste door 3, 25 4 =3+ 7 7 7 3 =1+ 4 4 4 1 =1+ 3 3 Door deze stappen achter elkaar te zetten zien we dat 25 4 1 =3+ =3+ 7 7 1+

3 4

1

=3+ 1+

1 1+

= [3, 1, 1, 3] 1 3

We hebben de berekening van de kettingbreuken zoals beschreven in paragraaf 2.2 weer teruggekregen! In het algemeen bepalen we de eindige kettingbreuk van met het algoritme van Euclides, a = a0 b + r1

a b

met a ∈ Z en b ∈ N

0 ≤ r1 < b

b = a1 r1 + r2

0 ≤ r2 < r1

r1 = a2 r2 + r3 .. .

0 ≤ r3 < r2

rk−1 = ak rk waarbij de laatste rest, rk+1 , gelijk is aan nul. Omdat de resten een dalende rij zijn, dus r1 > r2 > r3 > · · · ≥ 0 moet er op een gegeven moment een rest nul zijn. Wij beweren dat de laatste positieve rest, rk , de gevraagde ggd is. Schrijf nu alle delingen met rest als breuken op, a r1 = a0 + b b r2 b = a1 + r1 r1 r1 r3 = a2 + r2 r2 .. . rk−1 = ak rk Merk op dat voor elke m > 0 geldt dat

rm−1 = [am , am+1 , · · · , ak ]. rm

Stelling 2.3.1 Er zijn x, y ∈ Z waarvoor geldt dat ggd(a, b) = ax + by

2.3. EUCLIDISCH ALGORITME EN KETTINGBREUK ALGORITME 13 We laten de juistheid van deze stelling zien aan de hand van de breuk 143 84 = [1, 1, 2, 2, 1, 3, 2]. We schrijven 143 en 84 als lineaire combinatie van zichzelf, 143 = 1 · 143 − 0 · 84

84 = 0 · 143 + 1 · 84

We voeren nu de deling uit door te constateren dat 84 één keer in 143 past met een rest van 59. We trekken dus de onderste regel één keer van de bovenste regel af. Merk op dat a0 = 1. We krijgen dus, 143 = 1 · 143 − 0 · 84 84 = 0 · 143 + 1 · 84 59 = 1 · 143 − 1 · 84 Vervolgens past 59 één keer in 84, dus trekken we weer de onderste regel één keer (a1 = 1) af van de regel erboven, 143 = 1 · 143 − 0 · 84 84 = 0 · 143 + 1 · 84 59 = 1 · 143 − 1 · 84

25 = −1 · 143 + 2 · 84 Nu past 25 twee maal (a2 = 2) in de 59 met een rest van 9 en 9 past twee maal (a3 = 2) in 25 met een rest van 7, etcetera. We krijgen, 143 = 1 · 143 − 0 · 84

84 = 0 · 143 + 1 · 84 59 = 1 · 143 − 1 · 84

25 = −1 · 143 + 2 · 84 9 = 3 · 143 − 5 · 84

7 = −7 · 143 + 12 · 84 2 = 10 · 143 − 17 · 84

1 = −37 · 143 + 63 · 84 0 = 84 · 143 − 143 · 84

Op natuurlijke wijze zien we de wijzergetallen terugkomen in de berekeningen, namelijk het aantal keren dat een regel van de regel erboven wordt afgetrokken. Tevens zien we steeds lineaire combinatie’s van 143 en 84. In het bijzonder is in de voorlaatste stap, 1 = −37 · 143 + 63 · 84, de grootste gemeenschappelijke deler van 143 en 84 af te lezen, namelijk ggd(143, 84) = 1. Dus ggd(143, 84) = −37 · 143 + 63 · 84. In het algemeen zien we dat we met dit rekenschema oplossingen hebben gekregen van ggd(a, b) = ax + by.

14

2.4


Geheeltallige oplossingen van ax + by = c

Het volgende probleem doet zich voor. Je moet 51 euro betalen. Je hebt alleen voldoende munten van 2 euro en briefjes van 5 euro. Op hoeveel verschillende manieren kun je betalen? Dit probleem kun je oplossen door alle mogelijkheden na te gaan. Omdat 51 oneven is, heb je een oneven aantal briefjes van 5 euro nodig. Begin met 1 briefje en ga door totdat het aantal briefjes van 5 een te groot getal oplevert. De oplossingen zijn: munten van 2 euro briefjes van 5 euro

3 9

8 7

13 5

18 3

23 1

Alle mogelijkheden nagaan is vaak niet een efficiënte manier om dit soort problemen op te lossen. Zeker niet wanneer de getallen groter worden en je de oplossingen niet direct ziet. We ontwikkelen een theorie die alle oplossingen genereert. We bekijken de theorie aan de hand van het volgende voorbeeld. Een kleuterleidster wil voor 417 euro nieuwe puzzels kopen voor in de speelhoek. Er zijn twee typen puzzels die voor de kleuters in aanmerking komen. De ene soort, waarbij de kinderen gelijksoortige kaartjes moeten aanwijzen, kosten 8 euro per stuk en de andere soort, een soort legpuzzel, kosten 11 euro per stuk. Hoeveel puzzels van elk soort kan zij kopen zonder geld over te houden? We kunnen het aantal puzzels van 8 euro voorstellen door x en het aantal puzzels van 11 euro door y. Gevraagd wordt dus om de vergelijking 8x + 11y = 417 op te lossen voor gehele positieve waarden van x en y. Uitgangspunt is de vergelijking: ax + by = c met a, b, c ∈ Z, ggd(a, b) = 1 en ggd(c, ggd(a, b)) = 1. Als de ggd(a, b)|c, dan kunnen we de vergelijking herleiden door te delen door de ggd(a, b). Stel dat we nu een oplossing van de vergelijking weten. Bijvoorbeeld x = x1 en y = y1 is een oplossing van de vergelijking. Bekijk nu voor iedere gehele waarde van t: x = x1 + bt, y = y1 − at. Vul dit in (substitueer) in de vergelijking: ax + by = a(x1 + bt) + b(y1 − at) = ax1 + abt + by1 − abt = ax1 + by1 = c. Dus ook x = x1 + bt, y = y1 − at is een oplossing van de vergelijking, voor iedere gehele waarde van t. Stel x = x2 , y = y2 is nog een tweede oplossing van de vergelijking. Nu hebben we: ax1 + by1 = c ax2 + by2 = c zodat

2.4. GEHEELTALLIGE OPLOSSINGEN VAN AX + BY = C

15

a(x2 − x1 ) = b(y1 − y2 ), dus b|a(x2 − x1 ). Er is dus een t met bt = x2 − x1 , zodat at = y1 − y2 . Elke tweede oplossing van de vergelijking wordt dus gevonden uit x = x1 + bt, y = y1 − at. We hebben nu bewezen: Stelling 2.4.1 Als x1 , y1 een oplossing is van de vergelijking ax + by = c, dan is de algemene oplossing van die vergelijking x = x1 + bt, y = y1 − at. De oplossing x1 , y1 heet een particuliere oplossing van de vergelijking. De vraag is nu hoe men aan een particuliere oplossing komt. Hier kunnen we handig gebruik maken van kettingbreuken. pn . Dus pn = a en qn = b. Stel ab = [a0 , a1 , a2 , · · · , an ] = qn In paragraaf 2.2 hebben we afgeleid, dat pk qk+1 − pk+1 qk = (−1)k . Kies nu k = n − 1 dan pn−1 qn − pn qn−1 = (−1)n−1 = −(−1)n , dus pn qn−1 − pn−1 qn = (−1)n Stel nu dat x = (−1)n qn−1 en y = (−1)n−1 pn−1 . Substitueer in de vergelijking geeft,

ax + by = pn · (−1)n qn−1 + qn · (−1)n−1 pn−1 = (−1)n (pn qn−1 − qn pn−1 ) = (−1)2n =1 Hieruit volgt de volgende stelling. Stelling 2.4.2 x = (−1)n qn−1 , y = (−1)n−1 pn−1 is een oplossing van de verpn−1 gelijking ax + by = 1, waarbij de (n − 1)-de benaderende breuk is van ab . qn−1 cx, cy is dan een particuliere oplossing van de vergelijking ax + by = c.

De theorie om het probleem van de kleuterleidster op te lossen is hiermee ontwikkeld. We zoeken positieve geheeltallige oplossingen van de vergelijking 8x+11y = 417. We zoeken eerst een particuliere oplossing door 8x+11y = 1 op 8 te lossen. Dit doen we door de kettingbreuk ontwikkeling van 11 op te schrijven. 8 1 1 = 0 + 11 = 0 + 11 1+ 8

3 8

1

=0+ 1+

1 2+

1

=0+ 2 3

1

1+ 2+

1 1+

1 2

8 = [0, 1, 2, 1, 2] en n = 5. De 4-de benadering van is dus [0, 1, 2, 1] = 11 1 3 0+ = . Dus pn−1 = 3 en qn−1 = 4. Dit wil zeggen dat, 1 4 1+ 2 + 11 Dus

8 11

16


x = (−1)n qn−1 = (−1)5 · 4 = −4

y = (−1)n−1 pn−1 = (−1)4 · 3 = 3

een oplossing is van 8x + 11y = 1. We vinden dus de algemene oplossing: x = −4 · 417 + 11t y = 3 · 417 − 8t

Je wilt natuurlijk dat x > 0, dus moet gelden t > 4·417 11 . Je wilt ook dat y > 0 1251 dus dat t < 3·417 . Voor de positieve oplossingen geldt dus dat 1668 8 11 < t < 8 . Dus t = 152, 153, 154, 155, 156. De bijbehorende aantallen puzzels van 8 en 11 euro staan in de tabel, t= x= y=

152 4 35

153 15 27

154 26 19

155 37 11

156 48 3

De kleuterleidster kan dus 5 verschillende combinaties aantallen puzzels kopen, zonder geld over te houden.

2.5

Oefeningen

Oefening 2.5.1 Laat zien dat voor a0 ∈ Z en alle ai ∈ N, i ≥ 1 geldt dat [a0 , a1 , · · · , an ] = [a0 , a1 , · · · , an − 1, 1] Oefening 2.5.2 Bepaal de kettingbreukontwikkeling van: 2 17

13 33

31 336

30 41

71 171

Oefening 2.5.3 Bepaal van bovenstaande breuken alle convergenten. Oefening 2.5.4 Bepaal alle positieve gehele oplossingen x en y van de vergelijking 13 · x + 33 · y = 212 Oefening 2.5.5 Bepaal alle positieve gehele oplossingen x en y van 17x + 27y = 317 Oefening 2.5.6 Bepaal alle positieve gehele oplossingen x en y van 216x − 1000y = 4600

Hoofdstuk 3

Oneindige kettingbreuken 3.1

Representatie

Kettingbreuken worden pas echt interessant als ze oneindig lang zijn. Oneindige kettingbreuken horen bij irrationale getallen. √ getallen die niet als breuk √ Dit zijn zijn te schrijven, zoals bijvoorbeeld π, e, 2, 12 + 12 5, etc. We beginnen met een voorbeeld, de kettingbreukontwikkeling van π. Voor zijn kettingbreuk hebben we allereerst de decimalen van π nodig. Hier zijn de eerste 10: π = 3, 1415926535 · · · . We splitsen π in zijn gehele deel en de rest tussen 0 en 1. π = 3 + 0, 1415926535 · · · 1 De rest 0, 1415926535 · · · schrijven we als 7,06251330··· en van het getal in de noemer nemen we weer het gehele deel en de rest:

π =3+

1 7 + 0, 06251330 · · ·

1 De rest 0, 06251330 · · · schrijven we als 15,996594396··· en van het getal in de noemer nemen we het gehele deel en de rest:

1

π =3+ 7+

1 15 + 0, 996594396 · · ·

We kunnen zo lang doorgaan als we willen en krijgen de oneindige kettingbreukontwikkeling van π. Zet dit zelf nog een aantal stappen voort. Ter controle enkele wijzergetallen: π = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, · · · ] Algemeen kunnen we het volgende rekenschema opstellen. Kies een irrationaal getal α. We noteren het gehele deel van α als ⌊α⌋ (dus bijvoorbeeld ⌊3, 1415 · · · ⌋ = 3). Verder geldt voor de resten de notatie {α} = α − ⌊α⌋. 17

18

HOOFDSTUK 3. ONEINDIGE KETTINGBREUKEN

Noem α0 = α, dan zijn de wijzergetallen, a0 = ⌊α0 ⌋,

α1 = 1/{α0 }

a2 = ⌊α2 ⌋, .. .

α3 = 1/{α2 }

a1 = ⌊α1 ⌋,

an = ⌊αn ⌋, .. .

α2 = 1/{α1 }

αn+1 = 1/{αn }

Omdat voor de resten geldt 0 ≤ {αi } < 1 voor elke i ≥ 0 zien we dat αi+1 > 1 en dus dat ai+1 ∈ N. Na de n-de stap zien we dat α = [a0 , a1 , a2 , · · · , an−1 , αn ] Als αn = 0 voor een bepaalde waarde van n, dan is α rationaal. Omdat α irrationaal is, concluderen we dat {αn } > 0 voor alle n. Dit betekent dat het algoritme oneindig lang doorgaat, want we kunnen steeds weer αn+1 = 1/{αn } nemen. We krijgen dus de oneindig lange kettingbreuk α = [a0 , a1 , a2 , · · · , an , · · · ] Enkele voorbeelden: √

√

2 = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, · · · ]

3 = [1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, · · · ] √ 17 = [4, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, · · · ] √ 1 1 + 5 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, · · · ] 2 2 π = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, · · · ] e = [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, · · · ]

3.2

Benaderingseigenschappen

Kettingbreuken geven een alternatieve manier om reële getallen weer te geven. Deze manier van noteren is compleet anders dan de decimale ontwikkeling. Vanzelfsprekend is het gemakkelijker om voor het optellen en vermenigvuldigen de decimale notatie te gebruiken. Maar kettingbreuken hebben een aantrekkelijke eigenschap. Als voorbeeld bekijken we de kettingbreuk ontwikkeling van π en breken deze af voor 292, [3, 7, 15, 1] =

355 , 113

π−

355 = −0, 000000266764 113

De vierde kettingbreuk benadering van π geeft dus een benadering met een precisie van 6 cijfers.

19

3.2. BENADERINGSEIGENSCHAPPEN

Daarentegen geven de eerste vier decimalen van π = 3, 14159265 · · · een benadering tot op drie decimalen! Het zijn juist deze goede benaderingseigenschappen die kettingbreuken zo interessant maken. √ √ We bekijken de benaderingen van 2. De kettingbreukontwikkeling van 2 had de makkelijk te onthouden vorm [1, 2, 2, 2, 2, 2, 2, · · · ]. De convergenten berekenen we met het volgende schema: an pn qn

0 1

1 0

1 1 1

2 3 2

2 7 5

2 17 12

2 41 29

2 99 70

2 239 169

Nu volgt dat: √

7 5 √ 17 2− 12 √ 41 2− 29 √ 99 2− 70 √ 239 2− 169 2−

= 0, 0142135623 · · · = −0, 002453104 · · · = 0, 0004204589 · · · = −0, 0000072151 · · · = 0, 0000123789 · · ·

√ Het lijkt alsof de convergenten in een hoog tempo√naar 2 convergeren. Bovendien lijken ze afwisselend groter en kleiner dan 2 te zijn. We kunnen ons afvragen of andere breuken dan de convergenten,√ook zo’n goede benadering geven van een irrationaal getal. Stel we willen 2 benaderen door zo’n breuk. Kies een willekeurige noemer, bijvoorbeeld 100. Bepaal nu de √ p teller p zo dat de breuk 100 zo dicht mogelijk bij 2 ligt, dus p = 141. Nu is √ 17 2 − 141 100 = 0, 00421356 · · · . Duidelijk een slechtere benadering dan 12 , waarvan teller en noemer veel kleiner zijn dan 141 en 100. Kettingbreukbenaderingen zijn de beste benaderingen van irrationale getallen. De benaderingen van irrationale getallen α door breuken pq worden dus weergegeven door: α − p q De absolute waarde strepen zorgen ervoor dat er alleen naar de positieve afwijkingen wordt gekeken. De benaderingen liggen afwisselend boven- en onder de werkelijke waarde. Merk op dat voor alle convergenten geldt dat α − p < 1 q q2

20


3.3

Periodiciteit en symmetrie¨ en

Een aantal irrationale getallen heeft een kettingbreukontwikkeling met een√opvallend patroon erin. Dat geldt met name voor getallen van de vorm N , waarbij N een natuurlijk getal is, dat geen kwadraat is. Enkele voorbeelden met hun wijzergetallen: √

√

√

√ √ √

2 = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, · · · ]

13 = [3, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, · · · ] 14 = [3, 1, 2, 1, 6, 1, 2, 1, 6, 1, 2, 1, 6, · · · ] 19 = [4, 2, 1, 3, 1, 2, 8, 2, 1, 3, 1, 2, 8, · · · ]

31 = [5, 1, 1, 3, 5, 3, 1, 1, 10, 1, 1, 3, 5, 3, 1, 1, 10, · · · ] 52 = [7, 4, 1, 2, 1, 4, 14, 4, 1, 2, 1, 4, 14, · · · ]

In deze voorbeelden vallen drie regelmatigheden op:

• Na het eerste wijzergetal is de rij wijzergetallen √ periodiek. Zo is het perio√ dieke blok bij 14 gelijk aan 1, 2, 1, 6 en bij 31 is dat 1, 1, 3, 5, 3, 1, 1, 10. • Het laatste wijzergetal van het periodieke blok is twee maal zo groot als het eerste wijzergetal. • Als we van het periodieke blok het laatste getal weglaten, vormen de overgebleven wijzergetallen een √ √ palindroom. Bijvoorbeeld de getallen 1, 2, 1 bij 14 en 2, 1, 3, 1, 2 bij 19. √ We bekijken deze eigenschappen aan de hand van 52. De wijzergetallen kunnen we natuurlijk met een rekenmachine achterhalen, zoals we eerder deden met π, maar we kunnen √ dit √ ook doen door exact te rekenen. We maken eerst een afschatting van 52. 52 ligt tussen 7 en 8 in. Dus de kettingbreuk begint met √

√ 52 = 7 + ( 52 − 7) √ Vervolgens bepalen we de inverse van de rest 52 − 7 en splitsen het gehele deel weer af: √ √ √ 1 1 52 + 7 52 + 7 52 − 5 √ =√ ·√ = =4+ 3 3 52 − 7 52 − 7 52 + 7 We maken hier gebruik van het wegwerken van wortels uit de noemer door √ middel van vermenigvuldiging met √52+7 = 1. Deze 1 is zo gekozen dat er in 52+7 2 2 de noemer een uitdrukking van de vorm (a √ + b)(a − b) = a − b ontstaat. Het gehele deel achterhalen we doordat 14 < 52 + 7 < 15.

¨ 3.3. PERIODICITEIT EN SYMMETRIEEN

21

Dit proces herhalen we met de ontstane resten. We krijgen achtereenvolgens: 3 √ 52 − 5 9 √ 52 − 4 4 √ 52 − 4 9 √ 52 − 5 3 √ 52 − 7

= = = = =

3 √ 52 − 5 9 √ 52 − 4 4 √ 52 − 4 9 √ 52 − 5 3 √ 52 − 7

· · · · ·

√ 52 + 5 √ 52 + 5 √ 52 + 4 √ 52 + 4 √ 52 + 4 √ 52 + 4 √ 52 + 5 √ 52 + 5 √ 52 + 7 √ 52 + 7

= = = = =

√ 3( 52 + 5) 27 √ 9( 52 + 4) 36 √ 4( 52 + 4) 36 √ 9( 52 + 4) 27 √ 3( 52 + 7) 3

= = =

√ √ √ √

52 + 5 =1+ 9 52 + 4 =2+ 4 52 + 4 =1+ 9

√ √ √

52 − 4 9 52 − 4 4 52 − 5 9

52 − 7 3 √ √ = 52 + 7 = 14 + 52 − 7 =

52 + 5 =4+ 3

√

√ Deze rest 52−7 is precies de rest waar we in de eerste stap mee zijn begonnen. Dat betekent dat we vanaf nu steeds hetzelfde rijtje resten zullen tegenkomen. Hiermee zullen dus ook de gevonden wijzergetallen periodiek terugkeren! We √ hebben√ de periodiciteit van 52 vastgesteld. Merk op dat alle resten van de vorm NQ−P zijn. √ We generaliseren dit voorbeeld. We willen de periodiciteit van N , N ∈ N en geen kwadraat, aantonen. Het is voldoende te laten zien dat er maar eindig veel resten mogelijk zijn. Dan zal namelijk bij een oneindige voortzetting van het bepalen van de resten, in ieder geval dezelfde rest een keer terug keren! √ is, met 0 < P < N en Q is een √ deler van N − P 2 . Dit is zeker waar voor de eerste rest, N − P . Maar als we van één rest weten dat hij deze vorm heeft, dan weten we het van de volgende rest ook, immers, We beweren dat elke rest van de vorm

√

N −P Q

√ √ √ Q N +P N − P′ Q( N + P ) √ = = = a + N − P2 Q′ Q′ N −P N − P2 . Dus is ook Q′ natuurlijk een deler van N − P 2 . Verder Q verschillen P en −P ′ een Q-voud. Dus deelt Q′ ook N − P ′2 . Omdat we de √ resten positief kozen, geldt ook dat P ′ < N . Hieruit volgt dat er maar eindig veel kwadraten van N kunnen worden afgetrokken! Omdat N geen kwadraat is, zal N − P 2 6=√ 0 dus het proces gaat oneindig lang door. Hiermee is de periodiciteit van N aangetoond. Hierin is Q′ =

In verband met het volgende hoofdstuk, de vergelijking van Pell, vermelden we nog een belangrijk eigenschap (zonder bewijs).

22


Eigenschap 3.3.1 Als N ∈ N en N is geen kwadraat, dan heeft de kettingbreuk √ van N de gedaante √ N = [a0 , a1 , a2 , · · · , an , 2a0 ] √ met a0 = ⌊ N ⌋. Bovendien geldt [a1 , a2 , · · · , an ] = [an , · · · , a2 , a1 ].

3.4

Kalender

Zo’n 2000 jaar geleden veranderde Julius Caesar de Egyptische kalender die uitging van een jaar van precies 365 dagen. De Juliaanse kalender bestond uit een periode (cyclus) van 1461 dagen, namelijk 3 jaren van 365 dagen en 1 jaar van 366 dagen, een schrikkeljaar. Het jaar bestond dus gemiddeld uit 365, 25 dagen, een aardige benadering van het tropisch jaar, de gemiddelde omlooptijd van de aarde rond de zon. In ons tijdperk, AD 2000 duurt een tropisch jaar 365, 24219878 dagen. Ter vergelijking: 2000 jaar geleden duurde het tropisch jaar 20 seconden korter. Julius Caesar De Gregoriaanse kalender werd in 1582 ingevoerd door paus Gregorius XIII. De oude Juliaanse kalender was gaan achterlopen op de situatie in de natuur. Elke duizend jaar loopt de Juliaanse kalender ongeveer 7, 8 dagen voor. Om deze afwijking te corrigeren werd het systeem van schrikkeljaren aangepast, zodat elk jaartal dat deelbaar was door 100 voortaan geen schrikkeljaar is, behalve als het ook deelbaar is door 400. Dat betekent dat bijvoorbeeld 1600, 2000 en 2400 schrikkeljaren zijn, maar 1700, 1800, 1900, 2100, 2200 en 2300 niet. Het gemiddelde Gregoriaanse jaar duurt hierdoor 365, 2425 dagen. Per 1000 jaar worden er daardoor gemiddeld 7, 5 dagen gecorrigeerd. Ook besliste de paus dat er tien dagen geschrapt zouden worden. Het gevolg van de Gregoriaanse wijzigingen was ondermeer dat de dagen tussen 4 oktober 1582 en 15 oktober 1582 nooit hebben bestaan. Een ander gevolg was dat er in Europa gedurende lange periode twee kalenders hebben bestaan. In protestante landen voelde men er niet veel voor de plannen van de paus zomaar over te nemen. Uiteindelijk gingen in 1700 de meeste Nederlandse gewesten, Denemarken en Zwitserland over op de Gregoriaanse kalender. Engeland volgde pas in 1752 en Zweden nog een jaar later. We kunnen ons afvragen of er niet betere kalenders zijn dan de Juliaanse- of Gregoriaanse kalender. We hebben te maken met een cyclus, waarvan sommige jaren schrikkeljaren zijn, terwijl het gemiddelde jaar zo nauwkeurig mogelijk de omlooptijd van de aarde rond de zon (het tropisch jaar) moet benaderen. De periode lengte moet kort zijn of gemakkelijk in gebruik. Bijvoorbeeld de cyclus van 4 jaar van de Juliaanse kalender en de 400 jarige cyclus van de Gregoriaanse

23

3.4. KALENDER

kalender zijn gemakkelijk in gebruik, maar de Hebreeuwse 19 jarige cyclus niet. Je hebt dan een rekenmachine nodig om de schrikkeljaren uit te rekenen. We nemen een cyclus van q jaren met daarin p schrikkeljaren. Dan zijn er gedurende 1 cyclus 365q + p dagen verstreken. Dat wil zeggen dat de gemiddelde lengte van een jaar komt op: 365q + p p = 365 + q q We zijn dus op zoek naar de best mogelijke breuk pq die het getal α = 0, 24219878 benadert. Hiervoor zijn bijvoorbeeld de convergenten van de kettingbreuk ontwikkeling van α geschikt. We krijgen 1

0, 24219878 =

1

4+

1

7+

1

1+ 3+ De bijbehorende rij convergenten zijn

1 5 + ···

p1 1 p2 7 p3 8 p4 31 p5 163 = , = , = , = , = q1 4 q2 29 q3 33 q4 128 q5 673 De eerste breukbenadering hoort bij het 4 jarige cyclus systeem met 1 schrikkeldag van de Juliaanse kalender. De overige benaderingen zijn weliswaar nauwkeuriger, maar lastiger om mee te rekenen, hoewel een 33 jarige periode met 8 schrikkeljaren een serieuze optie is geweest. Een dergelijke kalender is inderdaad nauwkeuriger dan de tegenwoordige Gregoriaanse kalender, maar minder nauwkeurig dan bijvoorbeeld de kalender met een 500 jarige cyclus die hierna wordt besproken. We bekijken cycles van enkele jaren lang. Neem q = 100q ′ , waarbij q ′ een geheel getal is tussen de 1 en de 9 zijn. We benaderen nu α′ = 100α = 24, 219878 met convergenten. De kettingbreuk ontwikkeling wordt: α′ = [24, 4, 1, 1, 4, · · · ] De eerste vier convergenten zijn: p1 97 p2 121 p3 218 p4 993 = , = , = , = q1 4 q2 5 q3 9 q4 41 We zien drie kandidaten voor de kalender. De eerste correspondeert met onze Gregoriaanse kalender. Deze is gebaseerd op een 400 jarige cycle met 97 schrikkeljaren; namelijk alle jaren deelbaar door 4 (hier zijn er 100 van), behalve de honderdvouden 100, 200 en 300. De volgende benadering 121 5 hoort bij een cyclus van 500 jaar met daarin 121 schrikkeljaren. Bij deze kalender is elk jaar dat je kunt delen door 4 een schrikkeljaar, behalve als het deelbaar is door 100 met de uitzondering dat jaren deelbaar door 500 die wel weer schrikkeljaren zijn. Dit systeem is net zo simpel

24


als de Gregoriaanse kalender, maar veel nauwkeuriger. De Gregoriaanse kalender is 26 seconde langer dan een tropisch jaar; een fout van 1 dag elke 3320 jaar. De kalender met een cyclus van 500 jaar is 17 seconde korter dan een tropisch jaar; een fout van 1 dag elke 5031 jaar. De paus had dit niet door! De laatste breukbenadering is een kalender met een cyclus van 900 jaar met 218 schrikkeljaren. Er zijn echter 7 uitzonderingen op de 4 jarige schrikkel- regel (218 = 900 4 − 7), waardoor deze kalender onnodig ingewikkeld wordt en dus niet handig is.

3.5

Sectio divina

De gulden snede, ook bekend onder de namen gulden verhouding, gulden nummer, gulden getal of sectio divina, is een irrationaal getal, ongeveer 1, 618033988749894. Dit getal geeft een verhouding weer die veelvuldig in de natuur wordt aangetroffen. Daarnaast wordt deze verhouding in de klassieke architectuur gezien als de meest aangename, bijvoorbeeld bij de bouw van het theater van Epidaurus (Griekenland). Dit theater is een reusachtige schelp dat tegen de flank van een heuvel ligt. Gebouwd in de vierde eeuw voor Christus door de architect Polycletus de Jongere uit Argos volgens zuiver wiskundige principes. Het biedt plaats aan 14000 toeschouwers en de akoestiek is fantastisch! Er zijn 55 rijen zitplaatsen: 34 onder het middenpad (diazoma), verdeeld in 12 sectoren, en 21 rijen boven de diazoma, verdeeld in 22 sectoren. 55 Merk op dat 34 21 = 34 ≈ 1, 61 · · · , de gulden snede. Euclides heeft aangegeven hoe een lijnstuk verdeelt dient te worden om de gulden snede te krijgen, deel een lijn of lengte zodanig in twee ongelijke delen, dat de verhouding van het kleine tot het grote dezelfde is als die van het grote deel tot het geheel. Neem lijnstuk AB met daarop een punt S. Noem AS = a en BS = b. Kies punt S zo, dat

a A

a a+b = b a

b S

B

De verhouding ab wordt aangegeven met de Griekse letter φ, het zogenaamde gulden getal. Hieruit volgt dat φ=

a a+b b 1 = =1+ =1+ b a a φ

Vervangen we nu aan de rechterzijde van φ = 1 +

1 φ

telkens φ door 1 + φ1 , dan

25

3.6. OEFENINGEN

krijgen we de kettingbreukontwikkeling, 1

φ=1+

1

1+

1

1+ 1+

1 1 + ···

Dus φ = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, · · · ].

Wanneer we de convergenten berekenen met behulp van

krijgen we de tabel, am pm qm

0 1

1 0

1 1 1

1 2 1

1 3 2

1 5 3

1 8 5

1 13 8

1 21 13

am pm−1 + pm−2 pm = qm am qm−1 + qm−2

1 34 21

1 55 34

De teller en noemers van de convergenten zijn precies de getallen uit de rij 55 van Fibonacci. Ook herkennen we de verhoudingen 34 21 en 34 uit het theater van Epidaurus in Griekenland. De waarde van φ wordt dus benaderd door de verhouding van twee opeenvolgende getallen in de rij van Fibonacci. Overigens kunnen we met behulp van bijvoorbeeld de ABC-formule ook de gulden verhouding achterhalen. Immers, uit φ = 1 + φ1 volgt de vierkantsvergelijking √ 1 + 5 φ2 − φ − 1 = 0, met de positieve oplossing φ = ≈ 1, 6180339887499 · · · . 2 Ofwel,

3.6

√ 1+ 5 φ= = [1, 1, 1, 1, 1, 1, 1, · · · ] 2

Oefeningen

Oefening 3.6.1 Bepaal de eerste 10 convergenten van 12 + Laat zien dat inderdaad voor elke convergent pq geldt dat, α −

1 2

√ 7.

p 1 < q q2

Oefening 3.6.2 Langzaam ontstaat er in de Gregoriaanse kalender een fout. Met af en toe een correctie wordt deze fout gecorrigeerd. Hiervoor bekijken we langere cycles met lengten van 400 jaar, q = 400q ′ . Bereken met behulp van kettingbreuken wanneer er een schrikkeljaar komt te vervallen.

Oefening 3.6.3 φ, de gulden snede verhouding is ook als volgt te construeren:

26


Neem een vierkant ABCD met zijde 1. Kies E op het midden van AB. Teken een cirkel met middelpunt E en straat EC. Laat D C G het snijpunt zijn van de cirkel met het verlengde van AB. AB = φ. Toon aan dat geldt: BG A

E

B

G

Oefening 3.6.4 Welke (irrationale) getallen horen bij de volgende kettingbreuken: [1, 1, 2, 1, 2, 1, 2, 1, 2, · · · ] [1, 2, 1, 2, 1, 2, 1, 2, · · · ] [0, 1, 10, 5, 10, 5, 10, 5, 10, · · · ] [2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, · · · ] √

21,

√

28 √ √ Oefening 3.6.6 Ontwikkel in kettingbreuken: a2 + 1, a2 + a, waarin a een willekeurig positief geheel getal is. (Hint: gebruik de methode uit paragraaf 3.3)

Oefening 3.6.5 Ontwikkel in kettingbreuken:

Oefening 3.6.7 Gegeven is de vergelijking: 55x2 − 125x + 71 = 0. Bepaal de kettingbreukontwikkeling van de positieve oplossing van deze vergelijking. Oefening 3.6.8 Gegeven is de vergelijking: bx2 − abx − a = 0, waarbij a en b natuurlijke getallen zijn. Bepaal de kettingbreukontwikkeling van de positieve oplossing van deze vergelijking. Oefening 3.6.9 In de kettingbreukontwikkeling van het getal e zit een regelmaat. Onderzoek een soortgelijke regelmaat in de kettingbreukontwikkeling van √ ek + 1 . e2 , e en k e −1

Hoofdstuk 4

De vergelijking van Pell 4.1

Diophantische vergelijkingen

In Hoofdstuk 2 hebben we oplossingen bepaald van de vergelijking ax + by = c. Deze vergelijking is een voorbeeld van een Diophantische vergelijking. Een Diophantische vergelijking is een vergelijking in meerdere variabelen, waarvan de oplossingen gehele getallen moeten zijn. Het type vergelijking is genoemd naar de Griekse wiskundige Diophantus van Alexandrië. Hij leefde in de derde eeuw n.C. en schreef onder andere de Arithmetica, een boekwerk waarin een grote verzameling Diophantische vergelijkingen worden beschreven en opgelost. Over Diophantus zelf weten we bijna niets, alleen stond in een Griekse Anthologie van Metrodorus uit de zesde eeuw de volgende opmerking: Zijn jeugd maakte een zesde van zijn leven uit; na een verder twaalfde kreeg hij een baard; na een verder zevende trouwde hij en zijn zoon werd 5 jaar daarna geboren; de zoon werd maar half zo oud als zijn vader en de vader overleed vier jaar na de zoon. Dit voorbeeld geeft aanleiding tot een Diophantische vergelijking in 1 variabele van graad 1. Een beetje flauw om op te lossen. Andere voorbeelden van Diophantische vergelijkingen zijn: • x − 2y = 1: Het aantal gehele oplossingen (x, y) van deze vergelijking is oneindig. Voorbeelden van oplossingen zijn (3, 1), (5, 2), · · · • xn + y n = z n . Voor n = 2 zijn de gehele oplossingen de Pythagorese drietallen, hiervan zijn er oneindig veel. Voorbeelden zijn (3, 4, 5), (5, 12, 13), · · · . Voor n > 2 zegt de laatste stelling van Fermat dat er geen gehele getallen (x, y, z) bestaan die aan de vergelijking voldoen. • x2 − N y 2 = 1. Deze vergelijking staat bekend als de vergelijking van Pell, door Euler abusievelijk toegewezen aan de Engelse wiskundige John Pell (1611 - 1685). De vergelijking is reeds eeuwen daarvoor uitvoerig bestudeerd door Indische wiskundigen. Fermat bewees dat deze vergelijking altijd een oplossing heeft, behalve wanneer N een kwadraat is. De 27

28

HOOFDSTUK 4. DE VERGELIJKING VAN PELL

oplossing is te vinden in een eindig √ aantal stappen door met behulp van kettingbreuken een benadering van N te zoeken.

4.2

Pell nader bekeken

We bekijken een Diophantische vergelijking die er door zijn bijzondere eigenschappen al vroeg in de geschiedenis uitsprong. Stel dat N ∈ N geen kwadraat is. De vergelijking van Pell wordt gegeven door, x2 − N y 2 = 1 waarbij x, y ∈ Z≥0 . Neem bijvoorbeeld N = 2. We willen dus gehele positieve oplossingen vinden van de vergelijking x2 − 2y 2 = 1. Door enig proberen vinden we een oplossing (17, 12), immers 172 − 2 · 122 = 1. Met enig geduld of een computer vind je ook 902 − 2 · 702 = 1. Het zal blijken dat de lijst oplossingen oneindig lang is! Wanneer we in plaats van N = 2 een andere waarde van N nemen, dan zijn er steeds oplossingen te vinden, natuurlijk andere dan de triviale oplossing x = 1, y = 0. Dit werd reeds in de oudheid ontdekt en men vond het blijkbaar erg belangrijk. Soms moeten we wel lang zoeken naar oplossingen, bijvoorbeeld bij N = 61. De kleinste oplossing is 17663190492 − 61 · 2261539802 = 1. Het is duidelijk dat een dergelijke oplossing niet gevonden is door zomaar lukraak te proberen. In 1657 vond de Engelse wiskundige W. Brouncker een oplossingsmethode. Met deze oplossingsmethode vond hij bijvoorbeeld de kleinste niet triviale oplossing voor de vergelijking x2 − 313y 2 = 1: x = 32188120829134849

y = 1819380158564160

Een spectaculair resultaat! We bekijken de methode van Brouncker, die gebruik maakt van kettingbreuken. De volgende stelling zegt dat er in ieder geval één oplossing bestaat. Wanneer we de kleinste niet triviale oplossing van de vergelijking van Pell hebben, kunnen we de volledige oplossingsverzameling bepalen. Stelling 4.2.1 Stel N ∈ N en N is geen kwadraat. Dan bestaan er x, y ∈ Z>0 z´ o dat x2 − N y 2 = 1. Voor N = 2, 3 is de stelling zeker waar, want 32 − 2 · 22 = 1 en 22 − 3 · 12 = 1. We kunnen dus aannemen dat N > 4. √ We bekijken de kettingbreukontwikkeling van N . Deze is periodiek en zoals we eerder gezien hebben wordt deze gegeven door, √ N = [a0 , a1 , a2 , · · · , ar , 2a0 ], √ met a0 = ⌊ N ⌋. We nemen het eerste wijzergetal en het periodieke deel van de wijzergetallen, m.u.v. het laatste, en noemen de convergent pq , dus p = [a0 , a1 , a2 , · · · , ar ] q

4.2. PELL NADER BEKEKEN

29

Met behulp van de afschattingen voor convergenten van kettingbreuken (zie opgave 4.4.3) zien we dat p2 − N q 2 = (−1)r−1 Wanneer r oneven is, dus p2 − N q 2 = 1, kun je de oplossingen gewoon aflezen. Wanneer r even is, dus p2 − N q 2 = −1, dan vind je de oplossingen door eerst links en rechts te kwadrateren, zodat je krijgt (p2 − N q 2 )2 = (p2 + N q 2 )2 − N (2pq)2 = 1 en de oplossingen weer simpelweg af te lezen zijn. Samengevat zijn de oplossingen van de vergelijking van Pell: • Als p2 − N q 2 = 1, dan is een oplossing x = p en y = q • Als p2 − N q 2 = −1, dan is een oplossing x = p2 + N q 2 en y = 2pq Laten we als voorbeeld N = 61 bekijken. We zoeken dus oplossingen van de vergelijking x2 − 61 · y 2 = 1 √ De kettingbreuk van 61 is, √ 61 = [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1, 14] Hieruit volgt dat 29718 p = [7, 1, 4, 3, 1, 2, 2, 1, 3, 4, 1] = q 3805 Nu is 297182 −61·38052 = −1 dus een oplossing van de vergelijking x2 −61·y 2 = 1 is x = 297182 + 61 · 38052 = 1766319049 en y = 2 · 29718 · 3805 = 226153980. We weten nu dat er een niet triviale oplossing van de vergelijking van Pell bestaat en we weten hoe we die oplossing kunnen vinden. Maar er bestaan oneindig veel oplossingen! Om dit in te zien bekijken we de vergelijking met N = 2, dus x2 − 2 · y 2 = 1. We zagen eerder dat (17, 12) een oplossing is, want 172 − 2 · 122 = 1. Deze gelijkheid is met behulp van het√merkwaardig√product a2 − b2 = (a + b)(a − b) ook te schrijven (17 + √ 12 2)(17 − 12 2) = 1. √ als 2 2) (17 − 12 2)2 = 1. We Kwadrateer nu beide zijden, √ 2dus (17 + 12 √ √ werken de kwadraten uit: (17 + 12 2) = 289 + 408 2 + 288 = 577 + 408 2√ en evenzo √ 2 √ √ 2 (17 − 12 2) = 577 − 408 2. √ We kunnen (17√+ 12 2) (17 − 12 2)2 = 1 dus ook schrijven als (577 + 408 2)(577 − 408 2) = 1. Dit wil zeggen dat x = 577 en y = 408 ook een oplossing is van x2 − 2 · y 2 = 1! Nemen√we nu in plaats van vinden we via (17 + 12 2)3 = √ kwadraten √ derde machten dan √ (577 + 408 2)(17 + 12 2) = 19601 + 13860 2 de oplossing x = 19601 en y = 13860. Door nu steeds hogere machten te kiezen krijgen we een oneindige rij oplossingen! Bovendien geldt dat wanneer we starten met de kleinste niet triviale oplossing van de vergelijking we zelfs alle oplossingen vinden. Algemeen kunnen we zeggen dat (zonder bewijs),

30


Stelling 4.2.2 Als (p, q) met p, q ∈ Z>0 de kleinste oplossing is van de verge− N y 2 = 1, dan er bij iedere oplossing x, y ∈ N een n ∈ N z´ o lijking x2 √ √ bestaat n dat x + y N = (p + q N ) .

4.3

Knikkers

In deze paragraaf bekijken we een toepassing van de vergelijking van Pell. Stel we hebben een voorraad even grote knikkers. Na enig puzzelen blijkt dat we de knikkers zowel in een driehoekig patroon als in een vierkant patroon kunnen neer leggen. Hoeveel knikkers hebben we gebruikt? Eén (triviale) oplossing is onmiddellijk duidelijk, 1 knikker. Maar zijn er meer mogelijkheden? Je vindt wellicht dat je met 36 knikkers dit ook kunt realiseren:

=

Figuur 4.1: D8 = V6

Het aantal knikkers in een vierkant patroon noemen we vierkantsgetallen Vn , ofwel de kwadraten. Dus V1 = 1, V2 = 4, V3 = 9, V4 = 16, V5 = 25, V6 = 36, etc. Het aantal knikkers in een driehoekig patroon noemen we driehoeksgetallen Dn . Merk op dat we de driehoeksgetallen vinden door opeenvolgende natuurlijke getallen op te tellen, te beginnen bij 1. Dus D1 = 1, D2 = 1 + 2 = 3, D3 = 1 + 2 + 3 = 6, D4 = 1 + 2 + 3 + 4 = 10, D5 = 1 + 2 + · · · + 5 = 15, D6 = 1+2+· · ·+6 = 21, D7 = 1+2+· · ·+7 = 28, D8 = 1+2+· · ·+8 = 36, etc. Wie zien dat D8 = V6 . Met 36 knikkers kunnen we dus zowel een driehoekig patroon als een vierkant patroon vullen! n(n + 1) We kunnen driehoeksgetallen uitrekenen met de formule Dn = . Om 2 alle oplossingen te vinden moeten we de vergelijking Vm = Dn oplossen. Dus, n(n + 1) 2 Deze vergelijking kunnen we herschrijven tot m2 =

(2n + 1)2 − 8m2 = 1

4.4. OEFENINGEN

31

Ofwel een Pell vergelijking met N = 8. De kleinste oplossing is 32 − 8 · 12 = 1, corresponderend met m = 1, de triviale oplossing √ van 1 knikker. Alle andere oplossingen krijgen we door de machten van 3 + 8 uit te werken, √ √ (3 + 8)2 = 17 + 6 8 m2 = 62 = 36 √ √ 3 m2 = 352 = 1225 (3 + 8) = 99 + 35 8 √ √ (3 + 8)4 = 577 + 204 8 m2 = 2042 = 41616 .. . De conclusie is dat er oneindig veel oplossingen zijn om een aantal knikkers zowel in een driehoekig patroon als in een vierkant te leggen. Ook zien we dat de rij getallen zeer snel groeit. Je hebt dus ruim voldoende knikkers nodig als je ze daadwerkelijk wilt neerleggen!

4.4

Oefeningen

Oefening 4.4.1 Bekijk de opgave over Diophantus in de eerste paragraaf van dit hoofdstuk. Hoe oud was Diophantus? Oefening 4.4.2 Bepaal de kleinste oplossing van de vergelijking x2 − 2 · y 2 = 1 Oefening 4.4.3 Bepaal enkele oplossingen van de vergelijking x2 − 2 · y 2 = 1 door te beginnen met de kleinste oplossing uit de vorige oefening. Laat zien dat de oplossingen die in de tekst vermeld staan ook voorkomen in deze rij oplossingen. Oefening 4.4.4 (Lastig) Laat zien dat uit de afschattingen voor convergenten van een kettingbreuk, p √ − N < 1 q 2a0 q 2 de oplossingen van de vergelijking van Pell volgen.

Oefening 4.4.5 Laat zien dat uit de gelijkheid Vm = Dn de Pell vergelijking (2n + 1)2 − 8m2 = 1 volgt. Oefening 4.4.6 (Lastig) De aantallen knikkers, die zowel in een driehoekig patroon als in een vierkant gelegd√kunnen worden, kunnen we ook recursief √ bepalen. Stel namelijk dat xn + yn 8 = (3 + 8)n . We interesseren ons voor yn , want dat stelt de zijde m van √ het vierkant √ voor. Bepaal met behulp van de kwadratische vergelijking (3 + 8)2 = 6(3 + 8) − 1 een recursie formule voor yn+2 . Laat tevens zien dat wanneer je start met y0 = 0 en y1 = 1 je de waarden van m krijgt.

32


Tot slot enkele√opgaven waarbij het getal l(N ), de periodelengte van de kettingbreuk van N een rol speelt. Oefening 4.4.7 Neem een aantal waarden van N en bepaal de kettingbreuk en een oplossing van de Pell-vergelijking. Maak een tabel met daarin de waarden N en l(N ). Oefening 4.4.8 Het kan gebeuren dat N heel groot is en l(N ) heel klein. Dat zien we in deze opgave. √ Bepaal de kettingbreuk van een willekeurig getal van de vorm n2 + 1. (Hint: vergelijk opgave 3.6.6). Zie je ook een oplossing van de Pell-vergelijking met N = n2 + 1? √ Dezelfde vraag, maar nu voor getallen van de vorm 4n2 + 4. Oefening 4.4.9 We kijken naar waarden van N waarvoor geldt dat√l(N ) = 2. Kies a, b positief en geheel. Stel je wilt weten welk getal x = N een kettingbreuk van de vorm [a, b, 2a, b, 2a, b, 2a, · · · ] heeft (als zo’n N bestaat). Laat zien dat geldt: 1 x=a+ 1 b+ a+x Los hieruit x op. Aan welke voorwaarde moet a, b voldoen zodat de gevonden x2 geheel is?

Hoofdstuk 5

Eindopdrachten 5.1

De Slag bij Hastings

Misschien heb je wel gehoord van het tapijt van Bayeux. In het Franse stadje Bayeux hangt een linnen doek (’tapijt’) van ongeveer 70 meter lang en 50 cm hoog, waarop net als bij een stripverhaal, 58 taferelen geborduurd zijn. Deze taferelen geven onder meer de slag bij Hastings in 1066 weer. In totaal heeft men op het tapijt onder andere 626 personen, 202 paarden, 41 schepen en 37 gebouwen geteld. Op een latere datum is ook een boekje geschreven over die slag bij Hastings van 14 oktober 1066: de Carmen de Hastigae Proelio door Guy, Bisschop van Amiens. In dit boekje staat een bewering, welke we in deze opdracht in twijfel zullen trekken. Er staat: Harold’s mannen stonden als gewoonlijk dicht samengedromd in 13 vierkanten van gelijke grootte, en wee de Noorman die het waagde in zulk een falanx te willen indringen. Maar toen Harold zelf op het slagveld verscheen, vormden de Saksen één gigantisch vierkant met hun Koning aan de top en stormden voorwaarts onder de strijdkreten ”Ut!”, ”Olicrosse!” en ”Godemitte!”. De ”Saksen”(d.w.z. Harold’s mannen) zijn hier trouwens de ”Angelsaksen”die in de vijfde eeuw vanuit Duitsland naar Engeland migreerden.

Figuur 5.1: Ubi Harold dux Anglorum et sui milites equitant ad Bosham - Waar Harold, een Engelse graaf, en zijn soldaten naar Bosham rijden.

33

34

HOOFDSTUK 5. EINDOPDRACHTEN

Opdracht 1 Als x het aantal manschappen op een rij in het grote vierkant en y dat in het kleine vierkant is, wat is dan het verband tussen x en y? Als het goed is, heb je de vergelijking x2 − 13y 2 = 1 gevonden die de vergelijking van Pell genoemd wordt, hoewel John Pell niets met de vergelijking te maken had. Door een misverstand schreef Euler de oplossingsmethode die door Brouncker was ontdekt, toe aan Pell. Opdracht 2 Bepaal de kleinste oplossing van de vergelijking x2 − 13y 2 = 1. Opdracht 3 laat zien x2 − 13y 2 = 1 equivalent is met de vergelijking √ dat de vergelijking √ (x + y 13)(x − y 13) = 1. Opdracht 4 Bewijs dat de vergelijking x2 − 13y 2 = 1 oneindig veel oplossingen heeft. Opdracht 5 Hoe groot was volgens Guy, dus het leger van Harold minstens? Lijkt je dat realistisch? Om de laatste vraag te beantwoorden moet je eigenlijk de bevolkingsaantallen van Engeland uit de Middeleeuwen kennen. Zoek dat in betrouwbare bronnen op internet op. Harold, de koning van Engeland verloor overigens de Slag tegen Willem van Normandië · · · Op de webpagina die bij dit Zebradeeltje hoort, kun je meer informatie vinden over De Slag bij Hastings.

5.2

Computer practicum

In deze opdracht ga je kettingbreuken met behulp van een spreadsheet bekijken. Wanneer je MS Office gebruikt is dit MS Excel. Ook kun je het gratis kantoorpakket OpenOffice.org downloaden met daarin Calc. De Nederlandstalige OpenOffice.org is te downloaden via nl.openoffice.org Opdracht 1 Bestudeer in de tekst hoe het Euclidisch algoritme om de grootste gemeenschappelijke deler (ggd) van twee gehele getallen te bepalen werkt. Opdracht 2 Maak in je spreadsheet een werkblad waarmee je de ggd van twee gehele getallen kunt bepalen.

35

5.2. COMPUTER PRACTICUM

Opdracht 3 We kunnen gewone breuken als kettingbreuken schrijven. Voorbeeld: 65 1 1001 =9+ = 9 + 104 = 9 + 104 104 65

1 39 1+ 65

1

=9+

1+

1

= ···

65 39

Breid je werkblad uit zodat de wijzergetallen van de kettingbreuk worden gegeven. Bekijk de oneindige kettingbreukontwikkeling: x = [1, 2, 1, 2, 1, 2, · · · ]. We kunnen dit ook schrijven als x = [1, 2, x] ofwel: x=1+

1 2+

1 x

Uitwerking geeft x=1+

1 2+

1 x

=1+

x 3x + 1 = 2x + 1 2x + 1

Ofwel de vierkantsvergelijking 2x2 − 2x − 1 = 0 met oplossingen x = √ Inderdaad geldt dat 12 + 12 3 = [1, 2].

1 2

±

1 2

√ 3.

Opdracht 4 Bepaal van enkele oneindige kettingbreukontwikkelingen hun kwadratische vergelijking en vind de oplossingen. Opdracht 5 Kun je een grafische rekenmachine programmaatje schrijven om oneindige kettingbreuken decimaal te benaderen? Opdracht 6 Schrijf een programma op je grafische rekenmachine dat bij invoer van N de repeterende decimalen van N1 plot in porties van 10 decimalen.

36

HOOFDSTUK 5. EINDOPDRACHTEN

Hoofdstuk 6

Verder werken De tekst in dit boekje is zo gepresenteerd, dat het vermoeden kan bestaan dat het onderwerp kettingbreuken wiskundig gezien ’af’ is. Dit is niet het geval. Kettingbreuken blijft onderwerp van onderzoek en studie, wat valt binnen het vakgebied van de getaltheorie. Vaak zijn het eenvoudige kenmerken die opvallen als je aan kettingbreuken gaat rekenen, maar die lastig of (nog) niet te bewijzen zijn. Voor (aanstaande) wiskundigen is er op dit terrein dus nog ruim voldoende werk te verrichten. In dit hoofdstuk staan een aantal onderwerpen die met kettingbreuken te maken hebben, maar niet in deze vorm behandeld zijn in dit boekje. Opgaven begeleiden de tekst. Waar nodig kan gebruik gemaakt worden van de website die hoort bij dit boekje (zie voorwoord).

6.1

Vermoeden van Zaremba

Een getal x kan worden weergegeven als een kettingbreuk, 1

x = a0 + a1 +

1 a2 + · · ·

We schrijven dit als x = [a0 , a1 , a2 , · · · ]. De kettingbreukontwikkeling is eindig of oneindig, maar als x rationaal is, dan is de ontwikkeling eindig. In dit geval zijn er twee mogelijke manieren om de kettingbreukontwikkeling te noteren: één met het laatste wijzergetal ak en één met laatste wijzergetal 1 (het voorlaatste wijzergetal is dan ak − 1). Voorbeeld, 7 = [0, 2, 3, 2] = [0, 2, 3, 1, 1] 16 Het vermoeden van Zaremba. We nemen een willekeurig geheel getal m > 1. Dan bestaat er een geheel getal a, 0 < a < m en ggd(a, m) = 1, z´ o dat de kettingbreukontwikkeling a = [0, a , a , · · · , a ] wijzergetallen a heeft, waarvoor geldt dat alle ai ≤ B 1 2 i k m voor 1 ≤ i ≤ k. B is een kleine absolute constante, bijvoorbeeld 5, welke onafhankelijk is van m. 37

38

HOOFDSTUK 6. VERDER WERKEN

Zaremba heeft dit alleen kunnen bewijzen voor ai ≤ C ln(m).

Oefening 6.1.1 Kies een aantal noemers, bijvoorbeeld 11, 13, 17, etc. Bepaal met behulp van de applet op de ondersteunende internetpagina de bijbehorende waarde van B.

6.2

Elementaire functies

Tot nog toe hebben we kettingbreukontwikkelingen bepaald van rationale en irrationale getallen (breuken, wortels, pi en e). Steeds gingen we uit van kettingbreuken waarbij de ’teller’ gelijk is aan 1. We bekijken nu enkele eenvoudige functies, waarbij we zullen zien dat de teller niet 1 is. De kettingbreukontwikkeling van ln(1 + z) is:

ln(1 + z) =

z 12 z 1+ 12 z 2+ 22 z 3+ 22 z 4+ 32 z 5+ . 6 + ..

Oefening 6.2.1 Kies z = 1 en benader ln(2) op 5 decimalen nauwkeurig met behulp van je rekenmachine. Hoeveel wijzergetallen zijn er nodig? In Hoofdstuk 3 zagen we een kettingbreukontwikkeling voor het getal π. We merken op dat arctan(1) = π4 . De kettingbreukontwikkeling van arctan(z) wordt gegeven door:

arctan(z) =

z 1 · z2 1+ 4z 2 3+ 9z 2 5+ 16z 2 7+ . 9 + ..

Oefening 6.2.2 Bepaal π op 5 decimalen nauwkeurig. Hoeveel wijzergetallen zijn er nodig?

39

6.2. ELEMENTAIRE FUNCTIES

Enkele kettingbreuken die met het getal e te maken hebben: 1

ez = 1−

z z

1+ 2−

z z

3+ 2−

z 5+

z

. 2 − ..

Oefening 6.2.3 Bepaal e en e2 op 5 decimalen nauwkeurig. Vergelijk met opgave 3.6.9. Hoeveel wijzergetallen zijn er nodig? ez − e−z = ez + e−z

z 1+

z2 z2 3+ z2 5+ . 7 + ..

Oefening 6.2.4 Welke waarde moet je voor z invullen als je deren? Doe dit op 5 decimalen nauwkeurig.

e2 − 1 wilt benae2 + 1

Voor de leerlingen die bij wiskunde D een module ’Complexe getallen’ gevolgd hebben. Vervang in bovenstaande uitdrukking z door iz. Dan krijgen we: z

tan(z) = 1−

z2 z2 3− z2 5− . 7 − ..

Oefening 6.2.5 Bepaal tan(1) op 5 decimalen nauwkeurig. Hoeveel wijzergetallen zijn er nodig?

40

HOOFDSTUK 6. VERDER WERKEN

Hoofdstuk 7

Uitwerkingen van de oefeningen Oefeningen hoofdstuk 1

Oefening 1.3.1 37, 246 = 3 · 101 + 7 · 100 + 2 · 10−1 + 4 · 10−2 + 6 · 10−3 Oefening 1.3.2 Het aantal nullen kun je willekeurig lang maken. De decimale ontwikkeling wordt dus niet periodiek en de breuk is derhalve niet rationaal,dus irrationaal. Oefening 1.3.3 1 7 = 0, 142857 2 7 = 0, 285714 3 7 = 0, 428571 4 7 = 0, 571428 5 7 = 0, 714285 6 7 = 0, 857142 De decimalen zijn cyclisch. Steeds hetzelfde rijtje alleen verwisseld. Oefening 1.3.4 Bekijk een willekeurig priemgetal p, waarbij 1p periodelengte p − 1 heeft. Dan vinden we een formule voor de som van de cijfers in die periode. Schrijf 1p als, 1 = 0, a0 a1 a2 · · · ap−1 p 41

42

HOOFDSTUK 7. UITWERKINGEN VAN DE OEFENINGEN

Dus, 1 =0·p+1

10 · 1 = a1 · p + r1

10 · r1 = a2 · p + r2 10 · r2 = a3 · p + r3 .. . 10 · rp−1 = ap−1 · p + 1 Links en rechts van het =-teken optellen geeft, 10 · (r1 + r2 + · · · + rp−1 ) = p · (a1 + a2 + · · · ap−1 ) + r1 + r2 + · · · rp−1 Dus, 9 · (r1 + r2 + · · · + rp−1 ) = p · (a1 + a2 + · · · ap−1 ) Maar r1 + r2 + · · · rp−1 zijn precies alle mogelijke resten bij delen door p, dus r1 + r2 + · · · rp−1 = 1 + 2 + 3 + · · · + p − 1 =

1 p(p − 1) 2

Dat levert op:

1 9 · p(p − 1) = p · (a1 + a2 + · · · ap−1 ) 2 Zodat de som van de cijfers in de periode wordt: Sp = a1 + a2 + a3 + · · · + ap−1 =

9 · (p − 1) 2

Oefening 1.3.5 Vermeld staan de tellers: Eindig decimale breuk: 3, 6, 9, 12, 15, 18, 21, dus 3k, met k ∈ N Zuiver repeterende breuk: 8, 16, 32, 40, · · · Gemengd repeterende breuk: de anderen, dus 1, 2, 4, 5, 7, · · · Oefening 1.3.6

1 . Vermenigvuldig nu beide zijden met x, 1−x x dan krijgen we: x + x2 + x3 + x4 + x5 + · · · = . Vul nu x = 10−6 in, dan 1−x 10−6 1 10−6 + 10−12 + · · · = = 6 . We weten dat 17 = 0, 142857, dus −6 1 − 10 10 − 1 door de meetkundige reeks nu links en rechts met 142857 te vermenigvuldigen krijgen we: 1 + x + x2 + x3 + x4 + · · · =

1 142857 = 6 = 142857 · 10−6 + 142857 · 10−12 + · · · 7 10 − 1 Oefening 1.3.7 Het gemiddelde van de cijfers in de periode van 1p , met periodelengte p − 1 en

43 p een priemgetal, is 4 12 . Immers het gemiddelde wordt uitgerekend door alle getallen op te tellen en te delen door het aantal getallen, hier p − 1.

Oefeningen hoofdstuk 2 Oefening 2.5.1 [a0 , a1 , · · · , an − 1, 1] = a0 +

1 a1 +

..

.+

1

= a0 +

1

a1 +

1 1 an − 1 + 1

1 ..

.+

1 an

Oefening 2.5.2 2 = [0, 8, 2] 17

13 = [0, 2, 1, 1, 6] 33

30 = [0, 1, 2, 1, 2, 1, 2] 41 Oefening 2.5.3 an 0 8 pn 0 1 0 1 qn 1 0 1 8 an pn qn an pn qn an pn qn 30 41 an pn qn

2 2 17

0 0 1

2 1 2

1 0

0 0 1

10 1 10

0 1

1 0

0 0 1

1 1 1

2 2 3

1 3 4

0 1

1 0

0 0 1

2 1 2

2 2 5

2 5 12

0 1

1 1 3

71 = [0, 2, 2, 2, 4, 3] 171

dus convergenten:

1 0

0 1

31 = [0, 10, 1, 5, 5] 336

1 2 5

1 1 11

6 13 33 5 6 65

convergenten: 0, 5 31 336

2 8 11

4 22 53

0 1 2 = 0, en 1 8 17

1 11 15

3 71 171

1 1 2 13 , , en 2 3 5 33

convergenten: 0, 2 30 41

31 1 1 6 , , en 10 11 65 336

convergenten: 0, 1,

convergenten: 0,

2 3 8 11 , , , en 3 4 11 15

1 2 5 22 71 , , , en 2 5 12 53 171

Oefening 2.5.4 pn−1 = 2 qn−1 = 5

x = (−1)n qn−1 = (−1)5 · 2 = −2

y = (−1)n−1 pn−1 = (−1)4 · 5 = 5

44


Dus algemene oplossing: x = −2 · 212 + 33t y = 5 · 212 − 13t

Oefening 2.5.5 Particuliere oplossing: x0 = 2536 y0 = −1585 Dus alle oplossingen worden gegeven door, x = 2536 + 27t y = −1585 − 17t Oefening 2.5.6 Eerst de vergelijking door 8 delen, dus oplossen 27x − 125y = 575 Particuliere oplossing: x0 = −21275 y0 = −4600

Dus alle oplossingen worden gegeven door, x = −21275 + 125t y = −4600 + 27t

Oefeningen hoofdstuk 3 Oefening 3.6.1 an 1 1 4 1 1 1 4 1 pn 0 1 1 2 9 11 20 31 144 175 qn 1 0 1 1 5 6 11 17 79 96 √ 1 1 Noem α = + 7, dan geldt achtereenvolgens 2 2 α − 1 = 0, 8229 · · · < 12 1 1 α − 2 = 0, 1771 · · · < 12 1 1 α − 9 = 0, 02288 · · · < 12 5 5 α − 11 = 0, 01046 · · · < 12 6 6 etc.

1 319 175

1 494 271

45 Oefening 3.6.2 400 × 0, 24219878 = 96 +

1 1

1+

1

7+ 3+

1 2 + ···

De convergenten zijn: 96, 97,

775 2422 , ,··· 8 25

De derde convergent suggereert een 8× 400 = 3200 jarige cyclus met 775 schrikkeljaren. In de Gregoriaanse kalender zijn er 97 schrikkeljaren in een 400 jarige cyclus. In 8 cycli zijn er dus 8 × 97 = 776 schrikkeljaren geweest. Dus elke 3200 jaar 1 schrikkeldag schrappen zorgt ervoor dat we met behulp van de Gregoriaanse kalender een veel nauwkeurigere kalender krijgen! Dit systeem levert een fout op van 1 dag in de 100000 jaar. Oefening 3.6.3 AB AB AB 1 = = = 1√ BG EG − EB EC − EB 2 5−

1 2

√ 1+ 5 = =φ 2

Oefening 3.6.4 √ [1, 1, 2, 1, 2, 1, 2, 1, 2, · · · ] = 3 √ [1, 2, 1, 2, 1, 2, 1, 2, · · · ] = 12 + 12 3 √ [0, 1, 10, 5, 10, 5, 10, 5, 10, · · · ] = 13 + 13 3 √ [2, 1, 1, 1, 4, 1, 1, 1, 4, 1, 1, 1, 4, · · · ] = 7 Oefening 3.6.5 √ 21 = [4, 1, 1, 2, 1, 1, 8] √ 28 = [5, 3, 2, 3, 10] Oefening 3.6.6√ √ a2 + 1 = a +√ ( a2 + 1 − a) √ 1 a2 + 1 + a a2 + 1 + a √ 2 √ ·√ = 2 = a +1+a 2 a + 1 − a2 a2 + √ 1+a √a + 1 − a √ a2 + 1 + a = 2a + ( a2 + 1 + a − 2a) = 2a + ( a2 + 1 − a) Dit √ is dezelfde rest als een stap eerder, dus a2 + 1 = [a, 2a] Evenzo: √ a2 + a = [a, 2, 2a] Oefening 3.6.7 [1, 6, 2, 1]

46


Oefening 3.6.8 [a, b] Oefening 3.6.9 e2 = [7, 2, 1, 1, 3, 18, 5, 1, 1, 6, 30, 8, 1, 1, 9, 42, 11, 1, 1, 12, · · · ] √ e = [1, 1, 1, 1, 5, 1, 1, 9, 1, 1, 13, 1, 1, 17, 1, 1, 21, 1, 1, 25, · · · ] Kies enkele waarden voor k, bijvoorbeeld e+1 k = 1 dan = [2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, · · · ] e−1 e2 + 1 k = 2 dan 2 = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, · · · ] e −1

Oefeningen hoofdstuk 4 Oefening 4.4.1 Stel de leeftijd van Diophantus x, dan wordt de vergelijking x 2 + 4 = x en dus x = 84.

x 6

+

x 12

+

x 7

+5+

Oefening 4.4.2 De kleinste oplossing is: 32 − 2 · 22 = 1. Oefening √ 2 4.4.3 √ (3 + 2√2) = 17 + 12√2, dus x = 17 en y = 12. (3 + 2√2)3 = 99 + 70 2, √ dus x = 99 en y = 70. (3 + 2 2)4 = 577 + 408 2, dus x = 577 en y = 408. Oefening 4.4.4 √ Vermenigvuldig beide zijde van de afschatting met pq + N en maak gebruik √ √ van pq + N ≤ (2 N + 12 ) (Reken na!). We vinden nu: √ 2 p − N < 2 N + q2 2a0 q 2

1 2

√ 2 2 N + 12 2 Vermenigvuldig nu beide zijden zodat we krijgen p − N q < . 2a0 Controleer nu dat √ √ 2 N + 12 2 N + 12 √ = <2 2a0 2⌊ N ⌋ als N > 4. Hieruit volgt dat p2 − N q 2 < 2. Dus p2 − N q 2 = −1 of p2 − N q 2 = 1. Let op dat p2 − N q 2 6= 0. Als p2 − N q 2 = 1 dan hebben we x = p en y = q als oplossing. Als p2 − N q 2 = −1 dan volgt uit (p2 + N q 2 )2 − N (2pq)2 = (p2 − N q 2 )2 de oplossingen x = p2 + N q 2 en y = 2pq. met q 2

47 Oefening 4.4.5 n(n + 1) met 8. Dan krijgen we 2 2 2 8m = 4n + 4n. Links en recht er 1 bij optellen, zodat we aan de rechter kant een merkwaardig product herkennen: 1 + 8m2 = 4n2 + 4n + 1 = (2n + 1)2 . Hieruit volgt dat (2n + 1)2 − 8m2 = 1. Vermenigvuldig beide zijden van m2 =

Oefening 4.4.6 √ √ √ √ Stel xn + yn 8 = (3 + 8)n . We weten (3 + 8)2 = 6(3 + 8) − 1. Verme√ dat nigvuldig nu beide kanten met (3 + √8)n . Dan krijgen we √ n+2 √ n+1 (3 + 8) = 6(3 + 8) − (3√+ 8)n . Hieruit √ √ volgt dat xn+2 + yn+2√ 8 = 6(xn+1 + yn+1 8) − (xn + yn 8). Vergelijk nu de getallen die voor de 8 staan, want die wilden we hebben. We krijgen dan yn+2 = 6yn+1 − yn . Beginnend met y0 = 0 en y1 = 1 krijgen we y2 = 6 · 1 − 1 = 6, y3 = 6 · 6 − 1 = 35, y4 = 6 · 35 − 6 = 204, · · · Wat overeenkomt met m2 = 62 = 36, m2 = 352 = 1225, m2 = 2042 = 41616, · · · Oefening 4.4.7 N 2 3 5 l(N ) 1 2 1

6 2

7 4

8 2

10 1

11 2

13 5

31 8

131 6

Oefening 4.4.8 √ n2 + 1 = [n, 2n]. Hieruit volgt dat pq = [n] = n, met r = 0, p = n en q = 1. De oplossingen van de Pell-vergelijking zijn x = p2 +N q 2 = 2n2 +1 en y = 2pq = 2n, immers invullen in√x2 − (n2 + 1)y 2 = 1 geeft (2n2 + 1)2 − (n2 + 1) · 4n2 = 1. Merk op dat: x = n2 + 1 = [n, 2n] 1 n2 + nx + 1 x=n+ = . Kruislings vermenigvuldigen geeft n+x n+x √ nx + x2 = n2 + nx + 1 ofwel x2 = n2 + 1, met als oplossing x = n2 + 1. √

√ 4n2 + 4 = 2n + (√ 4n2 + 4 − 2n) √ 1 4n2 + 4 + 2n 4n2 + 4 − 2n √ = =n+ 4 4 4n2 + 4 − 2n√ 2 √ √ 4 4 4n + 4 + 8n √ = 4n2 + 4 + 2n = 4n + 4n2 + 4 − 2n = 4 4n2 + 4 √ De resten herhalen zich, dus 4n2 + 4 = [2n, n, 4n]. 1 2n2 + 1 p = [2n, n] = 2n + = . Hieruit volgt dat p = 2n2 + 1 en q = n, met q n n r = 1 dus x = p en y = q. Inderdaad, x2 − (4n2 + 4) · y 2 = (2n2 + 1)2 − (4n2 + 4) · n2 = 1.

48


Oefening 4.4.9 x = [a, b, 2a] = a +

1

, immers vul voor x in de kettingbreuk weer 1 b+ a+x zichzelf in, dan staat er (a + · · · ) + a = 2a + · · · en krijg je weer x. 1 a+x a2 b + abx + a + a + x a+ =a+ = = x. 1 ab + bx + 1 ab + bx + 1 b+ a+x Kruislings vermenigvuldigen geeft abx + bx2 + x = a2 b + abx + 2a + x, dus a2 b + 2a 2 x2 = . x is geheel als b|(a2 b + 2a) ofwel b|a. Met andere woorden er b bestaat een k ∈ N zo dat a = k · b. Voorbeeld: ar = 6 en b = 2. Merk op dat 2 een deler is van 6. Dan is x = r 2 a b + 2a 84 √ = = 42 = [6, 2, 12]. Inderdaad van de vorm [a, b, 2a]. b 2 Oefening 6.2.1 ln(2) = 0, 693147 · · · . Je hebt de eerste 8 wijzergetallen nodig. Oefening 6.2.2 π = 4 × arctan(1). Vul de kettingbreuk in met z = 1 tot en met · · · + benadering van π is dan op 5 decimalen nauwkeurig.

64 17 .

De

Oefening 6.2.3 e op vijf decimalen. Wijzergetallen kiezen tot en met · · · 9 + 12 . Oefening 6.2.4

ez − e1z e2 − 1 kies z = 1, immers uit z = volgt na kruislings vermenigvuldigen: e2 + 1 e + e1z (e2 − 1)(ez + e1z ) = (e2 + 1)(ez − e1z ). Haakjes uitwerken en vereenvoudigen geeft de vergelijking: e2z = e2 . Hieruit volgt eenvoudig z = 1. Vul in de kettingbreuk z = 1 in (de tellers worden dus allemaal 1) en kies de wijzergetallen tot en met · · · 5 + 17 . De benadering is dan op 5 decimalen nauwkeurig. Oefening 6.2.5 tan(1) op 5 decimalen nauwkeurig. Vul z = 1 in de kettingbreuk in en kies wijzergetallen tot en met · · · 7 − 19 .

Aanwijzingen bij de eindopdrachten. De Pell vergelijking is x2 −13y 2 = 1. De kleinste = 649 en y = 180. √ oplossing is x√ n Dan zijn alle (x, y) ∈ Z bepaald door x + y √13 = (649 + 180 √ 13) voor zekere n ∈ Z > 0. Er geldt namelijk dat (649 + 180 13)(649 − 180 13) = 1. Links en rechts tot de n-de macht verheffen levert natuurlijk hetzelfde op. De kleinste oplossing wordt dan gegeven voor n = 1 en geeft een leger van 421200 soldaten.

49 Voor al het programmeer werk op je grafische rekenmachine is de website van Henk Pfaltzgraff een prima start. Kijk op www.henkshoekje.com Op de website die bij dit boekje hoort vind je enkele programma’s die ter download voor de GR worden aangeboden.

50


Index ⌊α⌋, 17 φ, 24 {α}, 17 l(N ), 32 Bayeux, 33 Benaderingseigenschappen, 18 Breuk, 1, 9 Brouncker, 28

Knikkers, 30 Lineaire combinatie, 13 Merkwaardig product, 29 Oneindig, 17

De Thiende, 1 Decimale ontwikkeling, 1–3 Deler, 11 Diophantische vergelijking, 27 Driehoeksgetallen, 30

Palindroom, 20 Particuliere oplossing, 15 Pell, 27 Periode, 2, 4, 6 Periodelengte, 2, 6 Periodiciteit, 20 Periodiek, 2, 4, 20 Periodieke breuken, 2 Pi, 1, 17 Priemgetal, 4–6 Pythagoras, 27

Eindige kettingbreuken, 7 Elementaire functies, 38 Euclides, 24 Euclidisch algoritme, 11, 34

Rationaal getal, 2, 8 Rekenkundige rij, 5 Repeterende breuk, 2 Rest, 4, 12, 17, 20

Fibonacci, 25

Schrikkeljaar, 22 Sectio divina, 24 Simon Stevin, 1 Symmetrieën, 20

Convergent, 8, 19, 23 Convergeren, 19 Cyclus, 22

Gehele deel, 17 GGD, 11, 34 Grafische rekenmachine, 35 Gregoriaanse kalender, 22 Gulden snede, 24

Vergelijking van Pell, 27, 34 Vierkantsgetallen, 30 Vierkantsvergelijking, 25

Hastings, 33 Inverse, 20 Irrationaal getal, 6, 17, 20 Juliaanse kalender, 22

Wijzergetal, 8, 20 Wijzergetallen, 13 Zaremba, 37

Kalender, 22 Kettingbreuk, 7, 12, 17 51

Breuken - Brak - Gebroken. Kettingbreuken

Recommend Documents