Priemgetallen en de rij van Fibonacci, Vier artikelen voor het tijdschrift Pythagoras Bart Zevenhek 20 februari 2008 Samenvatting In deze vier artikelen wordt ingegaan op enkele getaltheoretische eigenschappen van de rij van Fibonacci {Fn }n∈N . Er is een geleidelijke opbouw naar het laatste artikel, waarin, met behulp van het gereedschap dat in de eerdere artikelen aangereikt is, bewezen wordt dat voor een priemgetal p het element Fp−1 of Fp+1 deelbaar is door p. In de aanloop hiernaar toe worden onder andere verschillende formules betreffende het verband tussen de rij van Fibonacci en de guldensnede behandeld, alsmede de kleine stelling van Fermat. Zijdelings wordt tevens aandacht gegeven aan de geschiedenis van het onderwerp en praktische toepassingen. Bij wijze van appendix is een meetkundig bewijs gegeven van de convergentie van het quotient van opvolgende elementen van de rij van Fibonacci naar de gulden snede verhouding, gebaseerd op de in het tweede artikel bewezen ’formule van Kepler’. Voor opname in dat artikel is dit meetkundig bewijs waarschijnlijk iets te lang. Het beoogde niveau is minimaal 4VWO wiskunde-B. Alhoewel er niet meer bekend verondersteld wordt dan het gebruik van binomiaalco¨effici¨enten, die in het artikel overigens wel ingeleid worden, is de kennis van elementaire algebra en vooral het abstractieniveau dusdanig hoog dat een onderbouwleerling moeite zal hebben met alle artikelen, behalve wellicht het eerste artikel. In verband met plaatsing in opeenvolgende edities van het tijdschrift ’Pythagoras’, wordt ieder artikel begonnen met een terugblik op de eerdere artikelen, teneinde het kunnen volgen van de inhoud zoveel mogelijk los te koppelen van kennis van de voorgaande artikelen.
1
Inhoudsopgave 1 Hoe reken je mijlen om naar kilometers?
2
2 De rij van Fibonacci en de gulden snede
5
3 Priemgetallen en getaltheorie
8
4 De rij van Fibonacci en priemgetallen
11
5 Appendix: een meetkundig bewijs
14
2
1
Hoe reken je mijlen om naar kilometers?
”Heb je wel eens gehoord van de rij van Fibonacci?” Ik vroeg het aan een Engelse vriend van me, nadat hij me gevraagd had om iets te vertellen over het wiskundig onderzoek waar ik me mee bezig houd. ”Ehh, is dat niet een manier om mijlen om te rekenen naar kilometers?” ”H`e, wat zeg je me nu? Leg eens uit?” ”Nou, 2 mijl is 3 kilometer, 3 mijl is 5 kilometer, 5 mijl is 8 kilometer, enzovoort.” ”Hoe bedoel je dat? Is 8 mijl dan 13 kilometer, soms?” Het begon me te dagen: 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13, inderdaad, de reeks van Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . wordt gebruikt! ”En hoe doe je het dan als je getal niet in de reeks voorkomt, bijvoorbeeld met 7?” ”Nou”, zei hij, ”dan neem je een getal in de reeks dat daardoor deelbaar is, bijvoorbeeld 21. Dan weet je: 21 mijl is 13 + 21 = 34 kilometer, dus 7 mijl is 34 : 3 = 11 31 kilometer.” Het klonk niet erg praktisch, maar theoretisch was het interessant: hoe weet je zeker dat, als je een getal hebt, er dan altijd een getal in de reeks van Fibonacci is dat deelbaar is door dat getal? Daar waren we precies bij het startpunt van mijn onderzoek aangekomen. In dit tijdschrift stond in het nummer van januari 2005 de volgende opgave: De rij van Fibonacci, waarvan de elementen genoteerd worden met Fi , wordt als volgt geconstrueerd: F0 = 0, F1 = 1, en verder geldt:Fi = Fi−1 + Fi−2 . Bewijs dat er voor elk positief geheel getal n oneindig veel getallen in de rij van Fibonacci zijn die een veelvoud zijn van n.
Vrijwel de vraag die we hierboven tegenkwamen! De vele wonderbaarlijke toepassingen in kunst en natuur van de rij van Fibonacci en de daarmee samenhangende gulden snede verhouding wordt veel over geschreven. Daar zit veel onzin tussen, zoals Albert van der Schoot in zijn proefschrift ‘de ontstelling van Pythagoras’ heeft laten zien. Maar de getaltheoretische eigenschappen van de reeks, zoals je bijvoorbeeld in de opgave tegen komt, zijn echt interessant, en daar hoor je zelden over. In dit eerste artikel van een serie waarin we enkele getaltheoretische eigenschappen van de reeks van Fibonacci gaan onderzoeken die uit de opgave voortkomen, gaan we de opgave samen oplossen. Waarom werkt die truc om mijlen in kilometers om te rekenen eigenlijk? Een Engelse mijl is 1.609344 kilometer. Volgens de truc zou dit getal gelijk moeten 2 zijn aan: 23 = 1.5, 53 = 1.6666.., 85 = 1.6, 18 = 1.625, 13 = 1.61538... Je ziet dat het redelijke benaderingen zijn. Het lijkt zelfs wel steeds beter te worden. Er zijn twee redenen dat de truc enigzins werkt. De eerste reden is puur toeval, een van die ’wonderbaarlijke’ toevalligheden waar de gulden snede steeds weer de pers√mee haalt: 1,609344 is ongeveer gelijk aan de gulden snede verhouding 1 5) = 1.618033989. De andere reden is puur wiskundig: de verhouding 2 (1 + van opvolgende getallen uit de reeks van Fibonacci nadert naar de gulden snede verhouding. In een van de volgende artikelen zullen we dit laten zien. Nu de opgave. Hoe pak je zoiets aan? Een goede methode, die vaak werkt als je geen idee hebt hoe je een opgave moet aanpakken, is: probeer maar eens wat getallen uit. Om te beginnen ga je de opgave dan beter begrijpen. Ten tweede ga je dan misschien een patroon, een regelmaat, een structuur ontdekken. Die kan je testen in meer gevallen en vervolgens ga je die proberen te bewijzen. Laten we deze methode eens proberen.
3
Het kleinste positieve getal dat we kunnen nemen is 1. Dat is flauw: natuurlijk zijn alle getallen in de rij van Fibonacci hierdoor deelbaar! Dan nemen we 2. Het derde Fibonaccigetal F3 is gelijk aan 2. Maar zijn er oneindig veel deelbaar door 2? Verder speuren levert op: F6 = 8, F9 = 34, F12 = 144, enz. Een patroon: ieder derde Fibonaccigetal is deelbaar door 2. Waarom? Kijk beter naar het patroon: 0,1,1,2,3,5,8,13,21,34,55,89,144. Steeds: oneven, oneven, even. Dat is logisch: oneven + oneven = even en oneven + even = oneven. We hebben ingezien dat er oneindig veel Fibonacci getallen deelbaar zijn door 2! Nu eens een moeilijker getal, bijvoorbeeld 13. Met proberen vind je F14 = 377, is deelbaar door 13 (want 377 = 390−13 = 30×13−13). Nog eens, met 11: F10 = 55 is deelbaar door 11. Met 14 vind je pas bij F24 = 46368 een Fibonacci getal dat er deelbaar door is! Als het al zo moeilijk is om er een te vinden, hoe kunnen we dan bewijzen dat er zelfs oneindig veel zijn? We gingen misschien te snel. Stapje terug. Hoe gaat het met 3? We vinden: F4 = 3, F8 = 21, F12 = 144, enz. Ha! Ieder vierde Fibonacci getal is deelbaar door 3. Maar hoe bewijzen we dit. Bij twee hadden we even/oneven, maar bij 3 niet? Wat hebben we wel bij 3? De rest die je krijgt als je een getal door 3 deelt! Zo kan je op het idee komen om, in plaats van de rij van Fibonacci, de rij te bekijken die je krijgt door de resten na deling door een getal op te schrijven. Bij het eerste voorbeeld, met 2, krijg je dan: 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, . . .Als je dit doet met 3 krijg je: 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, . . . Reken maar na! Laten we dit de 3-resten-rij noemen. Je ziet: de 3-resten-rij lijkt weer periodiek, net als bij 2. Iedere keer dat er een 0 te voorschijn komt heb je natuurlijk een Fibonacci getal gevonden dat deelbaar is door 3. Maar waarom zo een rij met resten periodiek is en waarom er nullen in voorkomen is nog steeds de vraag! Het is zeker geen makkelijke opgave, maar we gaan dapper door! Nog maar eens een rijtje resten opschrijven. Met bijvoorbeeld 8 krijg je: 0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, 1, 1, 2, 3, . . . . Kijk eens goed naar deze 8-resten-rij. Wat valt je op? Je ziet dat alleen de getallen 0 tot en met 7 voorkomen, dat is logisch, want het zijn de enige resten die je kan krijgen als je deelt door 8. De rij is weer periodiek, maar waarom? Nog steeds geen idee. Maar kijk eens goed: de 8resten-rij is weer een soort Fibonacci rij, alleen moet je steeds als je boven de 7 uitkomt er 8 aftrekken. Probeer maar en doe dat ook eens bij de rijen met resten van 2 en 3. Dit is een verschijnsel dat in de wiskunde modulorekenen wordt genoemd. Daar leer je dat de rest van de som van twee getallen gelijk is aan de rest van de som van de resten. Dus bij deling door 8 is de rest van 13+21 gelijk aan de rest van 5+5. Een bewijs vindt je in de kantlijn. [kantlijn:][Neem een getal n. Stel a en b zijn positieve gehele getallen. Na deling door n zijn er dan gehele getallen p, q, r, s met: a = np + r en b = nq + s, waarbij r en s de resten zijn, zodat 0 ≤ r < n en 0 ≤ s < n. Dan geldt: a + b = np + r + nq + s = n(p + q) + r + s = n(p + q + 1) + r + s − n. Als je a + b deelt door n, dan is de rest dus gelijk aan r + s wanneer dit kleiner is dan n, en anders is de rest r + s − n. In beide gevallen is de rest van de som gelijk aan de rest van de som van de resten.] 4
Nu hebben we de ingredi¨enten voor een bewijs. Neem weer eens een getal, bijvoorbeeld 11. Er zijn dan 11 mogelijke resten: 0 tot en met 10. Nu zijn er voor twee opeenvolgende resten in de 11-resten-rij, (0,1) (1,1) (1,2) (2,3) (3,5) (5,8) (8,2) (10,1) (1,0) (0,1) etc, maar 11×11 = 121 mogelijkheden. Dit betekent dat, als ik de eerste 122 opeenvolgende tweetallen in de 11-resten-rij bekijk, er twee tweetallen hetzelfde moeten zijn! In dit geval zie je dat het tweetal (0,1) na een tijdje terugkomt . Dan komt het getal dat volgt op dat tweetal ook twee keer voor in de 11-resten-rij, want je kunt altijd een getal in de 11-resten-rij uitrekenen als je de twee voorgaande weet. Maar dan komen ook de daarop volgende getallen overeen, . . . en de hele rij erna. Dan moet de rij die volgt op het eerste tweetal op een gegeven moment gaan samenvallen met de rij vanaf het tweede tweetal. Kortom, de rij is periodiek vanaf het eerste tweetal! We kunnen nog iets meer zeggen. Twee opeenvolgende getallen x, y in de rij van Fibonacci leggen ook het voorgaande getal vast, namelijk y − x, want y − x + x = y. Dit betekent dat ook het stuk v´o´or het eerste gelijke tweetal periodiek doorloopt. We hebben nu een merkwaardig resultaat. Als we het bovenstaande herhalen voor een willekeurig getal n, dan zie je dat de rij met resten periodiek is. Dus als er ergens een 0 zit (wat betekent dat het bijbehorende Fibonacci getal deelbaar is door n), dan komt dat oneindig vaak voor! Maar F0 is gelijk aan 0! Doordat de n-resten-rij periodiek is komt die 0 steeds weer terug en vind je oneindig veel Fibonaccigetallen die deelbaar zijn door n. De opgave is bewezen! De truc om mijlen naar kilometers om te rekenen werkt dus altijd. Maar of die methode erg praktisch is, hangt samen met de vraag hoe lang je moet zoeken voor je een geschikt Fibonacci getal kunt vinden. Zodoende kom je op andere vragen zoals: hoe vindt je, bij een gegeven getal n, de periode en wanneer komt het eerste getal dat deelbaar is door n, dus het eerste nulpunt bij de Fibonacci n-resten? In de tabel hieronder vind je daar wat waarden van. n Periode Nulpunt
2 3 3
3 8 4
4 6 6
5 20 5
6 24 12
7 16 8
8 12 6
9 24 12
10 60 15
11 10 10
12 24 12
13 28 7
14 48 24
15 40 20
Als je deze tabel goed bekijkt kan je er veel interessante verbanden in vinden. Probeer maar eens. Een van die verbanden heeft te maken met de vraag of het getal n een priemgetal is. Kan je dat verband zelf vinden? In de volgende artikelen zullen we daar verder mee gaan.
5
2
De rij van Fibonacci en de gulden snede
Je hebt vast wel eens gehoord van de rij van Fibonacci. Hier zie je het begin: F0 0
F1 1
F2 1
F3 2
F4 3
F5 5
F6 8
F7 13
F8 21
F9 34
F10 55
F11 89
F12 144
F13 233
F14 377
In een vorig artikel hebben we gezien dat er voor ieder getal n oneindig veel getallen in de rij van Fibonacci deelbaar zijn door n. Probeer voor de getallen 2 t/m 13 een getal in de rij te vinden dat er door deelbaar is. Kijk eens of je iets opvalt. Weet je wat een priemgetal is? Een geheel getal dat groter is dan 1 en alleen door zichzelf en door 1 deelbaar is. Omcirkel de priemgetallen van 2 tot en met 13. Zie je al iets? Juist: als n een priemgetal is dan is n een deler van Fn−1 of Fn+1 , behalve 5, dat is een deler van F5 . En als n niet een priemgetal is dan is n niet een deler van Fn−1 of Fn+1 . Is dat niet wonderlijk! Wat hebben priemgetallen nu met de rij van Fibonacci te maken? Waarom is 5 een uitzondering? Nu is het wel erg voorbarig om uit 12 testjes een conclusie te trekken. Maar ga je tot n = 300 dan blijkt het steeds geldig te zijn. De enige uitzondering blijft 5. Dat is toch wel frappant! Maar kunnen we nu concluderen dat het altijd waar zal zijn? Natuurlijk niet, en als je een stukje verder gaat, tot 323 om precies te zijn, dan zal je ontdekken dat 323 = 17 × 19 en dus niet een priemgetal is, maar F324 = 23041483585524168262220906489642018075101617466780496790573690289968 is wel deelbaar door 323. Maar het leuke is dat we de eerste uitspraak wel kunnen bewijzen! Als n een priemgetal ongelijk aan 5 is, dan is n een deler van Fn−1 of van Fn+1 . Makkelijk is het bewijs niet. Er zijn drie artikelen voor nodig. Maar we zullen onderweg al vele vruchten plukken. Om te beginnen gaan we twee mooie formules afleiden die te maken hebben met de reeks van Fibonacci. Uit beide formules valt een verband tussen de rij van Fibonacci en de gulden snede af te leiden dat we in het vorige artikel ook al tegen kwamen. Voor drie opeenvolgende getallen in de reeks van Fibonacci, zeg Fn−1 , Fn , Fn+1 , geldt per definitie: Fn−1 + Fn = Fn+1 . Er is echter een ander verband tussen drie opeenvolgende termen: Fn+1 Fn−1 − Fn2 = (−1)n .
(1)
Deze formule gaan we bewijzen. Stel: Fn+1 Fn−1 − Fn2 = Hn . Dan moeten we bewijzen dat Hn = (−1)n . We gaan naar vier opeenvolgende termen, Fn−1 tot en met Fn+2 kijken. Stel a = Fn−1 en b = Fn . Dan is Fn+1 = a + b en Fn+2 = b + a + b = a + 2b. Er geldt dan: Hn+1
2 = Fn+2 Fn − Fn+1 = (a + 2b) · b − (a + b)2 = ab + 2b2 − a2 − 2ab − b2 = b2 − a2 − ab = b2 − a(a + b) = Fn2 − Fn+1 Fn−1 = −Hn .
Maar H2 = F3 F1 − F22 = 2 · 1 − 1 = 1, en met het voorgaande volgt hieruit: H3 = −1, H4 = 1, . . . en Hn = (−1)n . Deze formule werd rond 1600 door niemand minder dan Johannes Kepler gevonden, alhoewel hij het niet als formule presenteerde maar als meetkundige 6
F15 610
figuren. Met behulp hiervan was hij een van de eerste personen die een verband tussen de rij van Fibonacci en de gulden snede vond en kon inzien. Als je niet (meer) weet wat de gulden snede is, lees dan even het verhaal in de kantlijn. Bekijk nu de rij die je krijgt door opeenvolgende termen van de rij van Fibonacci op elkaar te delen. Die begint zo: 1, 2, 1.5, 1.66 . . . , 1.6, 1.625, . . .. Deze rij komt steeds dichter bij de gulden snede verhouding! Dit valt als volgt in te zien. [kantlijn][getekend: lijnstuk met punten A,C,B en bij AC de lengte 1 en bij CB de lengte x][We zeggen dat C het lijnstuk AB verdeelt in de gulden snede AB verhouding als BC AC = BC , dus als het langste stuk in gelijke verhouding staat tot het kortste als het geheel tot het langste. Stel het kortste stuk is 1 en het x 2 langste x, dan moet dus gelden: x+1 x = 1 . Daaruit volgt x + 1 = x , oftewel √ x2 − x − 1 = 0. Met bijvoorbeeld de abc-formule vind je dan: x = 1+2 5 = 1, 618 . . . (de andere oplossing is negatief).] Als je in onze formule (1) nu alles deelt door Fn Fn−1 dan krijg je: Fn+1 Fn (−1)n − = . Fn Fn−1 Fn Fn−1 Nu wordt Fn snel groter wanneer n toeneemt, dus de rechterkant van het gelijkteken gaat heel snel naar 0 toe als n groter wordt. Dit betekent dat FFn+1 n n n en FFn−1 steeds dichter bij elkaar komen. Noem nu het getal waar FFn−1 naar toe gaat x. Onbekenden worden in de wiskunde nu eenmaal vaak x genoemd. n−1 = Fn +F = 1 + FFn−1 , waaruit Gebruik dat Fn+1 = Fn + Fn−1 en dus FFn+1 Fn n n volgt: Fn−1 Fn (−1)n 1+ − = . Fn Fn−1 Fn Fn−1 Voor x geldt dan 1+ x1 −x = 0, oftewel x+1−x2 = 0 of x2 −x−1 = 0. Precies de vergelijking die bij de gulden snede hoort! De positieve oplossing hiervan is dus het getal dat we zochten en je ziet: de verhouding tussen opeenvolgende getallen in de rij van Fibonacci komt steeds dichterbij de gulden snede verhouding. Nu gaan we naar een andere beroemde formule voor de rij van Fibonacci: de formule van Binet. Daarvoor gebruiken we ook de guldensnede verhouding. Laten we de oplossingen van de vergelijking x2 − x − 1 = 0 nu s en t noemen. Dus √ √ 1+ 5 1− 5 s= ,t = 2 2 Ga zelf na dat s > 1, −1 < t < 0 en s2 = s + 1. De rij 1, s, s2 , s3 , s4 , . . . is een rij waarvoor, net als bij de rij van Fibonacci, de som van twee opeenvolgende getallen het volgende getal is, want er geldt: sn + sn+1 = sn (1 + s) = sn · s2 = sn+2 . Ga zelf na dat wanneer a en b willekeurige getallen zijn, de rij Gn = asn + btn diezelfde eigenschap bezit. Nu is de truc dat we de a en b zo gaan kiezen dat de startwaarden gelijk zijn aan de rij van Fibonacci, dus dat G0 = 0 en G1 = 1. Invullen geeft dan: as0 +bt0 = 0 en as1 +bt1 = 1. Uit de eerste vergelijking volgt: a = −b. Wanneer je dit invult in de tweede vergelijking krijg je as − at = 1, n −1 1 n −1 n −tn 1 . Dan is dus b = s−t en Gn = s−t s + s−t t = s s−t . Maar oftewel a = s−t
7
omdat Gn hetzelfde begint en op dezelfde manier verder gaat als Fn moeten deze twee rijen hetzelfde zijn! We krijgen dan de formule van Binet: Fn =
sn − t n s−t
(2)
Dit is een merkwaardige, doch zeer handige formule. Merkwaardig, omdat √ √ 1− 5 1+ 5 s = 2 en t = 2 niet gehele getallen zijn, maar de uitkomst van de formule wel altijd een geheel getal oplevert. Met de formule kan je bijvoorbeeld in ´e´en keer het 100-ste Fibonaccigetal berekenen, zonder dat je alle voorafgaande getallen hoeft te bepalen. De formule van Binet is een zogenaamde directe formule voor de rij van Fibonacci. Wat ook mooi is aan de formule is de eenvoud en de symmetrie: als je s en t verwisselt blijft de formule geldig. Met behulp van de formule van Binet kan je op een tweede manier inzien dat de verhouding van opeenvolgende getallen van de rij van Fibonacci steeds dichter bij de gulden snede verhouding (waarvoor we nu de letter s gebruiken) komt. Met de formule van Binet kan je Fn zien als de som van twee zogenaamde meetkundige rijen: 1 n −1 n Fn = s + t s−t s−t Bedenk nu dat s, de guldensnede verhouding, groter is dan 1 en dat het eerste deel dus snel groter wordt als n vermeerdert. Om precies te zijn: als n met ´e´en toe neemt, dan wordt het eerste deel s keer zo groot. Het tweede deel van de formule bevat t, een getal dat tussen -1 en 0 in zit. Dit gedeelte gaat snel naar 0 toe als n groot wordt en is voor even n positief en voor oneven n negatief. Je ziet dat als n groot is, de verhouding tussen twee opeenvolgende getallen in de rij van Fibonacci steeds dichter bij s, de gulden snede verhouding, komt. Het deel van de formule met t erin zorgt ervoor dat in het ene geval die verhouding net iets meer is dan de gulden snede en in het andere geval iets minder. Nadat we in dit artikel deze twee mooie formules bewezen hebben en uit beide formules langs verschillende wegen hetzelfde resultaat hebben verkregen, gaan we in het volgende artikel enkele belangrijke eigenschappen van priemgetallen afleiden. In combinatie met de twee formules die we hier hebben gevonden, gaan we dan in het laatste artikel een bewijs leveren van de eigenschap: Als n een priemgetal ongelijk aan 5 is, dan is n deelbaar op Fn−1 of Fn+1 . We gaan dan eerst de formule van Binet inzetten om Fn uit te werken, tot er geen wortels meer in voorkomen. Helemaal op het eind van het bewijs gebruiken we dan de formule van Kepler. Maar eerst hebben we nog wat meer gereedschappen nodig en moet we meer afweten van priemgetallen.
8
3
Priemgetallen en getaltheorie
Weet je wat een priemgetal is? Een getal dat precies twee delers heeft. Het getal 1 is geen priemgetal, want die heeft slechts ´e´en deler, en 4 heeft drie delers en is dus ook geen priemgetal. Maar 2, 3, 5, 7, . . . zijn wel priemgetallen. In twee eerdere artikelen hebben we het gehad over de rij van Fibonacci en een merkwaardige eigenschap die te maken heeft met de rij en met priemgetallen. Dit artikel gaan we priemgetallen onder de loep nemen en krijgen we het nodige gereedschap in handen om in het volgende artikel het bewijs van die merkwaardige eigenschap te geven. Ieder getal kan je op precies ´e´en manier ontbinden in priemfactoren. Dat is helemaal niet eenvoudig om te bewijzen, net als de volgende stelling: Stelling 1 Als het product van twee getallen deelbaar is door een priemgetal, dan is een van de factoren van het product dat ook. Dat deze stelling alleen voor priemgetallen geldt zie je in de volgende voorbeelden. Het product 6 × 4 is deelbaar door 3 en inderdaad: 6 is deelbaar door 3. Ditzelfde product 6 × 4 is deelbaar door 12, maar 6 noch 4 is deelbaar door 12. We zullen deze stelling niet bewijzen, intu¨ıtief is hij hopelijk duidelijk genoeg. Priemgetallen zijn als het ware de onsplitsbare bouwstenen van getallen, zoals atomen dat zijn in de scheikunde. We gaan het nu hebben over het zogenaamde binomium van Newton. Aangezien dit tot de middelbareschoolstof behoort (4-de klas VWO), zullen we hierbij eveneens geen bewijzen leveren. Je weet dat (a + b)2 = a2 + 2ab + b2 . Met behulp hiervan kan je een formule vinden voor (a + b)3 : (a + b)3
= (a + b)(a + b)2 = (a + b)(a2 + 2ab + b2 ) = a3 + 2a2 b + ab2 + a2 b + 2ab2 + b3 = 1 · a3 + 3 · a2 b + 3 · ab2 + 1 · b3
De getallen 1,3,3,1 worden de binomiaalcoefficienten genoemd. Ze zijn zo belangrijk dat er de volgende notatie voor is: µ ¶ µ ¶ µ ¶ µ ¶ 3 3 3 3 = 1, = 3, = 3, =1 0 1 2 3 Deze binomiaalcoefficienten kan je voor k > 0 als volgt berekenen: µ ¶ n n(n − 1)(n − 2) · · · (n − k + 1) = k k(k − 1)(k − 2) · · · 1 Reken hiermee zelf na dat bijvoorbeeld geldt: (a + b)6 = a6 + 6a5 b + 15a4 b2 + 20a3 b3 + 15a2 b4 + 6ab5 + b6 De binomiaalcoeficient 15 kan je bijvoorbeeld berekenen door: µ ¶ 6 6·5 = = 15 2 2·1
9
Nu gaan we de volgende stelling, die uitsluitend voor priemgetallen geldt, bewijzen: 2 Voor een priemgetal p en voor een getal k met 0 < k < p geldt dat ¡Stelling ¢ p deelbaar is door p. k Het bewijs hiervan gaat als volgt. Voor k > 0 geldt: µ ¶ p(p − 1)(p − 2) · · · (p − k + 1) p = k k(k − 1)(k − 2) · · · 1 Hieruit volgt: µ ¶ p · k(k − 1)(k − 2) · · · 1 = p(p − 1)(p − 2) · · · (p − k + 1) k Nu is de rechterkant deelbaar door p, de linkerkant moet dat dus ook zijn. Maar omdat k < p, is k(k−1)(k−2) ¡ ¢ · · · 1 niet deelbaar door p. Omdat p een priemgetal is volgt uit stelling 1 dat kp dan deelbaar moet zijn door p. Klaar! Voordat we verder gaan, is het handig om de modulo-notatie in te voeren. Wanneer je twee getallen a en b deelt door hetzelfde getal n, kan het gebeuren dat de resten gelijk zijn. Dit wordt genoteerd door a ≡ b (mod n). Bijvoorbeeld: 17 ≡ 65 (mod 12). Als a ≡ 0 (mod n) wil dat zeggen dat a deelbaar is door n, de rest is dan immers 0. In een eerder artikel zagen we dat de rest van de som van twee getallen, na deling door een getal, gelijk is aan de rest van de som van de resten. In modulo-notatie wordt dit: wanneer a ≡ c en b ≡ d, dan is a + b ≡ c + d (mod n). Hetzelfde geldt ook voor vermenigvuldigen: als a ≡ c en b ≡ d, dan is a·b ≡ c·d (mod n). Probeer dat laatste eens zonder modulonotatie uit te spreken en vervolgens te bewijzen. Niet makkelijk, maar als je van dat vorige artikel het bewijs in de kantlijn imiteert moet het lukken! Ga ook na dat je stelling 1 en stelling 2 met de modulonotatie als volgt kunt opschrijven: Stelling 3 Voor een priemgetal p geldt: 1. Als a en b gehele getallen zijn met a · b ≡ 0 (mod p) dan a ≡ 0 (mod p) of b ≡ 0 (mod p) ¡ ¢ 2. Als k een geheel getal is met 0 < k < p dan kp ≡ 0 (mod p) Het eerste deel van de stelling herken je vast uit de ’gewone’ algebra. Bij modulorekenen geldt dit echter alleen voor priemgetallen! Uit het tweede deel van deze stelling volgt: µ ¶ µ ¶ µ ¶ p p−1 p p−2 2 p (a + b)p ≡ ap + a b+ a b + ... + abp−1 + bp (mod p) 1 2 p−1 ≡ ap + bp (mod p) Alle binomiaalcoeeficienten vallen immers weg omdat ze deelbaar zijn door p. We hebben dus alweer een stelling: Stelling 4 Voor een priemgetal p geldt (a + b)p ≡ ap + bp (mod p) Deze stelling is zeker niet waar in de ’gewone’ algebra en bij modulorekenen uitsluitend voor priemgetallen! 10
Tenslotte gaan we een heel belangrijke stelling uit de getaltheorie bewijzen. Stelling 5 (Kleine stelling van Fermat) Voor een priemgetal p en voor een willekeurig getal n geldt: np ≡ n (mod p) Deze stelling zegt bijvoorbeeld dat als je 1011 deelt door 11, de rest gelijk is aan 10, net als wanneer je 1013 deelt door 13. Reken maar na om te zien of het klopt. Het bewijs gebruikt een heel erg slimme truc, die in de wiskunde volledige inductie heet. De truc is, om eerst eens aan te nemen dat de stelling waar is voor een of ander getal n en dan te laten zien dat het vervolgens ook waar is voor het volgende getal n + 1. Aangezien de stelling duidelijk waar is voor n = 1, moet die vervolgens ook waar zijn voor n = 2, dan voor n = 3,. . . en zo voor ieder getal! Goed, neem dus aan dat voor een getal n geldt: np ≡ n (mod p). Om te laten zien dat de stelling nu ook geldt voor n + 1 gebruiken we stelling 5: (n + 1)p ≡ np + 1p ≡ n + 1 (mod p) Maar dit zegt precies dat de stelling ook geldt voor n + 1. Klaar! De kleine stelling van Fermat wordt onder andere gebruikt als pseudo-priemtest. Met zo een test kan je bij een gegeven getal soms met 100% zekerheid vertellen dat het niet een priemgetal is en anders dat het waarschijnlijk wel een priemgetal is. Dat gaat zo. Stel we willen weten of 10 een priemgetal is en we hebben geen zin om op zoek te gaan naar een deler. Dan gaan we kijken of de stelling van Fermat geldt voor 10. We nemen bijvoorbeeld n = 2 en berekenen 210 = 1024 ≡ 4 (mod 10). Als nu 10 een priemgetal was, zou hier niet 4 uit moeten komen maar 2. De conclusie is dat 10 onmogelijk een priemgetal kan zijn! Dat dit niet altijd goed gaat zie je als je n = 5 neemt om te testen of 10 een priemgetal is. Je krijgt dan 510 = 9765625 ≡ 5 (mod 10), dus de kleine stelling van Fermat gaat nu goed! Maar natuurlijk mogen we hier niet uit concluderen dat 10 een priemgetal is. De stelling zegt immers niets over wat er geldt voor getallen die niet een priemgetal zijn! Het is dus ook zo dat als je met een priemgetal begint en de kleine stelling van Fermat blijkt te kloppen, je niet daaruit mag concluderen dat het getal een priemgetal is. Deze pseudopriemtest lijkt trouwens erg onpraktisch, maar door allerlei handige trucjes blijkt deze methode voor grote getallen veel sneller te werken dan het zoeken naar delers. De eigenschap die we in het volgende artikel gaan bewijzen: Als p een priemgetal ongelijk aan 5 is, dan is p een deler van Fp−1 of van Fp+1 (waarbij Fn de rij van Fibonacci is), geeft je ook een pseudopriemtest in handen. Als n namelijk niet deelbaar is op Fn−1 of Fn+1 , kan n onmogelijk een priemgetal zijn. Helaas is ook hier het omgekeerde niet waar, zoals we zagen met het getal 323. Het schijnt echter dat als je beide pseudopriemtesten combineert je een behoorlijke priemtest krijgt. Er is bijvoorbeeld nog nooit een tegenvoorbeeld gevonden van een samengesteld getal n met: a) n ≡ ±2 (mod 5), b) Fn+1 ≡ 0 (mod n) en c) 2n ≡ 2 (mod n). Dit soort getallen blijken dus altijd priemgetallen te zijn. Er is een prijs uitgeloofd voor degene die een tegenvoorbeeld vindt!
11
4
De rij van Fibonacci en priemgetallen
Ken je de rij van Fibonacci? F0 = 0 en F1 = 1, en verder geldt: Fn = Fn−1 + Fn−2 . En weet je wat priemgetallen zijn? Een positief geheel getal met precies twee delers. De volgende getallen zijn voorbeelden van priemgetallen: 2,3,5,7,11,13,. . . en de volgende zijn dat niet: 1,4,6,8,9,10,. . . . Nu weet je genoeg om te begrijpen wat met de volgende merkwaardige eigenschap bedoeld wordt: Als p een priemgetal ongelijk aan 5 is, dan is p een deler van Fp−1 of van Fp+1 . Controleer deze eigenschap maar eens bij de volgende tabel: F1 1
F2 1
F3 2
F4 3
F5 5
F6 8
F7 13
F8 21
F9 34
F10 55
F11 89
F12 144
F13 233
F14 377
In dit artikel gaan we deze eigenschap bewijzen. Dat bewijs is niet eenvoudig, maar we hebben in de voorgaande artikelen een hoop gereedschap in handen gekregen. Met hulp hiervan gaan we een mooi bewijs in elkaar knutselen. Laten we nog eens kijken welke gereedschappen we ook al weer allemaal hebben. Eerst hebben we de rij van Fibonacci onder de loep genomen en daar twee formules voor afgeleid. De eerste formule, die we de formule van Kepler noemden is: Fn+1 Fn−1 − Fn2 = (−1)n . De tweede formule is de formule van Binet. Hierin stellen s en t de oplossingen voor van x2 − x − 1 = 0. √ √ sn − t n 1+ 5 1− 5 Fn = met s = ,t = s−t 2 2 We hebben kennis gemaakt met de modulo-notatie. Als je twee getallen, a en b, allebei deelt door een getal n, dan schrijf je a ≡ b (mod n) wanneer de resten gelijk zijn. Als a deelbaar is door n kan je dus schrijven: a ≡ 0 (mod n), de rest is dan immers gelijk aan 0. Een paar eenvoudige regels voor het modulorekenen zijn: als a ≡ c (mod n) en b ≡ d (mod n), dan a + b ≡ c + d (mod n), en iets soortgelijks geldt voor vermenigvuldigen. Voor een priemgetal p geldt: als ab ≡ 0 (mod p), dan is a ≡ 0 (mod p) of b ≡ 0 (mod p). We bewezen de kleine stelling van Fermat: Voor een priemgetal p en voor een willekeurig getal n geldt: np ≡ n (mod p). Tussendoor werd het binomium van Newton behandeld: µ ¶ µ ¶ µ ¶ n n−1 n n−2 2 n n n (a + b) ≡ a + a b+ a b + ... + abn−1 + bn . 1 2 n−1 ¡n¢ Van de zogenaamde ¡p¢binomiaalcoefficienten k hoef je alleen te weten dat als 0 < k < p, dan is k deelbaar door p als p een priemgetal is. Ook dat hebben we bewezen.
12
Zo, nu kunnen we aan de slag met het echte bewijs. We gaan eerst peuteren aan de formule van Binet, om aan een uitdrukking te komen voor Fp waarin geen wortels meer voorkomen. In de formule komen vormen voor zoals: √ √ 1+ 5 p (1 + 5)p ( ) = . 2 2p De teller gaan we nu uitwerken met het binomium van Newton. Je krijgt dan: µ ¶ µ ¶√ µ ¶√ µ ¶√ √ √ p p √ p p p p 2 3 5+ 5 + 5 + ... + 5p−1 + 5p (1 + 5) = 1 + 1 2 3 p−1 Nu gaan we aannemen dat p een oneven priemgetal is, dus dat p niet gelijk is aan 2. Voor p = 2 weten we al dat 2 een deler √ is van F3 , dus voor p = 2 hoeven we de stelling niet te bewijzen! Voor (1 − 5)p krijgen we nu: µ ¶ µ ¶√ µ ¶√ µ ¶√ √ p √ p √ p p p p 2 3 (1 − 5) = 1 − 5+ 5 − 5 + ... + 5p−1 − 5p 1 2 3 p−1 Dat bijvoorbeeld de laatste term negatief is, komt doordat p oneven is. Nu gaan we dan echt de formule van Binet uitwerken voor Fp , waarbij we gebruik maken van dat wat we net vonden. Daarbij gaat het een en ander √ wegvallen. De noemer van de formule van Binet is trouwens gelijk aan 5. Reken maar na! Nou, daar gaat hij. √ ¡ ¢√ ¡ ¢√ ¡ ¢√ 2 · p1 5 + 2 · p3 53 + 2 · p5 55 + . . . + 2 · 5p sp − tp √ Fp = √ = 5 2p 5 Omdat p oneven √ n zijn met √ p = 2n + 1. In bovenstaande √ is, moet er een getal andere wortels formule wordt 5p dan gelijk aan 52n+1 = 5n 5. Ook in alle √ komen alleen oneven √ exponenten voor, zodat we hier een factor 5 uit √ √ kunnen halen. Bijvoorbeeld: 55 = 52 5. Bij√de hele teller kunnen we dan 5 buiten haakjes halen en wegdelen tegen de 5 in de noemer. Als we met dit alles rekening houden, blijft er het volgende over: ¡ ¢ ¡ ¢ ¡ ¢ 2 · p1 + 2 · p3 · 5 + 2 · p5 · 52 + . . . + 2 · 5n Fp = F2n+1 = 2p Het is gelukt om de wortels kwijt te raken! Het blijft enigzins verbazend dat hier altijd een geheel getal uitkomt (dat komt er omdat Fp nu eenmaal een geheel getal is), maar die rare wortels zijn tenminste verdwenen. Nu gaan we over tot de tweede grote stap in ons bewijs. We gaan modulorekenen. Dat mag, want we hebben ¡ ¢ nu te maken met gehele getallen! We zagen dat alle binomiaalcoefficienten kp door p deelbaar zijn als p een priemgetal is en 0 < k < p. Dus als we modulo p gaan rekenen worden die allemaal 0. Dat ruimt lekker op! Verder gebruiken we nog eventjes de kleine stelling van Fermat om 2 op te schrijven in plaats van 2p . Die 2 kunnen we dan meteen wegdelen tegen de 2 die boven voorkomt. Tenslotte krijgen we dan: Fp ≡ 5n
(mod p)
Nu gaan we kwadrateren. Je ziet straks wel waarom. Tevens gebruiken we dat p = 2n + 1, zodat 2n = p − 1. Dan gaan we naar de kleine stelling van Fermat toewerken en . . . Kijk maar goed! Fp2 ≡ 52n ≡ 5p−1 ≡
5 5p ≡ ≡ 1 (mod p) 5 5 13
Deze laatste afleiding is trouwens hardstikke fout voor p = 5. Als p namelijk gelijk is aan 5, dan is 5 ≡ 0 (mod 5) en wordt F5 ≡ 5n ≡ 0 (mod 5). De rest klopt dan niet: delen door 0 mag nu eenmaal niet. Het bewijs gaat dus mank voor p = 5. Maar dat moest ook wel: 5 is nu net de enige uitzondering op de regel! Mooi dat we die uitzondering tegenkomen, anders zou er toch iets goed fout zijn aan ons bewijs. Wel lieten we zien dat 5 een deler is van F5 . Dat klopt goed, want F5 = 5. Eindelijk kunnen we overgaan tot de finale. We zetten onze laatste troef in: de formule van Kepler. Aangezien p een oneven priemgetal is, weten we dat (−1)p gelijk is aan −1. De formule van Kepler wordt dus: Fp+1 Fp−1 − Fp2 = −1 Nu gaan we dit invullen in onze modulo-vergelijking en we krijgen: Fp+1 Fp−1 + 1 ≡ 1 (mod p) Oftewel: Fp+1 Fp−1 ≡ 0 (mod p) Nu gebruiken we de eerder vermelde regel van modulorekenen die alleen geldt voor priemgetallen en we zijn waar we wezen willen: Fp+1 ≡ 0 (mod p) of Fp−1 ≡ 0 (mod p), dus p is een deler van Fp+1 of Fp−1 . Nu het bewijs geleverd is, blijven er nog wel wat vragen over. Is te voorspellen of p een deler is van Fp−1 , of van Fp+1 ? Valt er iets te zeggen over getallen die niet een priemgetal zijn? De eerste vraag is makkelijk te beantwoorden: als het priemgetal eindigt op een 2,3 of 7 is het een deler van Fp−1 , als het eindigt op 1 of 9 is het een deler van Fp+1 . Het bewijs hiervan is moeilijk en gebruikt veel geavanceerder gereedschappen dan we nu gebruikt hebben. De tweede vraag is wel iets over te zeggen: het is mogelijk bij ieder getal n een getal in de reeks van Fibonacci te voorspellen dat er door deelbaar is. Maar Fn+1 of Fn−1 is dat over het algemeen niet. Soms wel, zoals we zagen bij 323 = 17 × 19, dat een deler is van F324 . Zulke getallen worden Fibonacci- pseudopriemgetallen genoemd. Daar zijn er niet veel van, onder de 250.000 zijn er precies 100, maar er is wel bewezen dat er oneindig veel van zijn. Het resultaat dat we in dit artikel bewezen is niet nieuw. In 1846 werd door H.Siebeck bewezen dat een meer algemeen type rij dan de rij van Fibonacci deze eigenschap bezit. Getaltheoretici zijn voortdurend op zoek naar priemtesten: testen die uitwijzen of een gegeven getal al dan niet een priemgetal is. Dat wat we in dit artikel bewezen hebben is geen goede priemtest van te maken: veel te langzaam en het levert geen 100% garantie op dat een getal een priemgetal is. Maar in het spoor van dit soort onderzoek is er wel een priemtest gevonden voor zogenaamde Mersenne-priemgetallen, die gebaseerd is op eigenschappen van de gulden snede. Daarmee worden hele grote priemgetallen gevonden. Die spelen een belangrijke rol bij coderingstechnieken welke bij bijvoorbeeld mobiele telefonie gebruikt worden. Zo zie je maar: al dit werk doen wiskundigen niet voor niets!
14
5
Appendix: een meetkundig bewijs
G
E
F
G
x+1
x+1
F
E
65
13
S H
D x
x2
x
A
1
B
x
H S
x
8
C
A
5
B
D
8
64
8
8
C
Figuur 1: De gulden snede verhouding en de rij van Fibonacci We kijken eerst naar het linker figuur. Het punt B verdeelt het lijnstuk AC volgens de gulden snede als de verhouding van het langste stuk tot het kortste (BC : AB) gelijk is aan het hele lijnstuk staat tot het langste (AC : BC). Uitgaande van dit lijnstuk is vierkant BCDS, rechthoek ACDH en vierkant HDEG getekend. Je ziet dan dat BS : AB = DE : SD, vanwege de guldensnede eigenschap, zodat 4 ABS gelijkvormig is met 4 SDE. Hieruit volgt dat het punt S op de diagonaal AE ligt. We nemen AB als eenheid en BC stellen we gelijk aan x. Omdat er allerlei gelijke driehoeken in dit figuur zitten, kan je zien dat de oppervlakte van rechthoek BCDS gelijk is aan √ die van HSFG. Conclusie: x2 = x+1. Met de abc-formule vinden we dan x = 1+2 5 als positieve oplossing. Nu gaan we naar het rechter figuur, dat op dezelfde wijze is opgebouwd als het linker figuur, maar nu is uitgegaan van opvolgende getallen uit de rij van Fibonacci . De formule van Kepler zegt dan dat de oppervlakte van rechthoek BCDS bijna gelijk is aan die van HSFG. Het scheelt namelijk maar een eenheid, wat naarmate je verder gaat in de rij van Fibonacci steeds minder wordt ten opzichte van de oppervlakte van de rechthoeken. Het gevolg is dat het punt S nu niet op de diagonaal ligt, maar wel vlak erbij en steeds dichterbij naarmate je verder komt in de rij. Als je nu kijkt naar 4 ABS en 4 SDE, zie je dat de verhouding van BS tot AB steeds dichterbij die van ED tot SD komt. Als je nu beide figuren vergelijkt zie je dat die verhouding naar de gulden snede verhouding zal gaan. Zal dit de manier zijn geweest waarop Kepler het verband tussen de rij van Fibonacci en de gulden snede inzag? Het is mogelijk, omdat hij de formule van Kepler al een meetkundige interpretatie gaf en omdat de boven beschreven wijze van oppervlakten van rechthoeken vergelijken vanuit de Griekse oudheid 15
erg bekend was, zodat hij er waarschijnlijk van op de hoogte was. Anderszijds zijn er geen documenten bekend waaruit blijkt dat Kepler deze weg bewandeld heeft. Het is goed mogelijk dat het verband tussen de rij van Fibonacci en de gulden snede hem gewoon opgevallen was als een toevallige wetmatigheid in de rij, net zoals de eigenschap die we in dit artikel de formule van Kepler genoemd hebben, terwijl hij niet het verband tussen deze twee wetmatigheden doorzag.
16
