Zie bijlage voor het complete profielwerkstuk.
Introductie tot de p-adische getallen
Profielwerkstuk Junior College Utrecht
Lars van den Berg, Joep van den Hoven, Linda van der Spaa
Onder begeleiding van dr. R.W. Bruggeman
26 februari 2011
1 Laatst gewijzigd: 20 november 2011
Voorwoord
We zijn zo gewend om met de re¨ele getallen te rekenen dat we er meestal niet bij stilstaan wat een getal eigenlijk is. Het begrip ‘getal’ heeft in de loop van de geschiedenis echter een grote ontwikkeling doorgemaakt. De oude Grieken bijvoorbeeld geloofden alleen in
de rationale getallen (de ‘breuken’ a/b met a, b geheel), irrationale getallen als √2 en π
bezorgden hen veel hoofdpijn en ruzies. Pas een paar honderd jaar geleden werden de negatieve getallen algemeen geaccepteerd in de westerse wiskunde. De ontdekking van de complexe getallen is erg moeizaam verlopen, en heeft uiteindelijk heel de wiskundige gedachtenwereld op z’n kop gezet. Hoe kon zoiets bestaan als een imaginair getal? Het duurde tot Gauss (rond 1830) voor de complexe getallen echt op een wiskundig bonafide manier werden bestudeerd. Wiskundigen begonnen steeds meer te beseffen dat de filosofische vraag ‘bestaat het getal wel’ niet zo veel zin heeft, een antwoord op de vragen ‘hoe gedraagt het zich’ en ‘wat voor verbanden heeft het met andere wiskunde’ geven veel meer inzicht. Dit is zeker het geval bij de p-adische getallen, die rond 1897 zijn ontdekt door Kurt Hensel. Voor beginners is het moeilijk je iets concreets bij deze getallen voor te stellen, en zeker je ervan te overtuigen dat ze bestaan: ze lijken ergens is de mist van het bovennatuurlijke te zweven, voor eeuwig onbereikbaar. Ze mogen dan wel zo ontastbaar zijn als de sterren, we kunnen ze in elk geval proberen te begrijpen, en de studie naar deze getallen is de afgelopen eeuw zeer vruchtbaar gebleken.
De p-adische getallen zijn in zekere zin precies het omgekeerde van de re¨ele getal- len. Bijvoorbeeld 65.7204851 . . . ‘is’ een re¨eel getal (hoewel de vraag open blijft hoe hij verder doorloopt); links van de komma mogen maar eindig veel cijfers staan, rechts heeft hij de vrijheid zich tot in het oneindige uit te strekken. We kunnen zo’n getal zien als limiet van een rij rationale getallen die hem steeds beter benadert maar nooit precies bereikt, bijvoorbeeld 60, 65, 65.7, 65.72, . . . Een voorbeeld van een p-adisch getal is . . . 1584027.56: we hebben het getal van daarnet omgeklapt. We kunnen het zien als limiet van de rij 0.06, 0.56, 7.56, 27.56, . . . Maar bestaat deze limiet wel, en is dit getal niet oneindig groot? Dat hangt er vanaf hoe je het bekijkt. In de p-adische wereld worden de cijfers juist minder belangrijk naarmate ze verder naar links liggen. Als we de rij 0.06, 0.56, 7.56, 27.56, . . . met een gewoon meetlint meten wordt het lint al snel te klein, maar als we ons p-adisch meetlint uit de kast halen komen de getallen wel degelijk steeds dichter bij elkaar te liggen en convergeert de rij naar een limiet. Volgens ons lint liggen dus bijvoorbeeld . . . 5227289 en . . . 4227289 heel dicht bij elkaar.
Met p-adische getallen kunnen we ook rekenen, dit gaat eigenlijk net zo als dat we ii bij de re¨ele getallen gewend zijn. Er blijken dan wel wonderlijke dingen te gebeuren. De p-adische getallen kennen bijvoorbeeld geen onderscheid tussen positieve en negatieve getallen. En als a groter is dan b, dan kan het zomaar zijn dat a + c kleiner is dan b + c. Tussen de mystieke p-adisch getallen zitten zomaar getallen die we al lang kennen: alle rationale getallen komen ook voor tussen p-adische getallen. Ze zijn dan echter wel bijna onherkenbaar van gedaante veranderd.
Eerst moeten we leren rekenen met de getallen, dat is een belangrijke eerste stap om ze te begrijpen. Daarna nemen we een duik in de moderne algebra waar we hulpmiddelen zoeken om de p-adische getallen beter te bestuderen. Alles in de wiskunde hangt met elkaar samen, het zou kortzichtig zijn om wiskundige vragen te vermijden die op het eerste gezicht niet met p-adische getallen te maken hebben. We hopen dat je net zo veel plezier zult beleven aan het lezen hiervan als dat wij aan het schrijven hebben gehad.
Dat wij met plezier aan dit onderzoek hebben gewerkt was niet mogelijk geweest zonder de inspirerende gesprekken met Roelof Bruggeman. Hij heeft veel tijd besteed aan het begeleiden en in goede banen leiden van ons onderzoek. We hebben veel van hem geleerd, zowel zuivere wiskunde als het maken van een goed verslag, en we zijn hem veel dank verschuldigd. We ontvingen nuttig commentaar van Philip van Egmond, Corn´e Ruwaard, Erik Nonhebel en Marlien Sneller die het manuscript hebben doorgespit, we willen hen daar hartelijk voor danken.
Opmerking. Behalve dit voorwoord en het omslagplaatje hebben we vrijwel niets ver- anderd aan dit werkstuk. Het is daarom wiskundig van minder hoog niveau dan het werkstuk over de Laatste stelling van Fermat dat ook op mijn webpagina te vinden is, maar misschien daarom juist waardevoller voor vwo-leerlingen: er wordt minder voor- kennis vereist. Toch wil ik graag kwijt dat de p-adische getallen veel en veel meer omvatten dan we in dit werkstuk konden behandelen of zelfs maar konden vermoeden. Ze zijn essentieel in de moderne getaltheorie, maar om te begrijpen waarom heb je min of meer drie jaar universitaire wiskunde nodig. De link met getaltheorie kunnen we als volgt zien: bijvoorbeeld de rij 6, 56, 756, 2756, . . . met als grondtal het priemgetal p stelt het getal . . . 2756 voor modulo p, p2, p3 , p4, p5 . . .. Rekenen modulo m is in zekere zin
‘informatie vergeten’ of ‘minder nauwkeurig naar het getal kijken’ zodat het getal een- voudiger wordt, en hoe groter m, hoe groter de ‘graad van nauwkeurigheid’. We zoomen dus steeds verder in, en als we dit tot in het oneindige herhalen hebben we het getal
‘gelift’ naar de p-adische wereld. Er zit veel getaltheoretische informatie in verstopt, maar daar blijft het niet bij: net als bij de re¨ele getallen kunnen we de analyse inschake- len. Zo kunnen we bijvoorbeeld de afgeleide bekijken van een functie van een p-adische variabele, en we kunnen het hebben over ex met x een p-adisch getal. Op deze manier wordt een brug gebouwd tussen twee ogenschijnlijk verschillende vakgebieden. Dit alles kunnen we hier helaas niet behandelen, maar toch ben ik ervan overtuigd dat er genoeg interessants overblijft om te inspireren tot verdere studie.
Alle correcties en suggesties voor verbetering kun je sturen naar
lars.vd.berg@kpnmail.nl. Lars van den Berg, november 2011
Inhoudsopgave
Voorwoord ii
1 Kennismaking met g-adische getallen 3
1.1 Wat zijn g-adische getallen? . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 g-adisch rekenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Er zitten breuken verstopt in Qg . . . . . . . . . . . . . . . . . . . . . . . 8
2 Algebra¨ısche structuren 11
2.1 Algebra in een notendop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Symbolen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Ringen en Lichamen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Enkele stellingen over algebra¨ısche structuren . . . . . . . . . . . . . . . . 16
2.5 Getalsystemen als algebra¨ısche structuren . . . . . . . . . . . . . . . . . . 18
2.5.1 N, de Natuurlijke getallen . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.2 Z, de Gehele getallen . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.3 Q, de Rationale getallen . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.4 R, de Re¨ele getallen . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.5 C, de Complexe getallen . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.6 Zp en Qp , de p-adische gehele en gebroken getallen . . . . . . . . . 20
3 Precieze invoering van de ring Zg 21
3.1 Voorbereiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Bezwaren tegen de P methode . . . . . . . . . . . . . . . . . . . . 23
3.2 Formele definitie van Z∗ en Zg . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Algoritmes voor Z∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Optelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 Vermenigvuldiging . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Normalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.1 Lemma’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.2 Bewijs: Zg is een commutatieve ring met 1 . . . . . . . . . . . . . 34
3.5 Deelbaarheid in Zg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.1 Nuldelers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.2 Wanneer kun je delen in Zg ? . . . . . . . . . . . . . . . . . . . . . 39
3.6 Algoritme voor deling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 Formele invoering van het lichaam Qp 43
Hoofdstuk 1 Kennismaking met g-adische getallen
In de volgende hoofdstukken gaan we de g-adische getallen formeel defini¨eren en aan de hand daarvan een aantal stellingen bewijzen. Voordat we dit doen is het belangrijk dat we eerst een goed intu¨ıtief beeld hebben van wat deze getallen voorstellen. Dat doen we in dit hoofdstuk: alles wat hier wordt besproken is nog puur informeel. Maak je daarom geen zorgen over ‘vage’ definities en formules, het meer precieze werk komt later.
Merk op dat we hier g-adisch schrijven in plaats van p-adisch. g of p is een constante en stelt het grondtal voor; zo hebben de 10-adische getallen als grondtal 10. Later zal blijken dat het speciale geval dat g een priemgetal is, een belangrijke rol speelt. Voortaan als we p-adisch schrijven is p een willekeurig priemgetal; als er g-adisch staat, is g een willekeurig natuurlijk getal1 groter dan 1.
Door de tekst heen staan hier en daar oefeningen, die helpen je de stof beter te begrijpen. De antwoorden staan op pagina 61.
In dit werkstuk gebruiken we een decimale punt in plaats van een decimale komma, zoals in de wetenschappelijke literatuur gebruikelijk is.
1.1 Wat zijn g-adische getallen?
Voordat we de bizarre wereld van de g-adische getallen gaan verkennen, is het verhel- derend om eerst de bekende getallen eens nader te bekijken. Dan kunnen we daarna de analogie met de g-adische getallen gemakkelijker inzien.
We zijn gewend om met re¨ele getallen te werken, dat zijn getallen die als volgt kunnen worden geschreven (met eventueel een minteken ervoor).
an . . . a3a2 a1a0.a−1 a−2 . . . (1.1) Hier zijn ai de cijfers, niet-negatieve gehele getallen kleiner het grondtal2 g. De re¨ele
getallen zijn dus alle getallen die, uitgeschreven in cijfers, links van de komma eindig
1 De natuurlijke getallen zijn de niet-negatieve gehele getallen, dus 0, 1, 2, 3, . . .
2 Voor het gemak gaan we voorlopig uit van grondtal 10.
veel cijfers hebben, en rechts oneindig veel. Bijvoorbeeld 1 = 0.25 = 0.25000 . . . is een
√ 4
re¨eel getal, net als π = 3.141592654 . . . en 100
2 = 141.42135 . . .. In het bijzonder zijn
alle gehele getallen, en alle breuken met gehele getallen in de teller en noemer3, ook re¨ele getallen. Andersom geldt het echter niet!
Het is van de meeste re¨ele getallen onmogelijk om hun getalwaarde exact te bepalen: ze zijn immers oneindig lang en ‘bijna’ allemaal onregelmatig. Nu liggen de meeste mensen daar niet wakker van. Het is duidelijk dat elk re¨eel getal willekeurig dicht benaderd kan worden door een getal met eindig veel cijfers; bijvoorbeeld 3.141592 is voor de meeste toepassingen een voldoende nauwkeurige benadering van π. Immers, twee re¨ele getallen die pas vanaf de zevende decimaal verschillen, liggen dicht bij elkaar, en nog dichter als ze pas vanaf de twintigste decimaal verschillen. Dit komt doordat in R de volgende limiet geldt:
lim
n→∞
g−n = 0 (1.2)
en a0.a−1 a−2 . . . betekent niets anders dan a0g
i
+ a−1g−
+ a−2g−
+ . . . Hoe groter i,
des te kleiner de invloed van a−i g−
op de grootte van het getal.
In de volgende rij liggen twee opeenvolgende getallen steeds dichter bij elkaar. De rij
convergeert naar een limietwaarde ; die limietwaarde is een re¨eel getal.
300
310
314
314.1
314.15
314.159
314.1592
. . .
Het leuke is dat we met alleen deze kennis al een idee kunnen krijgen van wat g-adische getallen voorstellen. Het werkt namelijk net zo als bij de re¨ele getallen, alleen dan precies andersom! De g-adische getallen zijn getallen van de vorm
. . . a3 a2a1a0 .a−1a−2 . . . a−n (1.3)
waarbij ai de cijfers zijn, niet-negatieve gehele getallen kleiner dan het grondtal g. Blijkbaar lopen de g-adische getallen links van de komma oneindig, en rechts eindig ver door. Je vraagt je misschien af wat deze getallen voor nut kunnen hebben: ze zijn immers allemaal oneindig groot! Toch blijkt dat aan g-adische getallen een bepaalde, eindige grootte kan worden toegekend. We kunnen namelijk het grondtal g als ‘klein’ beschouwen, zodat geldt:
lim
n→∞
gn = 0 (1.4)
Dit is wiskundig gezien natuurlijk onmogelijk omdat g > 1, maar omdat we nu nog informeel bezig zijn, maken we ons daar niet druk over. Ook stellen we: hoe verder een
3 Dit worden ook wel de rationale getallen genoemd.
cijfer naar links ligt, hoe minder invloed het heeft op de grootte van het getal. Zo liggen de opeenvolgende rationale getallen in de volgende rij steeds dichter bij elkaar.
0.003
0.013
0.413
1.413
51.413
951.413
2951.413
. . .
De rij convergeert 10-adisch gezien naar een limietwaarde ; deze limietwaarde is een 10- adisch getal.
Met deze nogal vreemde beschouwing van ‘grootte’ kunnen we verwachten dat er ook vreemde dingen gebeuren. Bekijk bijvoorbeeld het volgende rijtje dat 10-adisch gezien steeds dichter naar −1 nadert.
9 = −1 + 101
99 = −1 + 102
999 = −1 + 103
9999 = −1 + 104
. . .
Volgens (1.4) is limn 10n
= 0, dus er moet wel gelden dat . . . 99999 = −1. Blijkbaar
kunnen positieve g-adische getallen een negatief (geheel) getal voorstellen! Later zal blijken dat alle tegengestelden van g-adische getallen zonder minteken geschreven kunnen worden. Het heeft daarom geen zin om negatieve getallen als − . . . a2a1a0 in te voeren,
want die bestaan allemaal al onder de g-adische getallen.
Voor de re¨ele getallen maakt het niet veel uit in welk grondtal je werkt; je kunt elk re¨eel getal in elk gewenst grondtal g ∈ N, g ≥ 2 schrijven. Bijvoorbeeld 1347 = 1024 + 256 +
64 + 2 + 1 = 10101000011 in grondtal 10 resp. 2. Bij de g-adische getallen blijkt het grondtal w´el uit te maken: je krijgt in sommige gevallen ´echt andere getallen als je op een ander grondtal overgaat.
In hoofdstuk 3 zullen we bewijzen dat er geen ‘nuldelers’ onder de g-adische getallen zijn, precies dan als g een priemgetal is. Nuldelers zijn getallen a en b ongelijk aan 0 waarvoor ab = 0, ofwel a = 0 en b = 0 . Het blijkt belangrijk te zijn dat er geen nuldelers
b a
bestaan, daarom kijken we later alleen naar de situatie dat g priem is. Voorlopig is het
voldoende dat g een natuurlijk getal groter dan 1 is.
Dan nog wat terminologie en afkortingen. Terloops hebben we de natuurlijke, de gehele, de rationale en de re¨ele getallen genoemd. De verzamelingen die uit precies al deze getal- len bestaan, duidt men aan met N, Z, Q resp. R. Wellicht ken je ook C, de verzameling complexe getallen. Later zullen we wat dieper ingaan op deze getalstelsels, evenals op het begrip verzameling.
De g-adische getallen die geen cijfers rechts van de komma hebben, noemen we de
g-adische gehele getallen. Volgens (1.3) zijn dit de getallen van de vorm
. . . a4 a3 a2a1a0 (1.5) De verzameling van alle g-adische gehele getallen noemen we Zg . Let op: welke getallen
deze verzameling bevat, hangt van het grondtal g af ! Er blijken zelfs oneindig veel verzamelingen Zg te zijn.
1.2 g-adisch rekenen
Het optellen en aftrekken in Zg gaat ongeveer hetzelfde als in R. We rekenen elements- gewijs en van rechts naar links, waarbij we naar links toe ‘overlenen’. Voor optelling in Z10 bijvoorbeeld houdt dat in dat je cijfer voor cijfer optelt, en als de som groter is dan
10, bijvoorbeeld 17, leen je de 1 van 17 over naar links zodat je 7 overhoudt. Hieronder
staan een paar voorbeelden van optellen en aftrekken in Z10 .
. . . 39142
. . . 86951 +
. . . 26093
. . . 74801
. . . 95236 −
. . . 79565
. . . 00000
. . . 39802 −
. . . 60198
Je kunt op deze manier elk paar willekeurige g-adische gehele getallen a en b optellen of aftrekken. Op deze manier kun je van elke a de tegengestelde −a berekenen door a van
0 = . . . 00000 af te trekken, zoals in het laatste voorbeeld is gedaan. Ter controle kun je daar snel berekenen dat inderdaad a + (−a) = 0.
Oefening 1.2.1.
a. Bereken exact de 10-adische uitkomst van 0 − 1. Komt dit overeen met wat we op pagina 5 hebben geconstateerd over −1?
b. Benader in 5 decimalen nauwkeurig: . . . 41342 + . . . 30243, maar nu in grondtal
5.
c. Stel dat de twee getallen die je bij b hebt opgeteld in 10 decimalen nauwkeurig waren gegeven. Had dat invloed kunnen hebben op de 5 decimalen die je daar hebt berekend?
Het lijkt er dus op dat als g-adische getallen a en b in n decimalen nauwkeurig bepaald zijn, we ook a + b ook in n decimalen nauwkeurig kunnen berekenen. Dat is handig, want als n naar oneindig gaat, weten we zeker dat a + b naar een g-adisch getal convergeert. In R zitten daar wat haken en ogen aan. Neem bijvoorbeeld de re¨ele getallen a = 2.19635 . . . en b = 3.23864 . . ., een simpele berekening leert dat a + b = 5.43499 . . .. Liggen deze zes
Tabel 1.2: Vermenigvuldigen en delen in Z10
. . . 22901
. . . 37586 ×
. . .37406
. . . 3208
. . . 505
. . . 07
. . . 3 +
. . .56986
3 / . . . 0000001 . . . 6667
21 −
. . .9999980
180 −
. . .9999800
1800 −
. . .9998000
18000 −
. . .
cijfers nu vast? Nee, dat hoeft niet. Stel dat we a en b iets beter benaderen, we vinden bijvoorbeeld a = 2.196358277 . . . en b = 3.238643530 . . .. Dan is a + b = 5.435001807 . . .; je ziet dat de eerste vijf decimalen niet allemaal overeenkomen met die van de eerder bepaalde waarde van a + b. In het algemeen is het zo dat tot en met de eerste decimaal van rechts die geen negen is, de cijfers onzeker zijn in een benadering in R. In Zg hebben we daar geen last van, omdat rechts altijd een eindig aantal decimalen staat.
We kunnen ook vermenigvuldigen in Zg , dit gaat net zoals in R. Zie de linker som in Tabel 1.2.
Delen levert wat problemen op. Slechts in sommige gevallen kan dat met een staartdeling; bovendien is de methode daarvoor in Zg even wennen. Een voorbeeld staat in Tabel 1.2 uitgewerkt naast de vermenigvuldiging, hier wordt 1 in Z10 berekend. Je moet bij zo’n staartdeling sommige dingen net andersom doen dan je gewend bent, omdat de meest
‘invloedrijke’ cijfers rechts staan. Je wilt eerst het meest rechtse cijfer weg hebben, in dit geval een 1. Dat kan, want 3 ×7 = 21; we zetten dus een 7 bij de uitkomst. Nu berekenen we 1 −21 = . . . 9999980 (ga maar na). Vervolgens willen we de 8 wegpoetsen, dit doen we met 3 × 6 = 18. We zetten daarom een 6 neer bij de uitkomst van het quoti¨ent, links van
de 7 die er al stond. (Zie je waarom?) Aftrekken levert . . . 9999800, weer hetzelfde getal als daarnet, maar nu met een nul erbij! De 8 kunnen we weer wegpoetsen met 3 × 6, dan krijgen we . . . 9998000, etc. Bij het quoti¨ent komen er steeds meer zessen bij, terwijl bij
de rest een steeds langere staart van nullen groeit; de rest wordt volgens de 10-adische beschouwing van grootte (zie vgl. (1.4)) steeds kleiner en nadert naar 0. Daarom is
3 = . . . 666667 in Z10 . En inderdaad, als we ter controle 3 × . . . 666667 berekenen komt
er 1 uit.
Bij het delen in Zg kom je al snel in de problemen. Probeer in Z10 maar eens 1 te
berekenen met een staartdeling. Je wilt net zoals in het vorige voorbeeld allereerst het meest rechtse cijfer a0 van het quoti¨ent zoeken waarmee je de 1 kan wegpoetsen. Dat is
echter onmogelijk, want a0 × 6 is altijd even en kan dus nooit 1 zijn! We kunnen nog wel andere dingen proberen, maar dat heeft geen zin. Immers, als x = 1 is 6x = 1; deze vergelijking is niet oplosbaar in Z10 , want het meest rechtse cijfer in 6x is even en in 1 is het oneven.
Voor delingen onder de g-adische getallen blijkt het handig zijn om kommagetallen toe te staan, die we al gezien hebben bij vgl. (1.3). De verzameling van deze g-adische kommagetallen noemen we Qg . Eigenlijk is dat wiskundige niet helemaal correct, want Qg heeft alleen ‘zin’ als g een priemgetal is. In hoofdstuk 4 zullen we zien waarom. Daar zullen we ons nu echter niet druk om maken.
In Q10 is de vergelijking 6x = 1 w´el oplosbaar. Omdat daar ook komma’s zijn toegestaan, hoeft het meest rechtse cijfer van 6x niet hetzelfde te zijn als het meest rechtse cijfer van 1. Neem bijvoorbeeld x = . . . 33333.5, dan is 2x = . . . 66667.0 en dat
is 1
zoals we gezien hebben. Dus 6x = 1. Dit konden we doen doordat 5 × 2 = 10 ≡ 0
(mod 10).4
Het optellen en vermenigvuldigen in Qg gaat hetzelfde als in Zg , waarbij je rekening moet houden met de plaats van de komma. Naar analogie van de voorbeelden op pagina
6 en 7 is bijvoorbeeld . . . 391.42 + . . . 869.514 = . . . 260.934, en . . . 2290.1 × . . . 375.86 =
. . . 56.986. Merk op dat het in R net zo gaat.
Delen door middel van een staartdeling in Qg gaat echter mis als g geen priemgetal is. Dat komt doordat er dan nuldelers in Zg zitten.
Oefening 1.2.2.
a. Bereken exact in Z5: (Let op: werk dus in grondtal 5.)
1421 × . . . 222222220413
Welk getal in Z stelt dit product voor (in grondtal 5)?
b. Bereken, indien mogelijk, 1 in Z10 . Heeft dit quoti¨ent een repeterende staart?
Dezelfde opdracht voor 1 .
c. Had iemand anders een andere uitkomst voor 1 in Z10 kunnen krijgen dan jij?5
Met andere woorden, is er een paar getallen uit de tafel van 7 met hetzelfde rechtercijfer, zodat een bepaald cijfer dus op meerdere manieren kan worden weggepoetst? En hoe zit dat met de tafel van 8?
1.3 Er zitten breuken verstopt in Qg
We hebben al gezien dat niet alle getallen in Qg per se als naar links oneindig doorlopende getallen hoeven te worden geschreven. Er bleken ook ‘normale’ getallen in te zitten, getallen die we al kenden. Bijvoorbeeld alle gehele getallen, en sommige rationale getallen
zoals 15.3, 1
en 1 . Dit zijn allemaal getallen die in de g-adische vorm een repeterende
4 Maak je geen zorgen als je niet weet wat (mod 10) is, hier komen we in hoofdstuk 3 op terug.
5 In de veronderstelling dat er geen rekenfouten zijn gemaakt.
1.3. ER ZITTEN BREUKEN VERSTOPT IN QG
staart hebben, namelijk . . . 00015.3, . . . 6667 en . . . 2857142857143. Men kan bewijzen dat een getal a uit Qg precies dan als getal in Q kan worden geschreven als a in de g-adische vorm een repeterende staart heeft. Er zijn natuurlijk heel veel onregelmatige g-adische getallen, deze kunnen dus niet als rationaal getal worden geschreven, en, zo kan men bewijzen, zelfs niet als re¨eel getal.
We focussen we ons nu op repeterende g-adische getallen. Hoe kunnen zij als rationaal
getal worden geschreven? Dit lichten we toe aan de hand van een paar voorbeelden; het algemene geval gaat net zo.
Voorbeeld 1.3.1. We nemen het 10-adische getal x = ...77777 en zijn benieuwd welk rationaal getal x voorstelt. Dat is niet moeilijk. Eerst berekenen 10x = . . . 77770. Ver- volgens berekenen we
−9x = x − 10x = . . . 77777 − 77770 = . . . 00007 = 7
waaruit volgt dat
x = −7
9
Wat we hier hebben gedaan was vrij intu¨ıtief en informeel; we zullen eens nader beschouwen wat we allemaal gebruikt hebben. Het blijkt dat de somformule van de meetkundige reeks hier belangrijk is. Een meetkundige reeks heeft te maken met een on- eindig lange getallenrij van de vorm a0 , a1, a2, a3, . . . waarin de opeenvolgende elementen steeds met dezelfde factor worden vermenigvuldigd. Er geldt dus steeds dat ai+1 = kai voor een zekere re¨ele constante k = 1. Je kunt makkelijk inzien dat de getallenrij ook geschreven kan worden als ak0, ak1, ak2, ak3, . . . waarbij a = a0 .
We willen alle oneindig veel elementen van de rij bij elkaar optellen. Of daar een
echt getal uitkomt of niet zien we later wel. Eerst beschouwen we een benadering van wat we willen berekenen, namelijk de som van de eerste n + 1 elementen. Deze noemen we xn . Dan berekenen we kxn , en vervolgens trekken we de twee van elkaar af. Hierbij vallen op twee na alle termen tegen elkaar weg.
xn = ak0 + ak1 + ak2 + ak3 + . . . + akn
kxn = ak1 + ak2 + ak3 + . . . + akn + akn+1
(1 − k)xn = ak0 − akn+1
Hieruit volgt dat
xn =
a(k0 kn+1 )
(1.6)
1 − k
Deze deling kunnen we uitvoeren omdat k = 1.
We zijn niet op zoek naar een benadering, maar naar de exacte waarde van limn→∞ xn =
ak0 + ak1 + ak2 + . . . Om deze te bepalen laten we n in (1.6) naar oneindig gaan. Er zijn dan twee6 mogelijkheden. Als |k| > 1 gaat kn+1 naar (min) oneindig; dan divergeert xn
n+1
zodat x∞ geen getal kan zijn. Als −1 < k < 1 gaat k
a(k0 − 0) a
naar 0; dan is dus
lim
n→∞
xn =
1 − k
=
1 − k
(1.7)
Een som van oneindig veel termen kan dus een rationaal getal opleveren! Dat wisten we eigenlijk al, want bijvoorbeeld 0.33333 . . . in grondtal 10 is niets anders dan een meetkundige reeks met a = 0.3 en k = 0.1. Uit (1.7) volgt dat
0.33333 . . . =
0.3
=
1 − 0.1
0.3 1
=
0.9 3
Nog een voorbeeld: 0.142857142857 . . . is een meetkundige reeks met a = 0.142857 en
k = 10−6 (ga dat na ), dus
0.142857142857 . . . =
0.142857
=
1 − 10−6
0.142857 1
=
0.999999 7
Hierboven hebben we gesteld dat de som van de meetkundige reeks alleen oplosbaar is
n+1
als |k| < 1, want alleen dan is limn→∞ k
= 0. Bij g-adische getallen is het echter
juist andersom, want volgens (1.4) gaat kn+1 naar 0 als k > 1! Daarom mogen we (1.7)
ook op repeterende getallen van Qg toepassen. Als voorbeeld nemen we weer . . . 77777 in Z10 , dit is een meetkundige reeks met a = 7 en k = 10.
. . . 77777 =
7 7
=
1 − 10 9
Je ziet dat er een negatieve breuk uitkomt! Omdat altijd geldt dat k > 1 en a > 0 is dat voor alle g-adische getallen het geval. Uiteraard zitten er ook positieve breuken in Qp , je kunt namelijk met de methode van pagina 6 de tegengestelde van bijv. . . . 77777 berekenen.
Alle g-adische getallen met repeterende staart zijn ook rationaal getal. Een voorbeeld laat zien hoe het algemene bewijs verloopt. We rekenen weer in Q10 .
. . . 2780527805139.46 = 103 . . . 2780527805 + 139.46 = 103 27805
1 − 105
+ 139.46
= 27805000 − 13945860.54 =
−99999
−1385913946
9999900
Men kan bewijzen dat alle rationale getallen als g-adisch getal te schrijven zijn, ofwel,
Q ∈ Zg voor alle g ∈ N, g > 1. Dat doen we hier echter niet.
6 Eigenlijk is er nog een derde mogelijkheid, namelijk k = −1. Dit is een geval apart, we bespreken het hier niet.
Hoofdstuk 2 Algebraïsche structuren en getalsystemen
2.1 Algebra in een notendop
Voor veel mensen betekent algebra zoiets als ‘rekenen met letters’. Algebra is echter veel meer dan dat. Heel globaal houdt de algebra zich bezig met het bestuderen van struc- tuur, zoals symmetrie¨en van regelmatige veelvlakken en de structuur van de verzameling priemgetallen in andere getalstelsels. De basisobjecten waar we altijd van uitgaan zijn verzamelingen waar inwendige bewerkingen op zijn gedefinieerd.
Verzamelingen Informeel is een verzameling het geheel van een aantal bij elkaar ho- rende objecten, een veelheid beschouwd als ´e´en.1 Objecten die in een bepaalde verza- meling niet op te delen zijn in kleinere objecten, worden elementen van die verzameling genoemd. Een object dat is opgebouwd uit meerdere elementen van een verzameling, wordt een deelverzameling daarvan genoemd. Deze is op zichzelf ook weer een verzame- ling.
We geven een voorbeeld. Alle mensen op aarde vormen een verzameling V . Alle Nederlanders vormen een deelverzameling W daarvan, en alle Nederlanders met blauwe ogen vormen daar weer een deelverzameling X van. Een willekeurige Nederlander met blauwe ogen is een element van X , en dus ook van W en van V . Natuurlijk weten wij dat een mens weer is opgebouwd uit achtereenvolgens organen, cellen, organellen, moleculen etc., maar wiskundig gezien wordt de mens in V , W en X als element beschouwd.
Een verzameling wordt vaak afgekort met een hoofdletter, en aangeduid met ac- colades waarbinnen een wiskundige omschrijving van de verzameling staat. Bijvoor- beeld A = {1, 3, 105} is de verzameling bestaande uit de drie getallen 1, 3 en 105. De
volgorde waarin de elementen staan maakt niet uit, dus A = {1, 3, 105} = {105, 1, 3}. Verzamelingen mogen oneindig veel elementen bevatten, denk bijvoorbeeld aan N =
{0, 1, 2, 3, 4, 5, . . .}. Het symbool ∈ wordt uitgesproken als ‘. . . is een element van de
1 Bron: [8]
verzameling . . . ’, of kortweg als ‘in’. Als gegeven is dat x ∈ A weet je dus dat x ´e´en van de drie getallen 1, 3 en 105 is. Als x ∈ N is x een natuurlijk getal.
In het algemeen wordt een verzameling V als volgt aangeduid:
V = {f (x) | omschrijving van x}
Dit is de verzameling van precies alle elementen f (x) waarvoor x aan de omschrijving rechts van de verticale streep voldoet. Bijvoorbeeld {2x + 1 | x ∈ N} is de verzameling van alle 2x + 1 waarvoor x een natuurlijk getal is: de oneven natuurlijke getallen dus.
Met V≥k bedoelen we de verzameling W = {x ∈ V | x ≥ k}.
Operaties, samenstellingswetten en inwendigheid Laat V1 en V2 twee verza- melingen zijn. Een operatie of bewerking van V1 naar V2 is een functie waarmee een combinatie van elementen van V1 wordt afgebeeld naar een element van V2. Dit klinkt wat ingewikkeld, maar bijvoorbeeld optellen en vermenigvuldigen zijn operaties van N naar N. Zo wordt 4 + 7 afgebeeld naar 11. We noemen + en × binaire operaties, omdat het altijd om een combinatie van twee elementen gaat.
We weten intu¨ıtief dat de regel a+b = b+a voor alle natuurlijke getallen a en b opgaat. Dit is een voorbeeld van een samenstellingswet. In §2.3 gaan we dieper op dergelijke wetten in. Al met enkele samenstellingswetten is het mogelijk om nieuwe wetten af te leiden. Dat is een van de mooiste eigenschappen van de wiskunde: uitgaande van een paar eenvoudige ‘basisregels’ kun je enorm veel, misschien wel oneindig veel nieuwe wetmatigheden ontdekken.
Er zit alleen een addertje onder het gras: samenstellingswetten mogen vaak alleen gecombineerd worden als ze inwendig zijn. Dat bijvoorbeeld + en × inwendig zijn in N, betekent dat a + b ∈ N resp. a × b ∈ N voor alle a, b ∈ N. Stel dat de operatie × niet
inwendig was in N, konden we er niet vanuit gaan dat ce een natuurlijk getal was, ook al waren c en e dat wel. Dit zou betekenen dat we niet zonder meer mochten beweren dat ce+b = b+ce. Gelukkig zijn + en × wel inwendig in N, zoals je gemakkelijk kunt nagaan. Daardoor zijn alle operaties samengesteld uit + en ×, zoals a(b + c), automatisch ook inwendig.
‘Aftrekken’ is een voorbeeld van een operatie die niet inwendig is in N. Bijvoorbeeld
5 − 7 = −2 is kleiner dan 0 en zit dus niet in N.
Om dubbelzinnigheden te voorkomen, gebruiken we in formele gedeelten overal waar dat nodig is haakjes. Alleen als er echt geen verwarring kan ontstaan, laten we ze weg. Zo gaat vermenigvuldiging bij afspraak vo´or optelling bij het ontbreken van haakjes. Verder laten we het ×-teken voor de overzichtelijkheid vaak weg, of schrijven we • ervoor in de plaats.
2.2 Symbolen
We zullen in dit werkstuk hier en daar gebruik maken van symbolen. E´en ervan zijn we al tegengekomen, namelijk ∈. Er zijn nog veel meer symbolen met een vaste betekenis,
Tabel 2.1: Enkele belangrijke symbolen
Symbool
Lees dit als:
∈
. . . (is een element) van de verzameling . . .
∀
Voor alle . . .
∃
Er is een . . .
:
. . . zodat geldt . . . ; of: . . . geldt het volgende: . . .
⊂
. . . is een deelverzameling van . . .
:=
. . . is per definitie gelijk aan . . .
⇒
. . . als . . . dan . . .
⇔
. . . dan en slechts dan als . . .
degene die wij gebruiken (behalve de bekende zoals ≥) hebben we opgesomd in Tabel
2.1 op pagina 13. De symbolen op zichzelf betekenen eigenlijk niets; ze worden altijd gecombineerd met andere symbolen.
Een paar voorbeelden van wat we met deze symbolen kunnen uitdrukken, maken veel duidelijk.
• ∀a ∈ A : a < 106 betekent: ‘Voor alle elementen a van de verzameling A geldt: a
is kleiner dan 106.’
• ∃x, y ∈ N : ∀a ∈ V : (a > x ⇒ a > y) betekent: ‘Er zijn natuurlijke getallen x, y
zodat voor alle a in V geldt: als a groter is dan x, dan is a groter dan y.’ We doen een paar opmerkingen over Tabel 2.1.
• A := B of B =: A betekent: we kennen B al, en cre¨eren nu een A die per definitie gelijk is aan B.
• A ⇒ B betekent: Als bewering A waar is, dan volgt daaruit dat bewering B ook waar is. Het zegt dus niets over de waarheid van A.
• A ⇔ B betekent dat A en B of beide waar of beide onwaar zijn. Dit wordt vaak uitgesproken als: A is waar dan en sl´echts dan als B waar is.
• V ⊂ W betekent dat V een deelverzameling is van W of gelijk is aan W . In symbolen: ∀a ∈ V : a ∈ W . Je kunt gemakkelijk inzien dat uit V ⊂ W en W ⊂ V volgt dat V = W .
Optelling
Tabel 2.2: Enkele samenstellingswetten
1) Inwendigheid van de optelling. Als a, b ∈ V , dan is ook a + b ∈ V .
2) Associativiteit van de optelling. (a + b) + c = a + (b + c)
3) Nulelement. Er is een 0 ∈ V zodat a + 0 = 0 + a = a.
4) Tegengestelde. Voor alle a ∈ V is er een tegengestelde −a ∈ V , zodat a + (−a) = (−a) + a = 0.
5) Commutativiteit van de optelling. a + b = b + a
Vermenigvuldiging
1) Inwendigheid van de vermenigvuldiging. Als a, b ∈ V , dan is ook a × b ∈ V .
2) Associativiteit van de vermenigvuldiging. (a × b) × c = a × (b × c)
3) Eenheidselement. Er is een 1 ∈ V zodat a × 1 = 1 × a = a.
4) Inverse. Voor alle a ∈ V, a = 0 is er een inverse a−1 ∈ V , zodat a × a−1 =
a−1 × a = 1.
5) Commutativiteit van de vermenigvuldiging. a × b = b × a
Combinatie
6) Distributiviteit. a(b + c) = ab + ac (links-distributiviteit), ´en (a + b)c = ac + bc
(rechts-distributiviteit).
7) Nul keer iets is nul. a × 0 = 0 × a = 0
8) V bevat geen nuldelers. Er kan alleen maar gelden dat ab = 0 als minstens
´e´en van beide a of b nul is.
2.3 Ringen en Lichamen
De ring en het lichaam zijn voorbeelden van algebra¨ısche structuren. Een algebra¨ısche structuur (V, +, ×) is een verzameling V waarop twee binaire operaties + en × zijn gedefinieerd, die aan bepaalde samenstellingswetten voldoen.2 Hoewel + en × niet per
se overeen hoeven te komen met de bekende optelling en vermenigvuldiging, is dat in dit werkstuk wel altijd zo. Een voorbeeld van een algebra¨ısche structuur is (N, +, ×). Op pagina 12 hebben we al een paar samenstellingswetten voor N gezien. In Tabel 2.2 op
pagina 14 staan er nog een aantal; deze gaan niet allemaal op voor N. De wetten gelden steeds voor alle elementen a, b en c van een zekere verzameling V .
Ook 0 en 1 hoeven niet per se overeen te komen met de bekende nul en ´e´en. In de algebra stellen het zelfs geen getallen voor. In dit werkstuk komen ze daarmee echter wel altijd overeen.
We zien drie soorten rekenregels in Tabel 2.2. Vijf regels gaan over de optelling, vijf soortgelijke regels gaan over vermenigvuldiging. De laatste drie regels gaan over de
2 Er zijn ook andere soorten algebra¨ısche structuren, maar die bestuderen we hier niet.
interactie tussen optellen en vermenigvuldigen.
Oefening 2.3.1.
a. Kunnen er algebra¨ısche structuren bestaan waarvoor wel de regels 7) en 8)
gelden, maar niet 3) voor optelling?
b. Welke van de samenstellingswetten uit Tabel 2.2 gelden voor V = N?
c. Dezelfde vraag voor Z, Q en R. Als je kunt rekenen met complexe getallen, kun je de vraag ook voor C beantwoorden.
Er zijn veel verschillende soorten algebra¨ısche structuren, afhankelijk van het aantal ope- raties en van de samenstellingswetten waaraan wordt voldaan. Veelgebruikte structuren hebben een naam gekregen; wij noemen er hier drie. De nummers verwijzen weer naar Tabel 2.2.
• Een algebra¨ısche structuur met een nulelement, waar optelling en vermenigvuldi- ging inwendig en associatief zijn en de optelling bovendien commutatief is, en waar de distributiviteit geldt, noemen we een halfring. Dit is dus een structuur die in
elk geval voldoet aan 1), 2), 3) en 5) voor +, aan 1) en 2) voor ×, en aan 6).
• Een halfring waarin bovendien ieder element een tegengestelde heeft, wordt een
ring genoemd. Dit is dus een halfring waar 4) geldt voor +.
• Een ring met een eenheidselement, waarin ieder element een inverse heeft en waarin bovendien vermenigvuldiging commutatief is, heet een lichaam. Dit is dus een ring waar 3), 4) en 5) gelden voor ×.
De begrippen ring en lichaam zullen we later nog vaak nodig hebben, daarom hebben we hun eigenschappen overzichtelijk in Tabel 2.4 gezet. Deze eigenschappen geleden in ieder geval, meer mag ook. Zo is elk lichaam automatisch ook een ring.
We kunnen bij de naam van een algebra¨ısche structuur de toevoegingen commuta- tieve, met 1 en zonder nuldelers plaatsen om aan te geven dat de regels 5) en 3) voor ×, en regel 8) gelden.3 Bijvoorbeeld een commutatieve ring met 1 waarvoor ook nog eens
ieder element een inverse heeft, is hetzelfde als een lichaam.
Oefening 2.3.2.
a. Ga na dat uit je antwoord bij opgave 2.3.1.a. volgt dat (N, +, ×) een commu- tatieve halfring met 1 zonder nuldelers is.
b. Welke algebra¨ısche structuren zijn Z, Q, R (en C)?
Het leuke is dat met enkel en alleen de samenstellingswetten uit Tabel 2.2 heel veel
3 Commutatieve gaat dan dus niet over optelling.
Tabel 2.4: Ring en Lichaam
Structuur
Samenstellingswetten
Ring
+: 1), 2), 3), 4), 5)
×: 1), 2); 6)
Lichaam
+: 1), 2), 3), 4), 5)
×: 1), 2), 3), 4), 5); 6)
(vaak zeer ingewikkelde) stellingen kunnen worden bewezen. Een aantal van de meest eenvoudige stellingen met bewijs kun je vinden in hoofdstuk 4 van [5]. Als bewezen is dat een stelling geldt voor bijvoorbeeld elke ring, mag deze op alle bekende ringen worden toegepast, bijvoorbeeld op Z, Q, R en C. Dat is de kracht van de algebra.
2.4 Enkele stellingen over algebra¨ısche structuren
In deze paragraaf bewijzen we drie stellingen die we later nog handig kunnen gebruiken. Bovendien geven de bewijzen een goed beeld van hoe je met algebra¨ısche structuren kunt werken. Als je algemene stellingen over bijvoorbeeld lichamen wilt bewijzen, kun je je niet beroepen op je intu¨ıtie over de lichamen Q, R en C die je al kent. Je wilt namelijk dat de stellingen gelden voor alle structuren die aan de eisen in Tabel 2.4 voldoen.
In dit werkstuk hebben we ervoor gekozen niet alle stellingen zo precies te bewijzen
als hier, dat zou veel te veel ruimte in beslag nemen en bovendien storend zijn voor het verhaal.
In de volgende stelling mag je voor ◦ zowel + als × invullen. Als boven een =-teken
bijvoorbeeld 2)◦ staat, betekent dit dat deze stap volgt uit samenstellingswet 2) voor operatie ◦ uit Tabel 2.2.
Stelling 2.4.1. Voor elke commutatieve ring (V, +, ×) geldt:
∀a, b, c, d ∈ V : (a ◦ b) ◦ (c ◦ d) = (a ◦ d) ◦ (c ◦ b)
Bewijs. Voor willekeurige a, b, c, d ∈ V geldt:
2)◦
5)◦
(a ◦ b) ◦ (c ◦ d) = a ◦ b ◦ (c ◦ d) = a ◦ (c ◦ d) ◦ b
5)◦
2)◦
2)◦
= a ◦ (d ◦ c) ◦ b = a ◦ d ◦ (c ◦ b) = (a ◦ d) ◦ (c ◦ b)
Dat stelling 2.4.1 geldt is intu¨ıtief meteen duidelijk, maar het kost toch wat moeite om hem te bewijzen!
De volgende stelling voorkomt dat we verderop in dit werkstuk zowel de rechts- als de links-distributiviteit moeten bewijzen.
Stelling 2.4.2. Voor elke commutatieve structuur (V, +, ×) geldt: als de links-distributiviteit waar is, dan ook de rechts-distributiviteit.
Bewijs. a, b en c zijn willekeurige elementen van V . Stel dat de links-distributiviteit geldt, zodat
Hieruit volgt:
a(b + c) = ab + ac (2.1)
(b + c)a
5)
= a(b + c)
(2.1)
= ab + ac
5)
= ba + ca
dus (b + c)a = ba + ca, de rechts-distributiviteit geldt dan dus ook. Hiermee is de stelling bewezen.
De laatste stelling gaat over eigenschap 7) uit Tabel 2.2 die zegt dat nul keer iets altijd nul is. Dit blijkt namelijk in elke commutatieve ring te gelden.4 In het bewijs laten we de verwijzingen boven de =-tekens weg; probeer zelf te achterhalen welke samenstel- lingswetten we gebruiken.
4 Het geldt zelfs voor elke ring, ook voor niet-commutatieve ringen. Geheel analoog aan het bewijs hier kun je namelijk aantonen dat 0 = 0 × a. In dit werkstuk vormt het echter geen beperking als de ring commutatief is.
Stelling 2.4.3. Voor elke commutatieve ring geldt:
∀a ∈ V : a × 0 = 0 × a = 0
Bewijs. Laat a een willekeurig element zijn van V . Er geldt:
0 = (a × 0) + −(a × 0) = (a(0 + 0) + −(a × 0) = a × 0 + a × 0 + −(a × 0)
= a × 0 + (a × 0 + −(a × 0) = a × 0 + 0 = a × 0
dus a × 0 = 0. Wegens de commutativiteit van × is dan ook 0 × a = 0, waarmee de stelling bewezen is.
2.5 Getalsystemen als algebra¨ısche structuren
We hebben tot nu toe zeven verschillende getalsystemen genoemd, nu zullen we daar wat meer over zeggen. De volgorde waarin ze staan, namelijk N, Z, Q, R, C, Zp , Qp , is niet willekeurig gekozen. Behalve Zp wordt elk van deze getalsystemen namelijk uit haar voorganger opgebouwd. Dat R wordt geconstrueerd vanuit Q is niet meteen duidelijk, maar in de wiskunde kunnen de re¨ele getallen gedefinieerd worden als limieten
van convergerende rijtjes rationale getallen. Zo is π/4 = arctan(1) = 1 − 1 + 1 −
1 3 5
1
7 + . . . Je kunt R ook construeren als oneindige decimale breuken, zoals we al hebben
aangeduid in hoofdstuk 1. Dat heeft wel twee bezwaren. Ten eerste moet je soms
verschillende decimale breuken identificeren. Zo is 1 = 0.99999 . . . Dat is lastig, maar niet onoverkomelijk. Ten tweede kun je je afvragen: “Als ik nu 8 vingers had, zou R er dan anders uit hebben gezien?” Gelukkig kan men bewijzen dat het voor de structuur van R niet belangrijk is welk grondtal je kiest.
Verder is elk hier genoemde getalstelsel deelverzameling van alle daaropvolgende stelsels (behalve Zp en Qp ), zoals je gemakkelijk intu¨ıtief kunt inzien.
Z ⊂ Zp
N ⊂ Z ⊂ Q ⊂ R ⊂ C
∩ ∩
Q ⊂ Qp
In het rechter schema zien we dat Z deelverzameling is van Zp , Q en Qp , en dat Qp de drie andere verzamelingen omvat. Maar bijvoorbeeld de inclusie Q ⊂ Zp is niet waar. Bijvoorbeeld 1 ∈ Q zit niet in Zp . Hier komen we in hoofdstuk 4 op terug.
N heeft in de volgorde die we aanhouden geen ‘voorganger’, maar je moet toch ergens beginnen. N wordt axiomatisch gedefinieerd en niet opgebouwd uit enig ander getalstelsel. Het staat aan de basis van alle ons bekende getalstelsels.
2.5.1 N, de Natuurlijke getallen
N is de verzameling natuurlijke getallen {0, 1, 2, 3, . . .}. Haar belangrijkste basiseigen- schappen zijn dat er een beginelement is (dat we 0 noemen), en dat ieder natuurlijk
getal een unieke opvolger in N heeft. In oefening 2.3.1 heb je intu¨ıtief ingezien dat N
een commutatieve halfring met 1 zonder nuldelers is.
Op het eerste gezicht hebben de natuurlijke getallen niet veel met p-adische getallen te maken, maar uiteindelijk is ook Zp , net als alle andere getalsystemen, gebaseerd op N.
2.5.2 Z, de Gehele getallen
Z is de verzameling gehele getallen {. . . , −3, −2, −1, 0, 1, 2, 3, . . .} bestaande uit de na- tuurlijke getallen, en voor elk natuurlijk getal zijn tegengestelde (0 is zijn eigen tegen- gestelde). Dat wil zeggen: Z = {a, −a | a ∈ N}.
Het grootste verschil tussen N en Z is dat Z geen beginelement heeft, en dat ieder getal een tegengestelde heeft. De gehele getallenlijn is als het ware symmetrisch ten opzichte van de 0.
We hebben N en Z formeel ingevoerd en bewezen dat ze een commutatieve halfring resp. ring met 1 zonder nuldelers vormen. Dit hebben we niet opgenomen in dit verslag. Men definieert Z op een heel andere manier dan N, en stellingen worden op een heel andere manier bewezen. Dit komt doordat N ‘uit het niets’ wordt opgebouwd, terwijl Z kan worden geconstrueerd vanuit N. De rekenregels die voor N bewezen zijn, kunnen handig worden gebruikt om stellingen over Z te bewijzen. Dit gaat voor de andere getalsystemen net zo.
In de uitbreiding van N naar Z hebben we geen eigenschappen gebruikt die spe- cifiek zijn voor N. Daarom kunnen we deze methode gebruiken om elke willekeurige commutatieve halfring met 1 uit te breiden naar een ring.
2.5.3 Q, de Rationale getallen
Q is de verzameling rationale getallen, ofwel breuken a , met in de teller en noemer een
geheel getal. Dat wil zeggen: Q = { a | a, b ∈ Z}.
In tegenstelling tot Z heeft een element in Q geen opvolger. Voor ieder paar a, b ∈ Q
ligt er immers nog een breuk tussen a en b, bijvoorbeeld a+b . Er zitten dus geen ‘gaten
met positieve lengte’ in de rationale getallenlijn.
In hoofdstuk 4 zullen we Q formeel construeren en bewijzen dat het een lichaam is.
2.5.4 R, de Re¨ele getallen
R is de verzameling re¨ele getallen, dat zijn alle getallen op de getallenlijn. R komt overeen met de verzameling van alle naar links eindig en naar rechts oneindig doorlopende decimale breuken in een willekeurig grondtal g ∈ N≥2 . Bijvoorbeeld 1.01100111000 . . . in grondtal 2, en 105π = 314159.2 . . . in grondtal 10 zijn re¨ele getallen. Formeler:
∀g ∈ N≥2 :
i=k
R = n X ai gi k ∈ Z, ∀i ∈ Z : (ai ∈ N, 0 ≤ ai ≤ g − 1)o
−∞
Een reden om N uit te breiden naar Z en Q is omdat er zo een ‘mooiere’ algebra¨ısche structuur ontstaat die aan meer axioma’s voldoet. Met Q is de mooiste structuur die we kennen (het lichaam) bereikt, dus we moeten andere redenen hebben om deze nog eens uit te breiden naar R en C.
We hebben eerder beweerd dat er geen ‘gaten’ in de rationale getallenlijn zitten: elk getal op de getallenlijn kan oneindig dicht benaderd worden door rationale getallen. Maar voor veel toepassingen, bijvoorbeeld in de analyse, blijkt benaderen niet goed genoeg te zijn. Daar is het namelijk belangrijk dat je limieten kunt nemen. Bovendien blijken
belangrijke re¨ele getallen zoals √2, e en π niet rationaal te zijn.
2.5.5 C, de Complexe getallen
De verzameling complexe getallen kan worden geschreven als C = {a + bi | a, b ∈ R}. De constante i is een zogenaamd imaginair getal. Per definitie is i2 = −1. Blijkbaar is i geen re¨eel getal, want in R zijn kwadraten altijd positief. Met i mag wel gerekend worden alsof het een re¨eel getal is.
De belangrijkste reden om C in te voeren is omdat zo een algebra¨ısch gesloten getal- systeem ontstaat. Dat wil zeggen dat er voor elke functie f van de vorm
f (x) = a0x0 + a1x1 + a2x2 + . . . + an xn (ai ∈ C, n ∈ N )
een x ∈ C is zodat f (x) = 0. Zo’n x heet een nulpunt van f (x). Dat R niet algebra¨ısch gesloten is, is gemakkelijk in te zien: bijvoorbeeld f (x) = x2 + 3 heeft geen nulpunt in
R. In C is bijvoorbeeld i√3 een nulpunt van deze functie.
Dat C algebra¨ısch gesloten is, bewijzen we hier niet. In hoofdstuk 8 van [5] staat een bewijs dat ook voor 6VWO-leerlingen te begrijpen is.
2.5.6 Zp en Qp , de p-adische gehele en gebroken getallen
Wat Zp en Qp intu¨ıtief inhouden hebben we uitgebreid besproken. In hoofdstuk 3 en 4 zullen we ze formeel defini¨eren.
In hoofdstuk 3 zullen we bewijzen dat Zg , voor elk geheel grondtal g ≥ 2, een
commutatieve ring met 1 is, en bovendien zonder nuldelers als g priem is. In hoofdstuk
4 bewijzen we dat Qp voor elk priemgetal p een lichaam is. Dan blijkt dat we Qp op een
heel andere manier invoeren dan je misschien verwacht, namelijk als breuken a
met in
de teller en noemer p-adische gehele getallen.
n a o
∀p ∈ P : Qp = b
a, b ∈ Zp , b = 0
Hier is P de verzameling priemgetallen. Uiteindelijk bewijzen we dat alle elementen van
Qp geschreven kunnen worden als p-adische kommagetallen van de vorm
. . . a3a2a1a0 .a−1a−2 . . . a−n
Bij deze schrijfwijze kunnen we ons tenminste iets voorstellen, en bovendien kunnen we op deze manier gemakkelijk met de getallen rekenen.
Hoofdstuk 3 Precieze invoering van de ring Zg
3.1 Voorbereiding
In dit hoofdstuk voeren we Zg formeel in, waarna we bewijzen dat het een commutatieve ring met 1 is, en bovendien zonder nuldelers als g priem is. Voordat we dat doen, willen we eerste intu¨ıtief inzien waarom dit zo is. Dat doen we in deze paragraaf. Let op: alle
‘bewijzen’ hier zijn nog informeel en niet strikt volgens wiskundige regels.
Een g-adisch geheel getal
betekent intu¨ıtief hetzelfde als
. . . a3a2a1 a0
. . . + a3g3 + a2g2 + a1g1 + a0g0 (3.1)
Dit korten we voortaan af als1
∞
X ai gi (3.2)
i=0
In §1.2 hebben we gezien dat twee g-adische getallen cijfer voor cijfer opgeteld worden, dus
∞ ∞ ∞
X ai gi + X bi gi = X(ai + bi )gi (3.3)
i=0
i=0
i=0
Hier stuiten we echter op een probleem: de nieuwe cijfers ai + bi kunnen groter zijn dan g − 1. We kunnen nu naar links ‘overlenen’ om er een echt g-adisch getal van te maken, maar dan hebben we geen simpele formule voor optelling meer. Het hangt immers van de specifieke waarden van alle ai en bi af of er overgeleend moet worden, en ook van alle vorige keren dat is overgeleend. Daarom nemen we voorlopig maar voor lief dat sommige cijfers te groot zijn.
1 P is het zogenaamde sommatie-teken. Lees formule (3.2) als: de som van alle termen ai gi waarbij
de index i alle gehele getallen van 0 tot ∞ doorloopt.
Het is nu makkelijk in te zien dat de optelling commutatief is. Alle ai en bi zijn namelijk natuurlijke getallen waarvoor de commutativiteit geldt, dus
∞ ∞ ∞
∞ ∞ ∞
X ai gi + X bi gi = X(ai + bi )gi = X(bi + ai )gi = X bi gi + X ai gi
i=0
i=0
i=0
i=0
i=0
i=0
Voor het gemak noteren we P∞
ai gi voortaan als [ai ], analoog hieraan schrijven we
[bi ] en [ci ]. Zo stelt bijvoorbeeld [0] een oneindige rij nullen voor.
Ook de associativiteit van de optelling is gemakkelijk in te zien.
[ai ] + [bi ] + [ci ] = [ai + bi ] + [ci ] = (ai + bi ) + ci
= ai + (bi + ci ) = [ai ] + [bi + ci ] = [ai ] + [bi ] + [ci ]
Het bestaan van een nulelement is n´og eenvoudiger aan te tonen; immers, [ai ] + [0] = [ai + 0] = [ai ]
en wegens de commutativiteit van + is ook [0] + [ai ] = [ai ].
Om te bewijzen dat ieder getal een tegengestelde heeft, moeten we wat meer moeite doen. We willen dat de tegengestelde van een ´echt g-adisch getal [ai ] (d.w.z. met cijfers
tussen 0 en g − 1) een ´echt g-adisch getal is. We kunnen daarom niet gewoon [−ai ]
nemen.
Oefening 3.1.1. Op pagina 6 hebben we van een g-adisch getal de tegengestelde be- rekend door het van 0 af te trekken. Wat is volgens deze methode in het algemeen de tegengestelde van . . . a3a2a1a0 ?
We vermoeden dus dat [bi ] de tegengestelde is van [ai ], waarbij b0 = g−a0 en bi = g−ai −1 voor de overige i. Als we [ai ] + [bi ] berekenen komt er [ci ] uit, met c0 = g en ci = g − 1 voor i > 0. Op het eerste gezicht lijkt dit niet veel op 0, maar we kunnen bewijzen dat wel degelijk [ci ] = 0. Hiervoor gebruiken we schrijfwijze (3.1) voor [ci ].
[ci ] = . . . + (g − 1)g3 + (g − 1)g2 + (g − 1)g1 + (g)g0
= . . . + g4 − g3 + g3 − g2 + g2 − g1 + g1
= . . . + 0 + 0 + 0 + 0 = 0
Gaan we vermenigvuldiging erbij betrekken, dan wordt de zaak ingewikkelder. Uit het voorbeeld van pagina 7 blijkt dat hoe verder een cijfer van het product naar links staat, hoe meer getallen bij elkaar opgeteld moesten worden om dit cijfer te verkrijgen. We willen een algemene formule vinden voor ci in het product [ai ] × [bi ] = [ci ]. Hiervoor schrijven we [ai ] en [bi ] weer zoals in vgl. (3.1).
[ci ] = (. . . a3g3 + a2g2 + a1g1 + a0g0) × (. . . b3g3 + b2g2 + b1g1 + b0g0)
Als we deze vermenigvuldiging term voor term uitvoeren, krijgen we een som van aj bk gj+k voor alle mogelijke combinaties van j en k (ga dat na). Deze term hoort wegens de factor gj+k bij het cijfer cj+k . Op deze manier kunnen we inzien dat bijvoorbeeld
5
c5 = a0 b5 + a1b4 + a2b3 + . . . + a5 b0 = X ak b5−k
k=0
Dit is de som van alle aj bk waarvoor j + k = 5. Voor andere cijfers ci gaat het analoog. We concluderen:
[ai ] × [bi ] =
i
h X
k=0
i
ak bi−k
(3.4)
Deze formule is heel wat lastiger dan formule (3.3) voor de optelling! De bewijzen van de rekenregels van vermenigvuldiging zijn dan ook een stuk lastiger. Dat van de commutativiteit is nog wel te overzien; het komt er op neer dat je moet bewijzen dat
a0bi + a1bi−1 + . . . + ai b0 = b0ai + b1ai−1 + . . . + bi a0
Dat is een kwestie van de som in omgekeerde volgorde schrijven en vervolgens alle pro- ducten omdraaien.
Oefening 3.1.2. Ga na dat uit formule (3.4) volgt dat [ei ] het eenheidselement van Zg is, waarbij e0 = 1 en ei = 0 voor de overige i. Dat wil zeggen: bewijs dat [ei ] × [bi ] = [bi ] voor alle [bi ].2
Het bewijs van de associativiteit voor × is een stuk lastiger, omdat daar drie elementen met elkaar vermenigvuldigd worden. Dit laten we daarom voorlopig achterwege, net als het bewijs van de distributiviteit.
3.1.1 Bezwaren tegen de P methode
We hebben nu twee nadelen gezien van het schrijven van g-adische gehele getallen als een oneindige som. Ten eerste zijn de eigenschappen van vermenigvuldiging vrij moeilijk te bewijzen, zeker als je dat strikt volgens de regels van algebra¨ısche structuren wilt doen.
Ten tweede kunnen cijfers groter zijn dan g − 1.
Wat misschien nog wel een belangrijker bezwaar is, is dat het niet wiskundig correct is om zomaar een oneindige som te nemen en daarmee te gaan rekenen zoals in (3.3) en (3.4). We zouden eerst moeten bewijzen dat deze sommen convergeren, en vervolgens dat (3.3) en (3.4) waar zijn. Daar hebben we te weinig voorkennis voor, daarom pakken we het anders aan. We defini¨eren g-adische getallen als abstracte rijtjes van ‘cijfers’, die op zichzelf niets voorstellen. Optelling en vermenigvuldiging worden vastgelegd met algoritmen (rekenvoorschriften). Het rekenvoorschrift voor optelling bijvoorbeeld doet
2 Dat ook [bi ] × [ei ] = [bi ] hoef je niet te bewijzen, want dat volgt direct uit de commutativiteit van vermenigvuldiging in Zg .
eigenlijk niets anders dan stap voor stap ‘onder elkaar staande’ cijfers optellen, zoals we ook in §1.2 hebben gedaan. Het verschil is dat we eerst het overlenen laten zitten, we staan cijfers groter dan g − 1 en kleiner dan 0 toe. Vervolgens laten we hier een algoritme op los dat kan overlenen, zodat een echt g-adisch getal ontstaat.
De verzameling van alle g-adisch-achtige getallen waar alle gehele getallen als cijfers zijn toegestaan, noemen we Z∗. We zullen bewijzen dat dit een commutatieve ring met
1 is. Vervolgens beelden we de elementen van Z∗ met het overleen-algoritme af naar Zg , en beredeneren dat Zg ook een commutatieve ring met 1 moet zijn. Daarna laten we zien dan Zg geen nuldelers heeft als g priem is, en kijken we waneer delen mogelijk is binnen Zg . Als toetje geven we uitleg bij een algoritme dat kan delen in Zp .
3.2 Formele definitie van Z∗ en Zg
We zullen Z∗ en Zg nu formeel defini¨eren. Met (ai ) : i ∈ N bedoelen we een geordende
rij van de vorm (a0, a1 , a2 , a3, • • • ). Deze rij is een abstract ding: voordat we er de
operaties optellen en vermenigvuldigen op gedefinieerd hebben, heeft de rij strikt gezien geen enkele betekenis. Toch houden we in ons achterhoofd wat we eigenlijk bedoelen met zo’n rij, namelijk een g-adisch geheel getal van de vorm
. . . a3a2a1a0
Zo wordt het veel gemakkelijker om intu¨ıtief in te zien wat in de bewijzen nou eigenlijk gedaan wordt. We zullen in de rest van dit hoofdstuk (ai ) vaak afkorten tot a, analoog voor andere letters dan a. Als iets anders bedoeld wordt met zo’n letter, wordt dat expliciet vermeld.
Definitie 3.2.1. We defini¨eren de verzameling Z∗ als volgt.
∀g ∈ N≥2 : Z∗ := {(ai ) | i ∈ N, ai ∈ Z}
Optelling en vermenigvuldiging in Z∗ zijn zo gedefini¨eerd als in algoritme 1 resp. 2, zie
§3.3.1 en §3.3.2. Dat wil zeggen: ∀a, b ∈ Z∗ is
a + b = add(a, b) en a × b = mult(a, b)
Definitie 3.2.2. Zg is de deelverzameling van Z∗
waarvoor alle ai tussen 0 en g − 1
liggen.
∀g ∈ N≥2 : Zg := {(ai ) | i ∈ N, ai ∈ Z, 0 ≤ ai ≤ g − 1}
Hoewel dit een deelverzameling van Z∗
is, zijn optelling en vermenigvuldiging anders
gedefinieerd.3 Nadat algoritme 1 of 2 is toegepast, laten we op de uitkomst namelijk ook nog algoritme 3 los, zie §3.4. Dat wil zeggen: ∀a, b ∈ Zg is
a + b = norm add(a, b) en a × b = norm mult(a, b)
3 Strikt gezien zijn het dan ook andere operaties.
3.3. ALGORITMES VOOR Z∗
3.3 Algoritmes voor Z∗
We hebben de bewerkingen in Zg en Z∗ dus gedefini¨eerd met algoritmen.4 Het is alsof je
een hypersnelle computer programmeert die bij twee oneindige rijtjes een nieuw oneindig rijtje oplevert. Natuurlijk bestaan zulke computers alleen in gedachten.
Hoewel onze hersenen niet als een computer werken, kunnen we toch inzien hoe zo’n algoritme werkt, en daarmee kunnen we bepaalde rekenregels bewijzen.
3.3.1 Optelling
Algorithm 1 Add
1: function add(a, b ∈ Z∗) ∈ Z∗
g g
2: c ∈ Z∗
3: begin
4: for i := 0 to ∞ do
5: ci := ai + bi
6: result := c
7: end
Met algoritme 1 kan de som c van twee elementen a en b uit Z∗ worden berekend.
Bij dit eerste algoritme zullen we uitleggen hoe je het kunt lezen.
Regel 1 vertelt de computer dat de functie die tussen begin en end staat afgekort wordt als add(a, b). De functie heeft als domein Z∗ en als bereik ook Z∗. Op regel 2
g g
wordt c in het geheugen van de computer geschreven, met de informatie dat c element van Z∗ is. Dat heeft een computer nou eenmaal nodig, anders zou hij niet weten wat hij
met regel 6 aanmoest.
Bij de regels 4 t/m 6 wordt de daadwerkelijke berekening uitgevoerd. Hierbij moeten we vermelden dat a gelijk is aan (a0, a1, a2, • • • ), analoog zijn ook b en c zulke rijtjes.5 De for-lus in regel 4 vertelt dat het volgende gedeelte moet worden uitgevoerd voor i = 0 tot i = ∞. In regel 5 worden de afzonderlijke elementen (de ‘cijfers’) van (ai ) en (bi ) bij elkaar opgeteld; het resultaat (ci ) wordt in regel 6 opgeslagen als c.
Wat het algoritme doet kan worden samengevat als
(ai ) + (bi ) = (ai + bi ) (3.5)
zoals je gemakkelijk kunt nagaan. De inwendigheid van + in Z∗ is wel duidelijk, optelling is immers ook inwendig in Z (bedenk dat ai , bi ∈ Z). Ook de associativiteit van optelling is makkelijk te bewijzen.
(ai ) + (bi ) + (ci ) = (ai + bi ) + (ci ) = (ai + bi ) + ci
= ai + (bi + ci ) = (ai ) + (bi + ci ) = (ai ) + (bi ) + (ci )
4 De taal waarin de algoritmen geschreven zijn is afgeleid van Pascal.
5 Natuurlijk moet de computer dat ook weten, maar voor de overzichtelijkheid hebben we dit uit het algoritme weggelaten.
Maar dit bewijs lijkt wel heel veel op dat van pagina 22! Het enige verschil is dat de vierkante haakjes [ ] vervangen zijn door ronde haakjes ( ), maar dat is slechts een kwestie van notatie. En natuurlijk is de interpretatie van het bewijs anders, [ai ] stelde immers een oneindige som voor terwijl (ai ) ‘slechts’ een abstracte rij getallen is. Dat maakt algebra¨ısch echter niet uit, de manier van bewijzen blijft hetzelfde. Verder is hier
ai ∈ Z, terwijl we in de voorbereiding met ai ∈ N werkten. Ook dat is niet erg, want in
Z gelden alle samenstellingswetten van N ook.
Voor de bewijzen van de andere samenstellingswetten voor optelling in Z∗ gaat dit ook op. Dat komt doordat de optelling op pagina 21 hetzelfde is ‘gedefinieerd’ als hier, namelijk als [ai ] + [bi ] = [ai + bi ]. Daarmee zijn de commutativiteit en de associativiteit van +, het bestaan van een nulelement, en het bestaan van een tegengestelde voor elk element bewezen; dit hebben we immers allemaal in §3.1 gedaan. Voor de tegengestelde van (ai ) mogen we nu zelfs (−ai ) nemen, omdat we met ai ∈ Z werken.
3.3.2 Vermenigvuldiging
Algorithm 2 Mult
1: function mult(a, b ∈ Z∗) ∈ Z∗
g g
2: c ∈ Z∗
3: begin
4: c := (0, 0, 0, • • • )
5: for i := 0 to ∞ do
6: begin
7: for z := 0 to i do
8: ci := ci + az • bi−z
9: end
10: result := c
11: end
Ook algoritme 2 komt op hetzelfde neer als de formule voor vermenigvuldiging zoals we die in §3.1 hebben afgeleid, namelijk vgl. (3.4). Dit zullen we beredeneren nadat we wat uitleg bij het algoritme hebben gegeven.
In regel 4 wordt c opgeslagen als een rij nullen: we beginnen met een schone lei. In regel 5 begint een oneindige lus, die op zijn beurt een eindige lus bevat, namelijk die van regel 7. Regel 8 ziet er wat vreemd uit, je zou zeggen dat dit alleen kan als az • bi−z = 0. Dat hoeft echter niet, want in computertaal betekent ci := ci + az • bi−z iets anders dan in de wiskunde. De rechter ci is het getal dat al in het geheugen van de computer stond (in het begin dus 0), die wordt vervangen door de linker ci . Eigenlijk betekent regel 8 dus: tel az • bi−z op bij ci .
Wat wordt hier nu eigenlijk gedaan? We berekenen (ai ) • (bi ) = (ci ). Elk ‘cijfer’ ci wordt samengesteld uit de som van alle az • bi−z waarvoor 0 ≤ z ≤ i. Dat wil zeggen:
(ai ) • (bi ) =
i
X
z=0
az bi−z
(3.6)
en dat is precies dezelfde formule als (3.4).6 Omdat we in §3.1 de commutativiteit van
× en het bestaan van een eenheidselement hebben bewezen, zijn we daar klaar mee. De inwendigheid is duidelijk. Blijft over de associativiteit en de distributiviteit.7
Stelling 3.3.1. De vermenigvuldiging is associatief in Z∗.
Bewijs. We willen bewijzen dat (ab)c = a(bc) voor alle a, b, c ∈ Z∗. Hiervoor voegen we twee mult-algoritmes8 samen tot ´e´en. Het begin en eind van het algoritme dat alleen voor de computer van belang is laten we voor het gemak weg. De uitkomst van a • b noemen we q; vervolgens berekenen we de uitkomst k = q • c van het algoritme. Het algoritme berekent dus (ab)c.
for i := 0 to ∞ do begin
for z := 0 to i do
qi := qi + az • bi−z ; (a) {Hier wordt q = a • b berekend zoals in algoritme 2.}
for z := 0 to i do
ki := ki + qz • ci−z ; (b) {Hier wordt k = qc = (ab)c berekend.}
end
In for-lus (b) is qz gelijk aan de bij (a) berekende som van i termen, dus we kunnen het algoritme als volgt korter opschrijven.
for i := 0 to ∞ do begin
for y := 0 to i do
for z := 0 to i − y do
ki := ki + az • bi−y−z • cy {Let op: z vervult hier een andere functie dan in for-lus (a).}
end
Hier wordt elk ‘cijfer’ ki berekend als de som van alle ap bq cr waarvoor p + q + r = i. Immers, z + (i − y − z) + y = i, en omdat z, i − y − z en y niet kleiner dan nul mogen zijn is het voldoende om y van 0 tot i te laten lopen en z van 0 tot i − y. Omdat dit een eindige som is in Z, doet de volgorde van de optelling er niet toe. Zolang we maar alle
6 Dat k vervangen is door z en [ ] door ( ) is slechts een kwestie van notatie.
7 Het bestaan van een invers element is een geval apart, dit komt in een andere paragraaf aan de orde.
8 d.i. algoritme 2 combinaties van ap bq cr waarvoor p + q + r = i een keer optellen bij ki , komt er dezelfde
k uit. We kunnen het algoritme dus ook als volgt schrijven.
for i := 0 to ∞ do begin
for y := 0 to i do
for z := 0 to i − y do
ki := ki + ay • bz • ci−y−z
end
Wegens de commutativiteit van vermenigvuldiging in Z mogen we in het laatste algoritme ook schrijven: ki := ki + bz • ci−y−z • ay . Als we dat doen, hebben we precies het tweede algoritme van dit bewijs teruggekregen, alleen nu met a, b en c omgewisseld. De uitkomst van dit algoritme is dus gelijk aan (bc)a en dat is a(bc). Maar we begonnen met een algoritme dat (ab)c berekende, en omdat de algoritmes steeds zo zijn omgeschreven dat de uitkomst gelijk blijft, mogen we concluderen dat (ab)c = a(bc).
Nu bewijzen we de distributiviteit.
Stelling 3.3.2. De vermenigvuldiging is distributief over optelling in Z∗.
Bewijs. We willen bewijzen dat a(b + c) = ab + ac en dat (a + b)c = ac + bc voor alle a, b, c ∈ Z∗. Hiervoor voegen we weer twee functies samen, dit keer de add-functie en de mult-functie (algoritme 1 en 2). Dit samengestelde algoritme berekent, zoals je gemakkelijk kunt nagaan, a(b + c).
for i := 0 to ∞ do begin
qi := bi + ci ; (a) {Hier wordt q = add(b, c) berekend.}
for z := 0 to i do
ki := ki + az • qi−z ; (b) {Hier wordt k = mult(a, q) berekend.}
end
Volgens (a) is qi = bi + ci , dus (b) kunnen we schrijven als ki := ki + az (bi−z + ci−z ), en dat is wegens de distributiviteit in Z gelijk aan ki + az bi−z + az ci−z . We kunnen dit algoritme dus schrijven als
for i := 0 to ∞ do begin
for z := 0 to i do
ki + az bi−z + az ci−z (a)
end
We kunnen (a) in twee¨en splitsen, zodat we het volgende algoritme krijgen:
for i := 0 to ∞ do for z := 0 to i do
begin
ki := ki + az • bi−z ; (a)
ki := ki + az • ci−z ;
end
In dit laatste algoritme kunnen we (a) als het ware buiten haakjes halen door deze berekening als eerst uit te voeren. De uitkomst noemen we q; die tellen we aan het eind bij ki op. Ga voor jezelf na dat het volgende algoritme echt dezelfde uitkomst zal geven als het vorige.
for i := 0 to ∞ do begin
for z := 0 to i do
qi := qi + az • bi−z ; (a)
for z := 0 to i do
ki := ki + az • ci−z ; (b)
ki := qi + ki ; (c)
end
Bij (a) wordt ab berekend, bij (b) wordt ac berekend, en bij (c) worden de uitkomsten daarvan bij elkaar opgeteld. De uitkomst k van het algoritme is dus gelijk aan ab + ac, en omdat het algoritme waarmee we begonnen a(b + c) berekende, hebben we bewezen dat a(b + c) = ab + ac, dat is de links-distributiviteit. Omdat de commutativiteit van × al is bewezen, geldt volgens stelling 2.4.2 ook de rechts-distributiviteit. Hiermee stelling
3.3.2 bewezen.
We hebben in deze paragraaf bewezen dat voor Z∗ de volgende samenstellingswetten uit Tabel 2.2 gelden. Voor + gelden 1), 2), 3), 4) en 5); voor × gelden 1), 2), 3) en 5); verder geldt ook 6). Met Tabel 2.4 volgt hieruit dat Z∗ een commutatieve ring met 1 is.
3.4 Normalisatie
We hebben nu bewezen dat Z∗ een ring vormt, maar dat willen we uiteindelijk natuurlijk bewijzen voor Zg . Om dit te bereiken komen we terug op het idee dat een element a van Zg te schrijven is als een oneindige som van de vorm
∞
a = X ai gi , ai ∈ Z (3.7)
i=0
Algorithm 3 Norm
1: function norm(a ∈ Z∗) ∈ Zg
2: d−1
:= 0 {Dit is nodig omdat de computer anders bij 6 in de knoop komt.}
3: begin
4: for i := 0 to ∞ do
5: begin
6: ai := ai + di−1 {Hier wordt als het ware overgeleend van ai−1.}
7: di := ai div g {a div b geeft het quoti¨ent bij de restdeling a .}
8: ai := ai − g • di {Dit is de rest bij die deling.}
9: end
10: result := a
11: end
Nu gaan we de volgende zeer fundamentele stelling gebruiken. Voor een bewijs verwijzen we naar §2.2 van [1].
Stelling 3.4.1. (Deling met rest) Stel a, b ∈ Z en b > 0. Dan zijn er gehele getallen
q en r z´o dat
a = bq + r, 0 ≤ r < b
We noemen q het quoti¨ent en r de rest van de restdeling a . De stelling zegt dus niets anders dan dat deze restdeling altijd kan worden uitgevoerd (mits b = 0), waarbij een positieve rest kleiner dan b ontstaat.
We kunnen volgens stelling 3.4.1 restdeling van de ‘cijfers’ ai van a (zie formule 3.7)
door g uitvoeren. Het quoti¨ent noemen we di en de rest ci . We krijgen:
ai gi = (di g + ci )gi = di gi+1 + ci gi , 0 ≤ ci < g
ci wordt het nieuwe cijfer van a op positie i; we tellen di wegens de factor gi+1 op bij het cijfer op positie i + 1, dit wordt de nieuwe ai+1 . Nu kunnen we restdeling op ai+1 toepassen, hierbij blijft ci onveranderd. Als we op deze manier vanaf a0 restdeling toepassen, krijgen we
∞ ∞
a = X ai gi = X ci gi , ci ∈ Z, 0 ≤ ci < g.
i=0
i=0
We hebben een getal a ∈ Z∗ omgevormd tot een een getal uit Zg ; immers, de cijfers ci liggen tussen 0 en g − 1. Dit is precies wat algoritme 3 (zie pagina 30) doet, het komt eigenlijk op hetzelfde neer als het ‘overlenen’ zoals we in §1.2 hebben gedaan.
Met algoritme 3 kunnen we Z∗ afbeelden naar Zg . We zullen in deze paragraaf de
volgende stelling bewijzen.
Stelling 3.4.2. Voor alle g ∈ N≥2 is Zg een commutatieve ring met 1.
Allereerst voeren we een notatie in.
Definitie 3.4.3. Voor alle (ai ) ∈ Z∗ defini¨eren we voor alle i > 0:
a0 0
i := ai−1 en a0 := 0
Verder duiden we (a0 ) aan met (ai )0 ofwel a0.
Het is intu¨ıtief duidelijk dat a0 overeenkomt met g × a. Alle cijfers van a schuiven immers
´e´en positie naar links op, en de lege plek wordt opgevuld met een 0. Deze bewering zullen we in het volgende hoofdstuk nodig hebben, daarom geven we een bewijs. In plaats van g schrijven we y = . . . 00010 ofwel (0, 1, 0, 0, 0, • • • ); het is duidelijk dat y = norm(g).
Stelling 3.4.4. De afbeelding a 7→ a0 in Zg komt overeen met vermenigvuldiging van a
met (yi ) = (0, 1, 0, 0, 0, • • • ). Informeel komt deze stelling neer op a0 = a × g.
Bewijs. We hebben eerder gezien dat de mult-functie van algoritme 2 dezelfde uitkomst geeft als formule (3.6) op pagina 27. In deze formule vullen we voor b het getal (yi ) in, zo krijgen we de volgende formule voor (ai ) × (yi ).
i
X az yi
z=0
(3.8)
Als z = i − 1 is yi−z = y1 = 1, dan is az yi−z dus gelijk aan ai−1 × 1 = ai−1. Voor de overige z is yi−z = y1 , dan is yz = 0. We concluderen dat de uitkomst van (3.8) alleen
9 0 0
bepaald wordt door z = i − 1, dus de uitkomst is (ai−1 ),
is bewezen dat a0 = a × (yi ).
ofwel (ai ), ofwel (ai ) . Hiermee
Om stelling 3.4.2 te bewijzen, hebben we eerst een paar lemma’s (hulpstellingen) nodig.
3.4.1 Lemma’s
Lemma 3.4.5. Voor alle a ∈ Z∗ is er een d ∈ Z∗ zodat norm(a) = a + d0 − gd, waarbij
g g
bovendien di = ai + di−1 div g voor alle i ≥ 0.
Bewijs. Beschouw algoritme 3. In regel 6 wordt di−1 bij ai opgeteld; in regel 8 wordt vervolgens g maal de in regel 7 berekende waarde van di , van ai afgetrokken. Dit betekent dat het genormaliseerde cijfer ai gelijk is aan ai +di−1 −gdi , en omdat bovendien d−1 := 0 is dat gelijk aan ai + d0 − gdi . We concluderen dat norm(a) = (ai + d0 − gdi ), en met
i i
behulp van vgl. (3.5) volgt hieruit dat
norm(a) = (ai + d0 + −gdi ) = (ai ) + (d0 ) + (−gdi ) = a + d0 − gd
i i
Bovendien blijkt uit regel 6 en 7 dat di = ai + di−1 div g.
9 en het eerste cijfer is a0 y0 = 0
Lemma 3.4.6.
∀b, e ∈ Z∗ : norm(b) = norm(b + e0 − ge)
Bewijs. Volgens lemma 3.4.5 is er een z ∈ Z∗ zodat
norm(b) = b + z0 − gz (3.9)
zi = bi + zi−1 div g (3.10) We gaan norm(b + e0 − ge) voor een willekeurige e ∈ Z∗ berekenen, en willen bewijzen
dat dat dit gelijk is aan norm(b). We doorlopen de norm-functie voor a = b + e0
− ge.
Eerst bereken we het nulde cijfer a0
. In regel 6 van algoritme 3 gebeurt er nog niets van
belang, want d−1 = 0. Regel 7 geeft vervolgens:
d0 = a0 div g = b0 + e0 − ge0 div g = b0 − ge0 div g = −e0 + (b0 div g)
= −e0 + (b0 + z−1 div g) Regel 8 berekent:
(3.10)
= −e0 + z0 (3.11)
a0 := a0 − gd0 = (b0 + e0 − ge0) − g(−e0 + z0 ) = b0 − ge0 + ge0 − gz0 = b0 − gz0
en dat is volgens vgl. (3.9) gelijk aan het nulde cijfer van norm(b), want z0 = 0.
Nu kijken we naar het algemene geval. Stel dat we voor een zekere i > 0 weten dat
di−1 = −ei−1 + zi−1 (3.12)
Regel 6 geeft dan
Regel 7 berekent
ai := ai + di−1 = (bi + e0 − gei ) + (−ei−1 + zi−1)
= bi + ei−1 − gei − ei−1 + zi−1 = bi − gei + zi−1 (3.13)
di := ai div g
(3.13)
= (bi − gei + zi−1) div g
(3.10)
= − ei + (bi + zi−1) div g
Regel 8 geeft vervolgens:
= −ei + zi (3.14)
ai := ai − gdi
(3.13)
= (bi − gei + zi−1) − gdi
(3.14)
= (bi − gei + zi−1) − g(−ei + zi )
= bi − gei + gei + zi−1 − gzi = bi + z0 − gzi
en dat is volgens vgl. (3.9) precies gelijk aan het i-de cijfer van norm(b). Bovendien blijkt uit (3.14) dat opnieuw de gelijkheid in (3.12) geldt, alleen nu met i eentje opgehoogd. We kunnen het hele verhaal dus opnieuw toepassen voor i + 1, dan voor i + 2, etc; telkens blijkt dat ai , het i-de cijfer van norm(b + e0 − ge), gelijk is aan het i-de cijfer van norm(b). Volgens (3.11) mogen we de redenering beginnen bij i = 1.10 Bovendien zagen we eerder al dat ook de nulde cijfers aan elkaar gelijk zijn. We concluderen dat alle cijfers van norm(b + e0 − ge) en norm(b) overeenkomen, waarmee de stelling bewezen is.
10 Bedenk dat er i − 1 staat bij vgl. (3.12).
Lemma 3.4.7.
∀a, b ∈ Z∗ : a0 + b0 = (a + b)0
Bewijs. In formule (3.5) hebben we gezien dat (ai ) + (bi ) = (ai + bi ). Als we het i-de cijfer van (ai ) + (bi ) voor het gemak (a + b)i noemen, volgt hieruit dat (a + b)i = ai + bi . Nu zien we dat voor alle i > 0 geldt:
(a + b)0 = (a + b)i−1 = ai−1 + bi−1 = a0 + b0 = (a0 + b0)i
i i i
Nu moeten we de stelling alleen nog maar bewijzen voor i = 0. Dat is zo gedaan:
(a + b)0
= 0 = 0 + 0 = a0 + b0
= (a0 + b0)0
0 0 0
Hiermee is bewezen dat (a + b)0 = (a0 + b0)i voor alle i, dus alle cijfers van (a + b)0 en a0 + b0 komen met elkaar overeen, deze getallen zijn dus gelijk. Hiermee is de stelling bewezen.
Lemma 3.4.8.
∀a, b ∈ Z∗ : a0 × b = (a × b)0
Bewijs. Volgens formule (3.6) geldt voor de cijfers ai en bi van de getallen (ai ) en (bi ):
i
ai × bi = X az bi−z
z=0
Hieruit volgt dat voor alle i > 0:11
i−1 i i
(ab)0 = (ab)i−1 = X az bi−1−z = X ak−1bi−k = X a0 bi−k = (a0b)i
i
z=0
k=1
k
k=1
We kunnen gemakkelijk aantonen dat bovenstaande gelijkheid ook geldt voor i = 0.
(ab)0
0
= 0 = 0 × b0 = a0 b0 = X a0 b0 = (a0b)0
0 0 0
z=0
Conclusie: voor alle i is (ab)0
= (a0b)i , dus de getallen (ab)0 en (a0b) zijn aan elkaar
gelijk.
Lemma 3.4.9.
∀a, b ∈ Z∗ : norm norm(a) + b = norm(a + b)
Bewijs. Volgens lemma 3.4.5 kunnen we norm(a) schrijven als a + d0 − gd voor een zekere
d ∈ Z∗. Nu kunnen we afleiden:12
norm norm(a) + b = norm (a + d0 − gd) + b = norm((a + b) + d0 − gd) 3.=4.6 norm(a + b)
11 In de derde stap wordt k gesubstitueerd voor z + 1.
12 een nummer boven een =-tekens verwijst naar het lemma dat bij die stap gebruikt wordt.
Lemma 3.4.10.
∀a, b ∈ Z∗ : norm norm(a) • b = norm(a • b)
Bewijs. We kunnen norm(a) schrijven als a + d0 − gd voor een d ∈ Z∗.
norm norm(a) • b = norm (a + d0 − gd)b = norm(ab + d0b − gdb)
3.=4.8 norm ab + (db)0 − g(db) 3.=4.6 norm(ab)
3.4.2 Bewijs: Zg is een commutatieve ring met 1
Om stelling 3.4.2 te bewijzen, hebben we nog twee belangrijke maar eenvoudig te bewij- zen stellingen nodig.
Stelling 3.4.11.
∀a, b ∈ Z∗ : norm(a + b) = norm norm(a) + norm(b)
Bewijs. De eerste gelijkheid volgt met behulp van het feit dat norm(b) ∈ Z∗, de tweede
met de commutativiteit van optelling in Z∗.
norm norm(a) + norm(b) 3.=4.9 norm a + norm(b) 3.=4.9 norm(a + b)
Stelling 3.4.12.
∀a, b ∈ Z∗ : norm(a • b) = norm norm(a) • norm(b)
Bewijs. Dit gaat geheel analoog aan dat van de vorige stelling.
norm norm(a) • norm(b) 3.=4.10 norm a • norm(b) 3.=4.10 norm(a • b)
Nu hebben we genoeg gereedschap om te bewijzen dat Zg een commutatieve ring met 1 is.
Laat a, b, c elementen zijn van Zg . Omdat Zg ⊂ Z∗ is ook a, b, c ∈ Z∗, dus op a, b en
g g
c mogen we de regels van een commutatieve ring met 1 al toepassen.
De optelling en vermenigvuldiging in Zg zijn anders gedefini¨eerd dan in Z∗, zie de-
finitie 3.2.2 op pagina 24. Om onderscheid tussen de operaties te maken, duiden we optelling en vermenigvuldiging in Zg aan met ⊕ resp. ⊗, in Z∗ schrijven we gewoon +
en ×. Volgens definitie 3.2.2 geldt:
a ⊕ b = norm(a + b), a ⊗ b = norm(a × b).
Verder geldt voor alle z ∈ Zg natuurlijk dat
norm(z) = z (3.15) Immers, alle cijfers zi van z liggen tussen 0 en g − 1, dus in algoritme 3 geldt voor alle i
dat di = zi div g = 0. Hierdoor blijven alle zi onveranderd.
Als eerste bewijzen we de inwendigheid van ⊕ en ⊗ in Zg . Dat is zo gedaan. Immers,
a ⊕ b = norm(a + b), en omdat + inwendig is in Z∗, is dit de norm-functie toegepast
op een element van Z∗. Volgens definitie 3.2.2 is het resultaat weer een element van Zg . Voor vermenigvuldiging gaat het analoog: vervang overal ⊕ door ⊗ en + door ×, en je bent er.
Nu bewijzen we de commutativiteit van ⊕ en ⊗ in Zg . Ook dat is eenvoudig:
a ⊕ b = norm(a + b) = norm(b + a) = b ⊕ a
Voor vermenigvuldiging gaat het weer analoog.
Voor de associativiteit moeten we wat meer moeite doen, omdat we met drie ele- menten te maken hebben. Het bewijs voor ⊕ gaat als volgt.13 We korten norm af tot n.
a ⊕ (b ⊕ c) = a ⊕ n(b + c) = n a + n(b + c)
(3.15)
= n n(a) + n(b + c)
3.=4.11 n a + (b + c) = n (a + b) + c = n n(a + b) + n(c)
= n n(a + b) + c = n(a + b) ⊕ c = (a ⊕ b) ⊕ c
Het bestaan van een nulelement en een eenheidselement in Zg is gemakkelijk te bewijzen: het zijn dezelfde 0 en 1 als in Z∗. Voor ⊕ 0 hebben we het bewijs uitgewerkt,
voor ⊗
1 gaat het analoog.
a ⊕ 0 = n(a + 0) = n(a) = a
Omdat we de commutativiteit voor ⊕ en ⊗ al hebben bewezen, is ook 0 ⊕ a = a en
1 ⊗ a = a, waarmee is aangetoond dat 0 en 1 inderdaad de gezochte elementen zijn.
Het bestaan van een tegengestelde van elke (ai ) ∈ Zg is makkelijk aan te tonen, het is vergelijkbaar met de manier waarop we de tegengestelde op pagina 6 hebben berekend. De kleinste i waarvoor ai = 0 noemen we k. We nemen het getal (bi ) ∈ Zg waarbij bi = 0 voor alle i < k, bk = g − ak en bi = g − ai − 1 voor alle i > k. Ga na dat inderdaad (bi ) ∈ Zg . Algoritme 1 berekent:
(ai ) + (bi ) = (0, 0, • • • , 0, g, g − 1, g − 1, g − 1, • • • ) := (ci )
Nu berekenen we (ai ) ⊕ (bi ) = norm(ci ). Alle cijfers ci met i < k blijven natuurlijk 0. Dan wordt dk = g div g = 1 berekent, daarna ck = g − g • 1 = 0. Dan wordt dk bij ck+1 opgeteld zodat dit g wordt, deze wordt weer 0 waarbij weer 1 wordt overgeleend, etc. Zo wordt (ci ) = 0, dus (bi ) is de tegengestelde van (ai ).
13 Opnieuw gaat het voor ⊗ analoog, maar nu moet wel stelling 3.4.11 vervangen worden door 3.4.12.
Het bestaan van een inverse bespreken we in de volgende paragraaf, evenals het (niet)
bestaan van nuldelers.
Tot slot bewijzen we de distributiviteit.
a ⊗ (b ⊕ c) = a ⊗ n(b + c) = n a • n(b + c) 3.=4.10 n a(b + c)
= n(ab + ac) 3.=4.12 n n(ab) + n(ac) = n(a ⊗ b + a ⊗ c) = a ⊗ b ⊕ a ⊗ c
Nu hebben we de eigenschappen 1), 2), 3), 4) en 5) voor optelling bewezen, zie Tabel 2.2. We hebben 1), 2), 3) en 5) voor vermenigvuldiging en bovendien 6) bewezen. Volgens Tabel 2.4 is hiermee stelling 3.4.2 bewezen: Zg is een commutatieve ring met 1.
In het vervolg werken we vooral met Zg . Daarom schrijven we gewoon weer + en ×
in plaats van ⊕ en ⊗, tenzij anders vermeld.
3.5 Deelbaarheid in Zg
Wanneer is delen mogelijk in Zg ? En in welke gevallen zijn er nuldelers? Daarover gaat deze paragraaf.
3.5.1 Nuldelers
Laten we met die laatste vraag beginnen. Zoals al eerder is gezegd, zijn nuldelers getallen a, b ongelijk aan 0 waarvoor a × b = 0. In de getalsystemen waarmee we bekend zijn bestaan geen nuldelers, maar we zullen laten zien dat deze er in Zg w´el zijn voor bepaalde grondtallen g.
Hiervoor hebben we eerst wat basiskennis nodig over modulorekenen14 , ook wel klok- rekenen genoemd. Iedereen leert als kind rekenen met de klok van twaalf. Als het nu 8 uur is, is het 7 uur later natuurlijk 3 uur. Dit noteren15 we als 8 + 7 = 15 ≡ 3 (mod 12). In het algemeen is a ≡ b (mod g) precies dan als a en b dezelfde rest hebben bij deling door g.
Met b mod g bedoelen we het kleinste positieve getal a waarvoor a ≡ b (mod g). Je kunt makkelijk inzien dat b mod g de rest is van de restdeling van b door g. Hierdoor is altijd 0 ≤ b mod g < g.
Maar wat heeft modulorekenen nou met g-adische getallen te maken? Bij het optellen of vermenigvuldigen van twee (g-adische) getallen gebruik je, wellicht zonder dat je het door hebt, modulorekenen. Bereken bijvoorbeeld 13 • 8 in grondtal 10. Het eerste cijfer
4 van het product heb je berekend met 3 • 8 = 24 ≡ 4 (mod 10), ofwel, door 2 • 10 naar links over te lenen. Bij g-adische getallen werkt het net zo. Als . . . a2a1a0 × . . . b2b1 b0 =
. . . c2c1 c0, dan is c0 = a0b0 mod g.
Nu gaan we laten zien dat Z10 nuldelers heeft. We zoeken hiervoor een x ∈ Z10
ongelijk aan 0 of 1 met de op het eerste gezicht absurde eigenschap x2 = x. Zo’n getal
14 Zie ook [10] voor meer uitleg hierover.
15 Spreek uit: ‘vijftien en drie zijn congruent modulo twaalf ’.
blijkt echt te bestaan. We beginnen met het vaststellen van het eerste cijfer:
x0 = 5.
Dan is ook het nulde cijfer van x2 gelijk aan 52 = 25 = 5 mod 10; dit cijfer voldoet dus aan de eis. Nu blijkt dat alle volgende cijfers vastliggen; we laten zien hoe we ze stap voor stap kunnen construeren.
Stel dat we in de k-de stap het cijfer xk willen bepalen zodat aan de eis wordt
voldaan.16 In de vorige stappen hebben we dus als benadering x = . . . xk
−1x
k−2
. . . x0
gevonden, waarbij x2 = . . . xk
−1 x
k−2
. . . x0 . Deze k cijfers kunnen niet meer be¨ınvloed
worden door volgende cijfers, deze zijn dus in elk geval goed.
Dit alles schrijven we iets duidelijker op. We weten dat
(xk−1 . . . x2x1x0)
en we zoeken xk zodat
≡ xk−1 . . . x2 x1 x0 (mod 10 )
(xk . . . x2 x1x0)2 ≡ xk . . . x2x1 x0 (mod 10k+1 )
We moeten modulo een macht van 10 rekenen omdat de volgende cijfers nog niet bekend zijn. Bedenk dat hoe groter k, hoe kleiner de invloed is van 10k , dus x wordt steeds nauwkeuriger bepaald.
Als we het i-de cijfer van x2 aanduiden met ai , dan volgt uit vgl. (3.6) en de norm- functie dat
k k−1
ak = X xz xk−z + dk−1 = x0xk + X(xz xk−z ) + xk x0 + dk−1 = yk−1 + 2x0 xk mod 10
z=0
k−1
z=1
waarbij yk−1 = Pz=1 (xz xk−z ) + dk−1. Omdat dk−1 met overlenen te berekenen is, en er
verder alleen termen met xi in voorkomen waarbij 0 < i < k, is yk−1 een bekend (geheel)
getal. Omdat x2 = x moeten alle i-de cijfers van x en x2 overeenkomen, dus
xk = ak ≡ 2x0xk + yk−1 (mod 10)
⇒ xk ≡ 2 • 5 • xk + yk−1 (mod 10)
⇒ − 9xk ≡ 1yk−1 ≡ 81yk−1 = 9 yk−1 (mod 10)
⇒ xk = −9yk−1 mod 10 (3.16)
Hiermee hebben we de gevraagde waarde van xk gevonden.17
Door steeds de waarde van yk−1 te bepalen om vervolgens xk te berekenen met
vgl. (3.16), kun je het getal x construeren; voor de eerste vijf decimalen vinden we
x = . . . 90625. Met een vermenigvuldiging kun je controleren dat inderdaad x2 = x op een veelvoud van 106 na.
16 De nulde stap is dus het vaststellen van x0 = 5.
17 In vgl. (3.16) mogen we mod 10 schrijven in plaats van (mod 10), want omdat xk een cijfer is weten we dat 0 ≤ xk < 10.
Nu berekenen we het getal y = 1 − x = . . . 09376. Als we dit met zichzelf vermenig- vuldigen, rijst het vermoeden op dat ook y2 = y. En inderdaad,
y2 = (1 − x)2 = 12 − 2x + x2 = 1 − 2x + x = 1 − x = y.
Er geldt:
xy = x(1 − x) = x − x2 = x − x = 0
dus x en y zijn nuldelers in Z10 .
In dit voorbeeld hebben we gebruik gemaakt van speciale eigenschappen van het begin- cijfer 5 van x, bijvoorbeeld bij de aanloop naar vgl. (3.16). Het is daarom niet meteen duidelijk of we deze methode ook bij andere grondtallen dan 10 kunnen toepassen, en zo ja, hoe. Het lijkt daarom een onbegonnen werk om te zoeken naar een g waarvoor de ring Zg geen nuldelers heeft. Toch blijkt dat heel gemakkelijk te zijn als we handig gebruik maken van eigenschappen van priemgetallen.18
Stelling 3.5.1. Voor alle p ∈ P bevat Zp geen nuldelers.
Bewijs. Beschouw twee p-adische getallen a en b ongelijk aan 0, waarbij p ∈ P. We schrijven a = . . . a2a1 a0 en b = . . . b2 b1 b0. Omdat a, b = 0 is er een kleinste ai en een kleinste bi die niet nul zijn, zeg ar en bs .
We berekenen ab = c door achtereenvolgens de mult-functie en de norm-functie toe
te passen. Volgens formule (3.6) is het door de mult-functie berekende cijfer cr+s gelijk aan
r+s
X az b(r+s) z
z=0
Als z < r is az = 0, deze termen vallen dus weg. Als z > r is (r + s) − z < s zodat b(r+s)−z = 0, ook deze termen vallen weg. Het enige wat overblijft is de situatie z = r, dus
cr+s = ar bs (3.17) Op dezelfde manier kun je gemakkelijk inzien dat ci = 0 voor alle i < r + s. Bij het
berekenen van a⊗b = norm(ab) wordt er vo´or cr+s dus niet overgeleend. cr+s zelf kan w´el
groter zijn dan p − 1, van dit cijfer kan dus een deel worden overgeleend. Kan het zijn dat
cr+s daardoor nul wordt? Dat zou betekenen dat cr+s veelvoud van p is.19 Maar ar en bs zijn cijfers tussen 1 en p − 1, dus cr+s = ar bs is niet nul en haar priemfactorontbinding kan nooit p bevatten, tegenspraak! We concluderen dat cr+s niet 0 kan zijn, ook niet nadat de norm-functie is toegepast. Daardoor kan ab = c niet 0 zijn, dus Zp heeft geen nuldelers.
In dit bewijs zie je ook waarom het voor samengestelde grondtallen mis kan gaan.
In hoofdstuk 4 zal blijken dat het van belang is dat Zg geen nuldelers heeft, daarom zullen we daar alleen kijken naar Zp met p priem.
18 P is de verzameling priemgetallen.
19 Dit volgt uit regel 7 en 8 van algoritme 3.
3.5.2 Wanneer kun je delen in Zg ?
Deze vraag moeten we wat nauwkeuriger formuleren. Stel a, b ∈ Zg . Zijn er grondtallen
g waarvoor we precies kunnen zeggen voor welke a en b geldt dat a ∈ Zg ?
Allereerst merken we op dat er geen enkele g is waarvoor elke a weer element is van
Zg ; geen enkele ring Zg is dus een lichaam.20 Stel namelijk dat x = a , dan is a = gx
zodat het eerste cijfer a0 van a gelijk is aan nul.21 In bijvoorbeeld Z10 is dus voor minstens 90% van alle a deze deling niet mogelijk. In het algemeen doet dit probleem zich voor bij a waarbij ggd(b, g) > 1.
In §1.2 hebben we al gezien dat delen in Z10 lang niet altijd mogelijk is, ook als b
niet deelbaar is door 10. Op pagina 8 constateerden we dat bijvoorbeeld x = a
nooit
element van Z10 kan zijn als a ‘oneven’ is en b ‘even’.22 Dit komt doordat als b even is, ook a = bx altijd even is; dit heeft te maken met het feit dat ggd(b0, 10) = 2. In het
algemeen is a
geen element van Zg als ggd(b0 , g) = d en bovendien d geen deler is van
a0 .
Als g priem is, is dat geen enkel probleem. Dan is ggd(b0, g) = 1 voor alle b met
b0 = 0, en dat 1 deler is van a0 vormt zeker geen beperking. We kunnen zelfs de volgende stelling bewijzen.
Stelling 3.5.2. Stel p ∈ P en a, c ∈ Zp . Als het eerste cijfer c0 van c ongelijk is aan 0, dan is a ∈ Zp .
Om dit te kunnen bewijzen, hebben we de volgende stelling nodig. Hierbij maken we weer gebruik van modulorekenen.
Stelling 3.5.3. Stel c, s ∈ Z en g ∈ N≥2. De verzameling {0, 1, 2, . . . , g − 1} noemen we Ag . We laten de variabele b alle elementen van Ag precies ´e´en keer doorlopen. Dan doorloopt ook bc + s mod g alle elementen a van Ag precies ´e´en keer, dan en slechts dan als ggd(c, g) = 1. Dit komt op hetzelfde neer als
∀a ∈ Ag : ∃b ∈ Ag : (bc + s) mod g = a ⇔ ggd(c, g) = 1
Bewijs. We onderscheiden twee gevallen.
Stel dat ggd(c, g) = d = 1. Dan zijn bc en g beide deelbaar door d, en daardoor is ook bc mod g deelbaar door d. Er is dus geen b ∈ Ag zodat bc mod g = 1, want 1 is deelbaar door geen enkel getal groter dan 1. Het element 1 + s mod g van Ag wordt dus niet bezocht door bc + s mod g.
20 In een lichaam bestaat immers voor alle b een element 1 , en wegens de inwendigheid van vermenig-
vuldiging bestaan ook alle a .
21 Dit is intu¨ıtief al duidelijk, maar we hebben het ook bewezen, namelijk in stelling 3.4.3. Daar concludeerden we dat ga = a0 en per definitie is a0 = 0.
22 Met even en oneven bedoelen we, ook in Zg , dat het meest rechtse cijfer (niet) deelbaar is door 2.
Dan nu het tweede geval, waarin ggd(c, g) = 1. Optelling en vermenigvuldiging volgens het modulorekenen zijn inwendig in Ag , dus alle bc + s mod g zijn element van Ag . Omdat b precies g elementen van Ag doorloopt, doet bc + s mod g dat ook, waarvan er nog een aantal gelijk kunnen zijn. Aanname: Stel dat er twee gelijk zijn, zodat b1c + s ≡ b2 c + s (mod g) en b1 = b2. Hieruit volgt dat (b1 − b2 )c ≡ 0 (mod g), dus (b1 − b2)c is een veelvoud van g. Omdat c en g geen priemfactoren gemeenschappelijk hebben en c = 0,23 moet (b1 − b2) een veelvoud zijn van g, en omdat b1, b2 ∈ Ag weten we ook dat 0 ≤ b1, b2 ≤ g − 1. Hieruit volgt dat |b1 − b2| ≤ g − 1. Dan kan alleen (b1 − b2) = 0, zodat b1 = b2, tegenspraak! Dus alle g getallen bc + s mod g zijn verschillend. En omdat Ag maar g elementen geeft, moeten alle elementen van Ag worden bezocht door bc + s mod g.
Met deze twee gevallen hebben we bewezen dat bc + s mod g alle elementen van Ag
doorloopt, dan en slechts dan als ggd(c, g) = 1. Hiermee is de stelling bewezen.
Met dit resultaat is het een kleine moeite om stelling 3.5.2 te bewijzen. Dit zullen we nu doen.
Bewijs. Laat p een priemgetal zijn, en a, c ∈ Zp . We willen bewijzen dat a
∈ Zp als
c0 = 0.
We berekenen het product a van twee getallen b, c ∈ Zp door er achtereenvolgens de
mult- en de norm-functie op los te laten. Het tussenproduct mult(b, c) duiden we aan met k.
a = norm(k) = norm mult(b, c)
Omdat Zp ⊂ Z∗ geldt ook dat b, c ∈ Z∗. We schrijven b, c en k uit in cijfers, bijvoorbeeld
p p
b = . . . b2
b1 b0
= (bi ). Uit vgl. (3.6) volgt dat elk cijfer ki
van k te schrijven is als
i
ki = X bz ci−z
z=0
Nu berekenen we a = norm(k). Als we nog eens naar algoritme 3 kijken, zien we dat in de regels 6 t/m 8 elk berekende cijfer ai gelijk is aan ki + di−1 mod 10. In de regels 7 en
8 wordt namelijk als het ware restdeling van ki + di−1 door p uitgevoerd; het quoti¨ent
wordt di genoemd, de rest wordt de nieuwe ai . Er geldt dus:
i i−1
ai = ki + di−1 = X bz ci−z + di−1 = X(bz ci−z ) + bi c0 + di−1 = bi c0 + s mod p
z=0
Hier is s = Pi−1 (bz ci
z ) + d
z=0
; omdat dit een eindige som in Z is, is s een geheel
z=0 −
i−1
getal, net als bi en c0. En omdat p priem is en c0 = 0, is ggd(ci , p) = 1. Hierdoor is er volgens stelling 3.5.3 voor alle mogelijke ai ∈ Ap een geschikte bi ∈ Ap te vinden
zodat ai = bi c0 + s mod g. Omdat Ap de verzameling is van alle mogelijke cijfers van
23 want als c = 0 is ggd(c, g) = g = 1
elementen van Zp , is er voor elk mogelijk cijfer ai een geschikt cijfer bi te vinden.24 We concluderen dat voor alle a, c ∈ Zp , c0 = 0 de vergelijking bc = a oplosbaar naar b is in Zp . Met andere woorden, voor alle a, c ∈ Zp waarbij c niet eindigt op het cijfer 0, is b = a ∈ Zp .
In hoofdstuk 4 zal blijken dat we handig gebruik kunnen maken van deze stelling.
3.6 Algoritme voor deling
Als afsluiting van dit hoofdstuk geven we een algoritme dat kan delen in Zg . Dit algoritme is gebaseerd op de staartdeling zoals we die in §1.2 hebben uitgevoerd. Laten we de werking van zo’n staartdeling eens nauwkeuriger bekijken. Als voorbeeld nemen we weer de berekening van 1 in Z10 die op pagina 7 staat uitgewerkt. De uitkomst van deze deling duiden we aan met c = . . . c2 c1c0, dit is dus gelijk aan . . . 667.
Om c te construeren, zochten we stap voor stap cijfers ci z´o dat het meest rechtse cijfer van 3ci gelijk was aan ai ; hiermee kon ai worden weggepoetst.25 Met andere woorden, we zochten ci zodat 3ci ≡ ai (mod 10). Zo vonden we bijvoorbeeld c0 = 7, want 3 • 7 = 21 ≡ 1 (mod 10). Hierna trokken we 21 af van a om een nieuw tussentijds product a te vinden.
In het algemeen gaat het net zo. Als we voor a, b ∈ Zg de getalwaarde van c = a ∈ Zg willen bepalen (voor zover c bestaat natuurlijk), moeten we de vergelijking ci b0 ≡ ai (mod g) oplossen naar ci . Merk op dat hier alleen het meest rechtse cijfer van b een rol speelt.
We lossen deze vergelijking op met behulp van het zogenaamde ‘uitgebreide algoritme van Euclides’. Dat is een algoritme dat voor ieder paar gehele getallen a, b de vergelijking ax + by = ggd(a, b) oplost naar x, y. Hoe en vooral waarom het algoritme werkt kunnen we hier niet in detail uitleggen; hiervoor verwijzen we naar §3.4 van [1] of hoofdstuk 1 van [5]. Het uitgebreide algoritme van Euclides hebben we (in computertaal) opgenomen als algoritme 4.
Algorithm 4 Uitgebreid algoritme van Euclides
function eucl(a, b ∈ Z) : (x, y) ∈ Z
begin
if a mod b = 0 then
result := (0, 1)
else
(x, y) := eucl(b, a mod b) result := (y, x − y • (a div b)) end
24 Bedenk dat alle cijfers van getallen in Zp tussen 0 en p − 1 liggen.
25 a = . . . a2 a1 a0 is hier het ‘tussentijdse product’ dat in het begin . . . 0001 was, vervolgens . . . 9998, et cetera.
Met dit algoritme kun je voor elke b0 , g ∈ Z de vergelijking b0 x+gy = ggd(b0, g) oplossen. Als bovendien ggd(b0 , g) = 1, dan is b0x + gy = 1 waaruit volgt dat b0x ≡ 1 (mod g). Volgens een regel van het modulorekenen geldt dan dat b0xai ≡ ai (mod g). Hiermee hebben we een mogelijkheid gevonden voor het gezochte cijfer ci dat moest voldoen aan ci b0 ≡ ai (mod g), namelijk ci = xai mod g.
Het mooie van dit algoritme is dat het je precies vertelt hoe je ci kunt construeren als ggd(b0, g) = 1. In de praktijk is het voor kleine g natuurlijk handiger om gewoon de tafel van b0 op te schrijven met grondtal g, en de ci te kiezen waarvoor het laatste cijfer van ci b0 gelijk is aan ai . Voor grote waarden van g is het algoritme van Euclides echter v´e´el sneller.
Aan de hand van het uitgebreide algoritme van Euclides cre¨eren we de functie divide(a, b), zie algoritme 5.
Algorithm 5 Divide
1: function divide(a, b ∈ Zg ) ∈ Zg
2: c := (0, 0, 0, • • • )
3: begin
4: (x, y) := eucl(b0 , g)
5: for i = 0 to ∞ do
6: begin
7: ci := xai mod g
8: a := norm(a − cb)
9: end
10: end
11: Result := c
Dit algoritme voert als het ware een staartdeling uit. In regel 7 wordt ci berekend met behulp van 4, waarna in regel 8 de waarde van het nieuwe tussenproduct a wordt bepaald.
Dit werkt alleen als ggd(b0 , g) = 1, anders geeft eucl(b0, g) de verkeerde uitkomst. Het gaat dus in ieder geval goed als g priem is en b0 ongelijk aan nul. Dit is in overeen- stemmingen met wat we eerder gezien hebben in §3.5.2.
Hoofdstuk 4 Formele invoering van het lichaam Qp
In §1.2 hebben we laten zien dat het bij deling handig is om g-adische kommagetallen toe te staan, getallen van de vorm . . . a2a1 a0.a−1a−2 . . . a−n . We zeiden toen dat we de verzameling van al deze kommagetallen Qg noemen, en dat deze verzameling eigenlijk alleen ‘zin’ heeft als g een priemgetal is. Waarom dat zo is, zal in dit hoofdstuk duidelijk worden. We veronderstellen vanaf nu dat p priem is. We defini¨eren Qp heel anders dan je zou verwachten, namelijk niet als kommagetallen maar als breuken met in de teller en noemer elementen van Zp . Later zal blijken dat deze twee ‘definities’ overeenkomen, dus al die breuken zijn als kommagetallen te schrijven.
Behalve dat Qp in sommige gevallen voordeel heeft bij het uitvoeren van delingen, heeft het een nog veel belangrijker voordeel ten opzichte van Zp . We kunnen namelijk bewijzen dat (Qp , +, ×) een lichaam is. In lichamen gaat alles erg mooi, omdat je altijd
kunt delen. Daardoor kunnen veel stellingen voor lichamen worden bewezen die voor ringen niet altijd opgaan.1 Daar gaan we hier verder niet op in; we verwijzen naar hoofdstuk 4 van [5] voor een aantal eenvoudige stellingen over ringen en lichamen.
Met de methode die we gebruiken, kun je elke willekeurige commutatieve ring met
1 zonder nuldelers (laten we deze ring Ξ noemen) uitbreiden naar een lichaam L. Dat is handig, want zo hebben we ook gelijk een formele invoering van Q vanuit Z. In dit hoofdstuk zullen we vooral in ons achterhoofd houden dat Ξ staat voor Zp en L voor Qp .
4.1 Definitie van L
We defini¨eren nu de algebra¨ısche structuur (L, +, ×), lees (Qp , +, ×)
Definitie 4.1.1.
L = n a | a, b ∈ Ξ, b = 0
b
1 Dit betekent niet dat lichamen per se rijkere structuren zijn dan ringen. In ringen kan delen soms wel en soms niet. Dat levert, voor een geschikte klasse van ringen, de mogelijkheid om iets in de trant van priemgetallen te defini¨eren en te bestuderen.
Twee ‘breuken’ a1 , a2 ∈ L worden als gelijk beschouwd volgens de regel:
b1 b2
a1 = a2
a b = a b
(4.1)
b1 b2 ⇔ 1 2 2 1
Op alle elementen a
∈ L defini¨eren we de operaties optelling en vermenigvuldiging als
volgt.
a1 + a2 := a1 b2 + a2b1
(4.2)
b1 b2
a1
b1b2
a2 := a1 a2
(4.3)
b1 × b2
b1b2
Voordat we van deze definitie uit mogen gaan, willen we eerst aantonen dat ze wel zinvol is. In dit geval komt het erop neer dat we twee stellingen moeten bewijzen.
1. De optelling en vermenigvuldiging zijn inwendig in L.
Bewijs. Wegens de inwendigheid van + en × in Ξ geldt dat a1b2 + a2b1 ∈ Ξ, dat
a1a2 ∈ Ξ en dat b1 b2 ∈ Ξ. Bovendien heeft Ξ geen nuldelers, dus b1b2 = 0. Hierdoor
zijn a1 b2 +a2 b1
1 2
b1 b2 elementen van L, dus + en × zijn inwendig in L.
2. De definitie van de som en het product zijn ondubbelzinnig. Dit houdt in dat
als a1
1
en a2
2
vervangen worden door andere elementen van Ξ die hieraan volgens
(4.1) gelijk zijn, de uitkomsten van de som en het product niet veranderen. Eerst
bewijzen we dit voor de optelling.
Bewijs. Stel dat voor de volgende vier elementen van L geldt:
a1 = c1
a2 c2
en =
(4.4)
b1 d1
b2 d2
We willen dus het volgende aantonen:
a1 + a2 = c1 + c2
(4.5)
b1 b2
d1 d2
Dit is volgens (4.2) gelijkwaardig met:
a1b2 + a2 b1 = c1d2 + c2d1
(4.6)
b1b2
d1d2
Volgens (4.1) is dit bewezen als we hebben aangetoond dat
(a1b2 + a2b1)(d1 d2) = (c1d2 + c2d1 )(b1 b2 ) (4.7) Uit (4.4) volgt bovendien met behulp van (4.1) dat
a1 d1 = c1 b1 en a2d2 = c2b2 (4.8)
Nu hebben we genoeg gegevens verzameld om te bewijzen dat vgl. (4.5) waar is.2
6)
(a1b2 + a2b1 )(d1 d2) = (a1b2)(d1d2 ) + (a2 b1 )(d1d2)
5)×
5)
= (d1d2)(a1b2) + (a2b1)(d1d2 )
= (d1d2 )(b2 a1) + (a2b1)(d1 d2) 2.=4.1 (d1a1 )(b2 d2) + (a2 d2)(d1b1)
5)
= (a1 d1)(b2d2) + (a2d2 )(d1 b1)
5)×
(4.8)
= (c1 b1)(b2d2) + (c2 b2 )(d1b1)
= (b1c1)(d2b2 ) + (b2c2)(d1b1) 2.=4.1 (b1b2)(d2c1 ) + (b2b1)(d1c2 )
5)×
6) 5)×
= (b1b2)(c1d2 ) + (b1 b2)(c2d1) = (b1 b2)(c1d2 + c2d1)
= (c1d2 + c2d1)(b1b2)
Hiermee hebben we de geldigheid van (4.7) aangetoond, en daarmee ook die van
(4.6) en (4.5). Dat laatste is precies wat we wilden bewijzen.
Nu bewijzen we de stelling voor vermenigvuldiging.
Bewijs. We gaan weer uit van de situatie in vgl. (4.4); daardoor geldt automatisch ook vgl. (4.8). We willen nu het volgende aantonen:
a1 a2 = c1 c2
(4.9)
b1 × b2
d1 × d2
Dit komt volgens (4.3) op hetzelfde neer als:
a1a2 = c1 c2
(4.10)
b1b2
d1 d2
Volgens (4.1) is dit bewezen als we hebben aangetoond dat
(a1a2 )(d1d2) = (c1c2)(b1b2) (4.11) Nu hebben we genoeg gereedschap om de stelling te bewijzen.
(a1 a2 )(d1 d2)
(4.8)
= (a1a2)(d2d1) 2.= (a1 d1)(d2a2)
5)×
5)
= (a1d1)(a2d2)
5)×
= (c1 b1 )(c2b2)
= (c1 b1 )(b2 c2) 2.=4.1 (c1c2)(b2b1)
= (c1c2)(b1b2)
Hiermee hebben we de geldigheid van (4.11) aangetoond, en daarmee ook die van
(4.10) en (4.9). En laat dat laatste nou juist ons doel zijn.
Samenvattend komt het er op neer dat we nu de algebra¨ısche structuur (L, +, ×) formeel hebben gedefinieerd, en bovendien bewezen dat de definities van + en × zinvol zijn.
2 Nummers met ´e´en haakje rechts verwijzen naar een eigenschap uit Tabel 2.2 die geldt voor Ξ. Bij- voorbeeld 5)× boven een =-teken betekent dat eigenschap 5), de commutativiteit, geldt voor de verme- nigvuldiging. Nummers met twee haakjes verwijzen naar een vergelijking, nummers zonder haakjes naar een stelling.
4.2 Lemma’s
Om te bewijzen dat L een lichaam is, hebben we twee lemma’s (hulpstellingen) nodig.
Lemma 4.2.1.
ca a
∀a, b, c ∈ Ξ, b, c = 0 :
=
cb b
Bewijs. Uit de associativiteit en commutativiteit van vermenigvuldiging in Ξ volgt dat
(ca)b = (ac)b = a(cb),
dus (ca)b = a(cb). Hieruit volgt met (4.1) dat ca = a .
cb b
Overigens geldt het lemma niet andersom. Niet voor elk paar gelijkwaardige breuken
a1 a2
b1 , b2 ∈ L is er een c ∈ Ξ te vinden zodat
ca1 = a2 en cb1 = b2
Als we bijvoorbeeld naar Ξ = Z en L = Q kijken, zien we dat 3 = 4 . Natuurlijk is
9 12
4
3 ×
4
maar 4 is geen element van Z.
3 × 9 12
Lemma 4.2.2.
∀a1, a2 , b ∈ Ξ :
a1 +
b
a2 =
b
a1 + a2
b
Bewijs. Uit (4.2), Lemma 4.2.1 en de distributiviteit in Ξ volgt:
a1 + a2 = a1b + a2b
(a1 + a2 )b
a1 + a2
b b b2 =
b2 = b
4.3 Bewijs: L is een lichaam
We gaan nu bewijzen dat (L, +, ×) een lichaam is. Hierbij maken we onder meer gebruik van de formules (4.1) t/m (4.3), van de twee lemma’s en van het feit dat (Ξ, +, ×) een commutatieve ring met 1 zonder nuldelers is.
4.3.1 Bewijzen van de eigenschappen van optelling
Als je niet meer weet wat de eigenschappen die we hier bewijzen inhouden, kun je altijd terugblikken naar Tabel 2.2.
We laten vanaf nu de verwijzingen boven de =-tekens weg, het is aan jou om te achterhalen welke eigenschappen worden toegepast. Bijna overal wordt de inwendigheid van + en × in Ξ en L, gebruikt, net als het niet bestaan van nuldelers in Ξ.
Inwendigheid. Dit hebben we al bewezen in §4.1.
Commutativiteit.
a1 + a2 = a1b2 + a2b1 = a2b1 + a1b2 = a2 + a1
b1 b2
b1 b2
b2b1
b2 b1
Associativiteit.
( a1 + a2 ) + a3
b1 b2 b3
= a1b2 + a2b1
b1b2
+ a3
b3
= (a1b2 + a2b1)b3 + a3 (b1b2) (b1b2)b3
= (a1b2)b3 + (a2b1 )b3 + a3(b1 b2 ) (b1b2)b3
= a1(b2b3) + (a2b1)b3 + (a3b1)b2
(b1 b2 )b3
= a1(b2b3) + (b3a2)b1 + (b2a3)b1
b1(b2 b3)
= a1(b2b3 ) + b3(a2 b1 ) + b2(a3 b1 ) (b1b2)b3
= a1(b2b3 ) + (b3a2 + b2a3 )b1
b1(b2b3)
= a1
b1
+ b3 a2 + b2a3
b2b3
= a1
b1
+ a2b3 + a3b2
b2 b3
= a1
b1
+ ( a2
b2
+ a3 )
b3
Nulelement van L. We duiden het nulelement van Ξ aan met 0, en het eenheidselement met 1. Hieruit leiden we af:3
a a + 0
= =
b b × 1
a × 1 + 0 × b = a + 0
b × 1 b 1
Wegens de commutativiteit van + in L geldt ook dat 0 + a
= a . Hiermee is bewezen
dat 0 het nulelement is van L.
1 b b
Tegengestelde. Voor alle a ∈ Ξ is er ook een −a ∈ Ξ zodat a + −a = 0. Nu leiden we af:
a + −a =
b b
a + −a =
b
0 = 0 × b =
b b
0 × b = 0
1 × b 1
Wegens de commutativiteit van + in L geldt ook dat −a + a
= 0 . En omdat 0
het
b b 1 1
nulelement is van L, is hiermee aangetoond dat elk element a
∈ L een tegengestelde
b ∈ L heeft.
3 Bij het bewijs van deze en de volgende stelling wordt stelling 2.4.3 gebruikt.
4.3.2 Bewijzen van de eigenschappen van vermenigvuldiging
Inwendigheid. Dit is al bewezen in §4.1.
Commutativiteit. a1
a2 = a1a2
= a2a1
= a2 × a1
b1 × b2
b1b2
b2b1
b2 b1
Associativiteit.
( a1
b1
a2 a3
× b2 b3
= a1 a2
b1 b2
a3
× b3
= (a1a2)a3
(b1b2 )b3
= a1(a2a3)
b1(b2b3)
= a1
b1
a2 a3
× b2 b3
= a1
b1
( a2
× b2
a3 )
× b3
Eenheidselement van L. We duiden het eenheidselement van Ξ weer aan met 1.
a = a × 1 =
b b × 1
a 1
b × 1
Wegens de commutativiteit van × in L geldt ook dat 1 × a = a . We concluderen dat 1
het eenheidselement van L is.
1 b b 1
Inverse. We willen bewijzen dat elke a
∈ L ongelijk aan het nulelement 0
van L, een
inverse heeft in L. Uit Lemma 4.2.1 volgt dat
0 = 0 × b = 0
1 1 × b b
voor alle b ∈ Ξ. We zijn dus klaar als we hebben bewezen dat er voor elke a ∈ L met
a = 0 een inverse is. Dat is niet moeilijk. Omdat a = 0 is namelijk b ∈ L.
a b ab
1 × (ab) 1
b × a = ba = 1 × (ab) = 1
Omdat vermenigvuldiging commutatief is in L, is ook b × a = 1 , het eenheidselement
a b 1
van L. Hiermee is bewezen dat elk element a ∈ L ongelijk aan 0 een inverse b
heeft.
b 1 a
4.3.3 Bewijs van de distributiviteit
Distributiviteit. We bewijzen eerst de links-distributiviteit:
a1 a2 a3 a1 a2b3 + a3b2 a1 (a2 b3 + a3b2)
( + ) = × =
b1 × b2 b3 b1
b2b2
b1 (b2b3)
= a1(a2 b3 ) + a1(a3b2)
b1(b2 b3)
= (a1a2)b3 + (a1a3)b2
(b1b2)b3
= (a1a2)b3
(b1b2)b3
+ (a1a3 )b2
(b1b2)b3
= (a1 a2 )b3
(b1 b2)b3
+ (a1 a3)b2
b3(b1 b2)
= (a1a2)b3
(b1b2 )b3
+ (a1a3)b2
(b3b1)b2
= a1 a2
b1 b2
+ a1 a3
b3 b1
= a1a2
b1b2
+ a1a3
b1b3
= a1
b1
a2
× b2
+ a1
b1
a3
× b3
Omdat × commutatief is in L, mogen we stelling 2.4.2 toepassen. De rechts-distributiviteit geldt daarom ook.
Met dit alles hebben we bewezen dat L een lichaam is. In het bijzonder zijn dus Q en
Qp lichamen. Dit zetten we tot slot nog even overzichtelijk in een tabel.
Commutatieve ring met 1 zonder nuldelers Daaruit geconstrueerd lichaam
Algemeen
Ξ
L
Voorbeelden
Z Zp
Q Qp
4.4 Koppeling tussen Ξ en L
We weten intu¨ıtief dat Ξ een deelverzameling is van L. Immers, voor alle a ∈ Ξ is a/1 ∈ L, en voor ons gevoel is a = a/1. Hoe logisch dat ook lijkt, het is niet echt te bewijzen. Dat komt doordat we de operaties in L heel anders gedefinieerd hebben dan
in Ξ, en je kunt in de wiskunde geen appels met peren vergelijken.
Wel kunnen we laten zien dat ons idee om a en a/1 als gelijk te beschouwen, ‘zinvol’ is. Hiervoor cre¨eren we een ‘afbeeldingsfunctie’ f , die elk element a ∈ Ξ aan het element a/1 ∈ L koppelt.
Definitie 4.4.1.
a
∀a ∈ Ξ : f (a) := 1
Het nagaan dat het zin heeft om a aan a/1 (ofwel f (a)) te koppelen, komt in dit geval hierop neer. We bewijzen drie dingen, namelijk dat f (a)+f (b) = f (a+b), dat f (a)f (b) = f (ab), en dat uit a = b volgt dat f (a) = f (b). Dat zijn drie vereisten die natuurlijk in elk geval zouden moeten gelden als f (a) op te vatten is als a. Als hieraan voldaan wordt, zegt men ook wel dat f de bewerkingen + en × in Ξ en L ‘respecteert’.
Stelling 4.4.2. De som van de afbeeldingen is gelijk aan de afbeelding van de som.
∀a, b ∈ Ξ : f (a) + f (b) = f (a + b)
Bewijs.
a b f (a) + f (b) = + =
1 1
a × 1 + b × 1 =
1 × 1
a + b
1
= f (a + b)
Stelling 4.4.3. Het product van de afbeeldingen is gelijk aan de afbeelding van het product.
∀a, b ∈ Ξ : f (a) × f (b) = f (ab)
Bewijs.
a b a × b ab
f (a) × f (b) = 1 × 1 = 1 × 1 =
= f (ab)
1
Stelling 4.4.4. Verschillende elementen hebben verschillende afbeeldingen.
∀a, b ∈ Ξ : a = b ⇒ f (a) = f (b)
Bewijs. Laat a ongelijk zijn aan b. Aanname: Stel dat f (a) = f (b). Hieruit volgt:
a b
f (a) = f (b) ⇒ 1 = 1 ⇒ a × 1 = b × 1 ⇒ a = b
Maar we hadden gesteld dat a = b, tegenspraak! We concluderen dat de aanname onjuist is, dus de stelling is juist.
We hebben nu aangetoond dat f de bewerkingen van Ξ en L respecteert. Nu heeft het zin om de verzameling Ξ als deelverzameling van L op te vatten, waarbij a en a/1 als gelijk worden beschouwd. Gelukkig maar dat we konden bewijzen dat dat ‘zin’ heeft, anders was er iets vreemds aan de hand!
4.5 Komen verschillende definities van Qp overeen?
We hebben tot nu toe twee idee¨en van Qp door elkaar heen gebruikt. In de informele beschouwing van hoofdstuk 1 kwam ons beeld van Qp hierop neer:
∀p ∈ P : Qp = {. . . a3a2a1a0 .a−1a−2 . . . a−n | ai ∈ N, 0 ≤ ai < p} (4.12) In de formele definitie van Qp in §4.1 hebben we juist gesteld dat
n a o
∀p ∈ P : Qp =
b | a, b ∈ Zp , b = 0
(4.13)
In deze paragraaf bewijzen we dat beide definities van Qp op hetzelfde neerkomen. Bo- vendien bewijzen we dat er nog een derde definitie mogelijk is die ook op hetzelfde neerkomt.
4.5.1 Plan van aanpak
We gaan uit van de formele definitie van Qp , dus van (4.13) en niet van (4.12).
We defini¨eren de deelverzameling Vp van Qp als de verzameling van breuken die
geschreven worden als a
met a ∈ Zp
en n ∈ N. Dit is duidelijk een deelverzameling van
Qp , want omdat Z ⊂ Zp is ook pn ∈ Zp ; bovendien is pn nooit nul.
Vp :=
a
pn | a ∈ Zp , n ∈ N
(4.14)
Op een soortgelijke manier defini¨eren we de deelverzameling Wp van Qp als de verzame-
ling van breuken die geschreven worden als a met a ∈ Zp en d ∈ Z .
Wp := n
d
| a ∈ Zp ; d ∈ Z≥1
o (4.15)
Omdat pn ∈ Z
is bovendien Vp
een deelverzameling van Wp , zodat
Vp ⊂ Wp ⊂ Qp (4.16)
Hierdoor gelden ook voor elementen uit Vp en Wp de vergelijkingen (4.1), (4.2) en (4.3). We willen de volgende stelling bewijzen.
Stelling 4.5.1.
Vp = Wp = Qp
Je vraagt je misschien af wat dit te maken heeft met wat bovenaan §4.5 staat, namelijk dat we bewijzen dat de verzamelingen bij (4.12) en (4.13) overeenkomen. Toch komt het bewijzen van stelling 4.5.1 op hetzelfde neer, zoals later zal blijken. Vp komt namelijk overeen met de verzameling bij (4.12).4 De verzameling Wp is de derde mogelijke definitie van Qp .
We bewijzen de stelling door aan te tonen dat Qp ⊂ Vp . Omdat Vp ⊂ Qp volgt daaruit5 dat Vp = Qp . Uit (4.16) volgt dan natuurlijk ook dat Vp = Wp = Qp , waarmee de stelling bewezen is.
Om de stelling te bewijzen hebben we een lemma nodig.
4.5.2 Lemma: goochelen met nullen
Lemma 4.5.2 is een uitbreiding van stelling 3.4.4 (zie pagina 31). Voor elk p-adisch getal
a, is pa volgens stelling 3.4.4 gelijk aan a met een nul erachter geplakt.
p × . . . a2a1 a0 = . . . a2a1 a00
4 Behalve dat we nu nog niet mogen beweren dat verzameling (4.12) gelijk is aan Qp , want dat willen we juist bewijzen.
5 zie pagina 13
Vermenigvuldigen met pn kan worden opgevat als het n keer herhaald vermenigvuldigen met p. Dus pn a is gelijk aan a met n nullen erachter geplakt.
Een eigenschap van deling in Qp is dat het vermenigvuldiging ongedaan maakt. Immers,
a × b = (a × 1) × b = a × 1 = a = a (4.17)
b 1 × b 1 1
Daarom moet deling door pn in Zp op hetzelfde neerkomen als een verschuiving van alle cijfers n plaatsen naar rechts, waarbij een rij van n nullen waar a op eindigt, wordt verwijderd. Deze nullen moeten er natuurlijk wel zijn, anders is het resultaat geen element van Zp . We mogen eventuele andere cijfers dan nullen niet “achter de komma” plaatsen en zeggen dat dit een element van Qp is, want we hebben de elementen van Qp niet gedefinieerd als rijtjes van cijfers. Dus als a eindigt op z nullen (waarbij z ook 0 kan zijn), moet gelden dat n ≤ z willen we kunnen delen door pn binnen Zp .
Lemma 4.5.2. Voor alle a = . . . a2a1 a0 ∈ Zp en n ∈ N komt vermenigvuldiging met pn
op hetzelfde neer als n nullen achter a plakken.
n nullen
pn × . . . a2a1a0 = . . . a2a1a0 0z 00}.|. . 0{
Als ai = 0 voor alle i ≤ z, en bovendien z ≥ n, dan komt deling door pn op hetzelfde neer als een rij van n nullen achter a schrappen.
. . . a2a1a0
pn = . . . an+2 an+1 an
4.5.3 Bewijs: Vp = Wp = Qp
Allereerste een verkorte notatie. De verzameling {x | x ∈ N, x ≤ p − 1}, dat zijn alle mogelijke cijfers van getallen in Zp , noemen we weer Ap .
We beschouwen een element c = a
∈ Qp . De p-adische gehele getallen a, b en c
schrijven we als . . . a3a2a1a0 , . . . b3b2 b1 b0 resp. . . . c3 c2c1c0 waarbij ai , bi , ci ∈ Ap . De
kleinste i waarvoor bi = 0 noemen we z. Het is makkelijk na te gaan dat z het aantal nullen is waar b op eindigt.
We onderscheiden 2 gevallen.
i. z = 0, dus b0 = 0. Omdat bovendien p priem is, volgt uit stelling 3.5.2 dat a ∈ Zp .
Omdat6 Zp ⊂ Vp is ook a ∈ Vp .
ii. z = 0, dus b0 = 0. Stelling 3.5.2 mogen we nu niet toepassen, want die geldt alleen als b0 = 0. Wat we wel kunnen doen, is b delen door pz . Dit komt op hetzelfde neer als bij b direct links van de komma z nullen verwijderen, zie Lemma 4.5.2. En
6 Immers, als n = 0 is a
= a = a, een vrij te kiezen element uit Zp .
omdat b op precies z nullen eindigt, is het eerste cijfer van b/pz ongelijk aan nul. Nu mogen we stelling 3.5.2 w´el gebruiken, dus
a
b/pz =: y ∈ Zp (4.18)
Omdat Vp ⊂ Qp mogen we de rekenregels voor Qp natuurlijk ook toepassen op Vp . Daarvan zullen we nu gebruik maken. De derde gelijkheid volgt uit vgl. (4.17).
y = Hieruit volgt:
a b/pz
a pz
= = (b/pz ) × pz
a × pz
b
a pz
=
b × 1
a pz
= b × 1
= a pz
b
y a
pz = b
Volgens vgl. (4.18) is y ∈ Zp , dus y/pz ∈ Vp .7 Hieruit blijkt dat a ∈ Vp .
In beide gevallen i en ii, dus voor alle a ∈ Qp ,8 is a ∈ Vp . We concluderen dat Qp ⊂ Vp .
b b
Uit vgl. (4.16) volgt dat
Hiermee is stelling 4.5.1 bewezen.
Vp = Wp = Qp (4.19)
4.5.4 Qp beschouwd als rijtjes van cijfers
Met dit resultaat kunnen we Qp voortaan beschouwen als Vp , zodat elk element van Qp kan worden opgevat als een p-adisch geheel getal gedeeld door een macht van het grondtal p. In Zp hebben we gezien dat a/pn overeenkomt met een verschuiving van alle cijfers n plaatsen naar rechts, mits a eindigt op minstens n nullen. We kunnen dit idee uitbreiden naar Qp . Hiervoor voeren we in Zp een decimale punt in rechts van elk getal, zo kunnen we bijvoorbeeld a = . . . k3k2k1 k0. schrijven. Deling door pn kunnen we weer opvatten als een verschuiving van alle cijfers n plaatsen naar rechts, waarbij cijfers ook rechts van de komma mogen staan. Zodoende kunnen we elk element a/pn ∈ Qp opvatten als een rij cijfers . . . kn+3 kn+2 kn+1 kn .kn−1 kn−2 . . . k0. Voor m ∈ N, m ≤ n komt vermenigvuldiging met pm overeen met een verschuiving van alle cijfers m plaatsen naar links, want
m a pm
a × pm
a × pm
. . . kn+1 kn .kn−1 . . . k0 × p
= =
pn 1
=
pn × 1 (pn−m × pm ) × 1
a pm
=
pn−m × pm
a
= pn−m
= . . . kn−m+1 kn−m .kn−m−1 . . . k0
Dit kan ook worden opgevat als een verschuiving van de komma m plaatsen naar rechts. Deling door pm in Qp kan dan worden opgevat als een verschuiving van de komma m
7 Immers, z is het aantal nullen is waarop b eindigt, dus z ∈ N.
8 want als i niet geldt, dan geldt ii en andersom plaatsen naar links. Een eventuele rij nullen aan het eind van het getal rechts van de komma mag worden weggedacht.
Als m ∈ N, m ≥ n is
a pm
. . . kn+1 kn .kn−1 . . . k0 × p = pn 1 =
a pm
=
pn × 1
a × (pm−n × pn )
1 × pn
m−n nullen
(a × pm−n ) × pn
1 × pn
a pm−n
=
1
= a × pm−n = . . . k3 k2k1k0 0 000}|. . . 0{
Dit komt overeen met een verschuiving van de komma m plaatsen naar rechts, waarbij de m − n lege plaatsen van een nul worden voorzien.
De gevonden resultaten ordenen we in formules. Laat c ∈ Qp , q ∈ N. We schrijven c uit in cijfers als . . . k3k2k1k0 .k−1k−2 . . . k−n . Let op: het laatste cijfer is nu k−n en niet k0, zoals hiervoor steeds het geval was.
c × pq =
. . . k−n+3 k−n+2 k−n+1 k−n
q−n nullen
z0 00}.|. . 0{
als n < q
. . . k−n+3 k−n+2 k−n+1 k−n als n = q
. . . k−q+2 k−q+1 k−q .k−q−1 k−q−2 . . . k−n als n > q
Voor deling door pq in Qp gelden de volgende formules. Het is mogelijk dat n = 0 zodat c ∈ Zp , dan is dus c = . . . k3k2 k1k0. Als in dat geval c bovendien rechts eindigt op z nullen, dan mogen de nullen achter de komma natuurlijk weggedacht worden in c/pq . In formule:
c
. . . kz+3 kz+2 kz+1 kz
z−q nullen
0 00}.|. . 0{
als n = 0, z > q
pq =
. . . k
q+3
kq+2
kq+1 kq
als n = 0, z = q
. . . kq+2 kq+1 kq .kq−1kq−2 . . . kz als n = 0, 0 ≤ z < q
. . . kq+2 kq+1 kq .kq−1kq−2 . . . k−n als n = 0
Dat laatste geval, n = 0, is natuurlijk het meest voorkomend. De eerste drie gevallen zijn uitzonderingen.
Een voordeel van getallen uit Qp voorstellen als rijtjes van cijfers
. . . k3k2 k1k0.k−1k−2 . . . k−n
is dat er gemakkelijk mee kan worden gerekend. Stel dat we twee willekeurige p-adische getallen a1/pn1 en a2 /pn2 bij elkaar willen optellen. Zoals we weten geldt:
a1 a2
a1pn2 + a2pn1
pn1 + pn2 =
pn1 +n2
a1pn2 en a2 pn1 zijn de oorspronkelijke p-adische getallen waarbij de komma n1 + n2
plaatsen naar links geschoven is, en de n2 resp. n1 lege plekken met nullen zijn opgevuld.
Deze p-adische gehele getallen tellen we op volgens het optel-algoritme, en vervolgens “delen” we door pn1 +n2 , ofwel we plaatsen de komma n1 + n2 stappen naar links. Nu hebben we de gevraagde som berekend.
Deze optelling klinkt misschien ingewikkeld, maar het gaat eigenlijk net zo als we bij (afgeronde) re¨ele getallen gewend zijn. Op pagina 8 hebben we zelfs al zo’n optelling uitgevoerd.
Ook vermenigvuldigen is makkelijk als elementen a/pn ∈ Qp als rijtjes voorgesteld
worden. We weten namelijk:
a1 a2
a1 a2
pn1 × pn2 = pn1 pn2
a1 en a2 zijn de oorspronkelijke p-adische getallen waarbij “de komma weggedacht wordt”. We berekenen a1a2 met het vermenigvuldig-algoritme en plaatsen de komma links van het (n1 + n2 )-de cijfer, waarmee het gevraagde product gevonden is. Ook dit gaat eigenlijk net zo als vermenigvuldiging van (afgeronde) re¨ele getallen.
Hoofdstuk 5 Weergave van g-adische getallen
Hoe kun je Zg of Qp grafisch weergeven? En welke problemen treden daarbij op? Daar- over gaat dit hoofdstuk.
5.1 Chaos
De verzamelingen N, Z, Q en R kunnen we afbeelden op een getallenlijn. In principe kunnen we dit ook met C doen, we zouden bijvoorbeeld 523.7104 . . . + 8.9076 . . . i kunnen afbeelden naar het punt 502038.79100746 . . . van de re¨ele getallenlijn. In het algemeen zouden we C kunnen afbeelden naar R met de afbeeldingsfunctie
an . . . a0 .a−1 . . . + bn . . . b0.b−1 . . . i 7→ an bn . . . a0b0.a−1b−1 . . .
Op deze manier stelt elk punt op de re¨ele getallenlijn precies ´e´en complex getal voor. De vraag is alleen wat deze afbeelding voor zin heeft. Het blijkt veel waardevoller te zijn om C af te beelden naar een getallenvlak door een imaginaire as loodrecht op de re¨ele as toe te voegen.
Iets dergelijks doet zich voor bij de p-adische getallen. We zouden simpelweg een afbeeldingsfunctie f : Qp → R kunnen defini¨eren die elk getal omkeert.
f : . . . a2a1a0.a−1 . . . a−n 7→ a−n . . . a−1.a0a1a2 . . .
Dit hebben we eens uitgeprobeerd met Q5, voor het gemak hebben we alleen naar de deelverzameling Z5 daarvan gekeken. Met Microsoft Excel hebben we voor alle elementen x ∈ Z5, afgerond op 5 decimalen, de waarde van f (x) berekend en die op de getallenlijn uitgezet. Vervolgens lieten we een grafiek van de functie g(x) = x + b tekenen, waarbij b een constant 5-adisch geheel getal was. Dit is een lineaire functie; als je deze grafiek voor x, b ∈ R zou tekenen, zou er een rechte lijn ontstaan. In Zg blijkt dat niet het
geval te zijn, zie Figuur 5.1 op pagina 57. De x-as is de re¨ele getallenlijn op het interval [0, 1) in grondtal 5, voor de y-as geldt hetzelfde. Voor b hebben we hier . . . 42424244 genomen. Op het eerste gezicht ziet dit er best ordelijk uit, hoewel minder dan een rechte lijn. Toch heeft elk schuin ‘streepje’ op zijn beurt ook weer een grillige structuur.
Figuur 5.1: Grafiek van g(x) = x + b met x, b ∈ Z5
Ook blijkt dat op hoe meer decimalen nauwkeurig je de getallen benadert, hoe grilliger deze structuur is. Als je op ´e´en streepje van de grafiek inzoomt, lijkt dit heel veel op de grafiek zelf. We vermoeden dat het plaatje een fractal is als je de getallen met oneindige nauwkeurigheid zou benaderen.
Vervolgens hebben we de punten van Figuur 5.1 laten verbinden door een vloeiende lijn. Hierbij werd de volgorde x = . . . 001, . . . 002, . . . 003, . . . 010, • • • aangehouden. Op deze manier is Figuur 5.2 ontstaan, zie pagina 58. Het is een prachtig en bizar plaatje, maar het is niet duidelijk wat de betekenis ervan is. In ieder geval ziet het er chaotisch uit, het is bepaald geen rechte
lijn zoals bij de re¨ele getallen het geval zou zijn. De afbeelding doet denken aan de zogenaamde Lorenz-attractor, een oplossing van een bepaalde differentiaalvergelijking die oorspronkelijk is opgesteld om een natuurkundig verschijnsel te modelleren. De Lorenz-attractor blijkt een fractal te zijn.1 Of dit werkelijk iets met de afbeelding van p-adische getallen te maken heeft weten we niet; misschien heeft het vooral te maken met de vreemde volgorde van het verbinden van punten, en met de manier waarop Excel vloeiende lijnen tekent.
1 Bron: [2], hoofdstuk 20
Figuur 5.2: Opnieuw de grafiek van g(x) = x + b, nu verbonden door een lijn.
5.2 Het g-adische getallenvlak
We hebben gezien dat een poging om 5-adische getallen op een getallenlijn uit te zetten, absurde resultaten oplevert. Uit Figuur 5.1 blijkt bijvoorbeeld dat er problemen ontstaan als we een bepaalde grootte aan een 5-adisch getal willen toekennen. Het is voor de hand liggend om af te spreken dat het meest rechtse cijfer het meeste invloed heeft op de grootte van het getal, gevolgd door het cijfer links daarvan, et cetera. Dan is bijvoorbeeld . . . 13 > . . . 11 en . . . 29 > . . . 31. Maar ook geldt:
. . . 13 + . . . 18 = . . . 31 < . . . 29 = . . . 11 + . . . 18
Blijkbaar gaat, volgens deze definitie van de relatie >, de regel a > b ⇒ a + c > b + c niet altijd op. Dit verschijnsel wordt goed ge¨ıllustreerd door Figuur 5.1.
Voor een beter begrip van g-adische getallen is het afbeelden op een getallenlijn dan ook geen goed idee, het schept alleen maar verwarring. Daarom pakken we het anders aan. In plaats van een getallenlijn tekenen we een getallenvlak.
We werken weer in Z5 , voor andere Zg en voor Qp gaat het analoog. Allereerst tekenen we een grote cirkel, hierin bevinden zich alle elementen van Z5 . Deze cirkel delen we op in vijf kleinere cirkels, zie Figuur 5.3. Deze vijf cirkels stellen de mogelijkheden voor van a0 waarbij a = . . . a2 a1 a0 een willekeurig element van Z5 is. Voor het gemak nummeren we de cirkels met
0, 1, . . . , 4.
Laten we bijvoorbeeld a0 = 2 kiezen. Binnen cirkel 2 tekenen we weer vijf cirkels, zij geven de mogelijkheden van a1 weer. Hieruit kiezen we weer een cirkel en delen deze ook op. Zo kunnen we in theorie oneindig lang doorgaan. Met ieder cijfer wordt a beter benaderd, evenals de plaats van het getal in het 5-adische getallenvlak.
We zien nu grafisch weergegeven dat hoe verder een cijfer van een g-adisch getal naar links staat, hoe minder invloed het heeft op (de plaats van) het getal. Opnieuw is het resultaat een prachtig plaatje, dit keer is het duidelijk dat het een fractal is. Het behoeft geen uitleg hoe het g-adische getallenvlak er in het algemeen uitziet voor andere g.
Figuur 5.3: Het 5-adische getallenvlak
Antwoorden
1.2.1 a. . . . 99999, dit is inderdaad wat we op blz. 5 gezien hebben. b. . . . 22140 c. Nee. Het overlenen gebeurt van rechts naar links, dit kan daarom geen invloed hebben op cijfers die je eerder hebt berekend.
1.2.2 a. . . . 00001423423 = 1423423 in grondtal 5 in Z. b. 1
= . . . 2857142857143, dit heeft
285714 als repeterende staart. 1 is niet te berekenen in Z10 , het eerste cijfer 1 van . . . 00001 is namelijk niet weg te poetsen met een getal uit de tafel van 8. c. In de tafel van 7 heeft ieder getal in grondtal 10 een ander rechtercijfer; elk rechtercijfer komt precies 1 keer voor. Daardoor is elk cijfer op precies ´e´en manier weg te poetsen in een deling. In de tafel van 8 komt elk even rechtercijfer twee keer voor, en elk oneven rechtercijfer nul keer. Dit alles heeft te maken met het feit dat ggd(7, 10) = 1 en ggd(8, 10) = 2 = 1.
2.3.1 a. Nee. 7) en 8) zijn geen zinvolle beweringen als er geen nulelement is vastgelegd. b. Allemaal behalve 4) voor optelling en 4) voor vermenigvuldiging. c. Z: allemaal behalve 4) voor vermenigvuldiging. Voor Q, R en C gelden alle regels.
2.3.2 b. Z is een commutatieve ring met 1 zonder nuldelers. Q, R en C zijn lichamen.
3.1.1 . . . b3 b2 b1 b0 waarbij b0 = g − a0 , en bi = g − ai − 1 voor alle i > 0.
3.1.2 Er geldt: [ei ] × [bi ] = [ Pi
ek bi
k ] = [e b
] = [1b ] = [b ], want als k > 0 is e
= 0 en
dan is ook ek bi−k = 0.
k=0 −
0 i−0 i i k
Bibliografie
[1] Frits Beukers, Getaltheorie voor Beginners, Epsilon Uitgaven 2008
[2] Jan van de Craats, Vervolgboek Wiskunde, Pearson Education 2009
[3] David A. Madore, A first introduction to p-adic numbers, 2000
[4] Fernando Quadros Gouvˆea, p-adic Numbers: An Introduction, Springer-Verlag 2003
[5] M. Riemersma, Algebra, Epsilon Uitgaven 2003
[6] http://en.wikipedia.org/wiki/P-adic number
[7] http://en.wikipedia.org/wiki/Algebraic structure
[8] http://nl.wikipedia.org/wiki/Verzameling %28wiskunde%29
[9] http://nl.wikipedia.org/wiki/Polynoom
[10] http://en.wikipedia.org/wiki/Modular arithmatic#The congruence relation
(Zie de genoemde pagina’s van Wikipedia voor de primaire bronnen.)
Introductie tot de p-adische getallen
Profielwerkstuk Junior College Utrecht
Lars van den Berg, Joep van den Hoven, Linda van der Spaa
Onder begeleiding van dr. R.W. Bruggeman
26 februari 2011
1 Laatst gewijzigd: 20 november 2011
Voorwoord
We zijn zo gewend om met de re¨ele getallen te rekenen dat we er meestal niet bij stilstaan wat een getal eigenlijk is. Het begrip ‘getal’ heeft in de loop van de geschiedenis echter een grote ontwikkeling doorgemaakt. De oude Grieken bijvoorbeeld geloofden alleen in
de rationale getallen (de ‘breuken’ a/b met a, b geheel), irrationale getallen als √2 en π
De p-adische getallen zijn in zekere zin precies het omgekeerde van de re¨ele getal- len. Bijvoorbeeld 65.7204851 . . . ‘is’ een re¨eel getal (hoewel de vraag open blijft hoe hij verder doorloopt); links van de komma mogen maar eindig veel cijfers staan, rechts heeft hij de vrijheid zich tot in het oneindige uit te strekken. We kunnen zo’n getal zien als limiet van een rij rationale getallen die hem steeds beter benadert maar nooit precies bereikt, bijvoorbeeld 60, 65, 65.7, 65.72, . . . Een voorbeeld van een p-adisch getal is . . . 1584027.56: we hebben het getal van daarnet omgeklapt. We kunnen het zien als limiet van de rij 0.06, 0.56, 7.56, 27.56, . . . Maar bestaat deze limiet wel, en is dit getal niet oneindig groot? Dat hangt er vanaf hoe je het bekijkt. In de p-adische wereld worden de cijfers juist minder belangrijk naarmate ze verder naar links liggen. Als we de rij 0.06, 0.56, 7.56, 27.56, . . . met een gewoon meetlint meten wordt het lint al snel te klein, maar als we ons p-adisch meetlint uit de kast halen komen de getallen wel degelijk steeds dichter bij elkaar te liggen en convergeert de rij naar een limiet. Volgens ons lint liggen dus bijvoorbeeld . . . 5227289 en . . . 4227289 heel dicht bij elkaar.
Met p-adische getallen kunnen we ook rekenen, dit gaat eigenlijk net zo als dat we ii bij de re¨ele getallen gewend zijn. Er blijken dan wel wonderlijke dingen te gebeuren. De p-adische getallen kennen bijvoorbeeld geen onderscheid tussen positieve en negatieve getallen. En als a groter is dan b, dan kan het zomaar zijn dat a + c kleiner is dan b + c. Tussen de mystieke p-adisch getallen zitten zomaar getallen die we al lang kennen: alle rationale getallen komen ook voor tussen p-adische getallen. Ze zijn dan echter wel bijna onherkenbaar van gedaante veranderd.
Eerst moeten we leren rekenen met de getallen, dat is een belangrijke eerste stap om ze te begrijpen. Daarna nemen we een duik in de moderne algebra waar we hulpmiddelen zoeken om de p-adische getallen beter te bestuderen. Alles in de wiskunde hangt met elkaar samen, het zou kortzichtig zijn om wiskundige vragen te vermijden die op het eerste gezicht niet met p-adische getallen te maken hebben. We hopen dat je net zo veel plezier zult beleven aan het lezen hiervan als dat wij aan het schrijven hebben gehad.
Dat wij met plezier aan dit onderzoek hebben gewerkt was niet mogelijk geweest zonder de inspirerende gesprekken met Roelof Bruggeman. Hij heeft veel tijd besteed aan het begeleiden en in goede banen leiden van ons onderzoek. We hebben veel van hem geleerd, zowel zuivere wiskunde als het maken van een goed verslag, en we zijn hem veel dank verschuldigd. We ontvingen nuttig commentaar van Philip van Egmond, Corn´e Ruwaard, Erik Nonhebel en Marlien Sneller die het manuscript hebben doorgespit, we willen hen daar hartelijk voor danken.
Opmerking. Behalve dit voorwoord en het omslagplaatje hebben we vrijwel niets ver- anderd aan dit werkstuk. Het is daarom wiskundig van minder hoog niveau dan het werkstuk over de Laatste stelling van Fermat dat ook op mijn webpagina te vinden is, maar misschien daarom juist waardevoller voor vwo-leerlingen: er wordt minder voor- kennis vereist. Toch wil ik graag kwijt dat de p-adische getallen veel en veel meer omvatten dan we in dit werkstuk konden behandelen of zelfs maar konden vermoeden. Ze zijn essentieel in de moderne getaltheorie, maar om te begrijpen waarom heb je min of meer drie jaar universitaire wiskunde nodig. De link met getaltheorie kunnen we als volgt zien: bijvoorbeeld de rij 6, 56, 756, 2756, . . . met als grondtal het priemgetal p stelt het getal . . . 2756 voor modulo p, p2, p3 , p4, p5 . . .. Rekenen modulo m is in zekere zin
‘informatie vergeten’ of ‘minder nauwkeurig naar het getal kijken’ zodat het getal een- voudiger wordt, en hoe groter m, hoe groter de ‘graad van nauwkeurigheid’. We zoomen dus steeds verder in, en als we dit tot in het oneindige herhalen hebben we het getal
‘gelift’ naar de p-adische wereld. Er zit veel getaltheoretische informatie in verstopt, maar daar blijft het niet bij: net als bij de re¨ele getallen kunnen we de analyse inschake- len. Zo kunnen we bijvoorbeeld de afgeleide bekijken van een functie van een p-adische variabele, en we kunnen het hebben over ex met x een p-adisch getal. Op deze manier wordt een brug gebouwd tussen twee ogenschijnlijk verschillende vakgebieden. Dit alles kunnen we hier helaas niet behandelen, maar toch ben ik ervan overtuigd dat er genoeg interessants overblijft om te inspireren tot verdere studie.
Alle correcties en suggesties voor verbetering kun je sturen naar
Inhoudsopgave
Voorwoord ii
1 Kennismaking met g-adische getallen 3
1.1 Wat zijn g-adische getallen? . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 g-adisch rekenen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Er zitten breuken verstopt in Qg . . . . . . . . . . . . . . . . . . . . . . . 8
2 Algebra¨ısche structuren 11
2.1 Algebra in een notendop . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Symbolen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4 Enkele stellingen over algebra¨ısche structuren . . . . . . . . . . . . . . . . 16
2.5 Getalsystemen als algebra¨ısche structuren . . . . . . . . . . . . . . . . . . 18
2.5.1 N, de Natuurlijke getallen . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.2 Z, de Gehele getallen . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.3 Q, de Rationale getallen . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.4 R, de Re¨ele getallen . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5.5 C, de Complexe getallen . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.6 Zp en Qp , de p-adische gehele en gebroken getallen . . . . . . . . . 20
3 Precieze invoering van de ring Zg 21
3.1 Voorbereiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Bezwaren tegen de P methode . . . . . . . . . . . . . . . . . . . . 23
3.3 Algoritmes voor Z∗ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.1 Optelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3.2 Vermenigvuldiging . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Normalisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.1 Lemma’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.4.2 Bewijs: Zg is een commutatieve ring met 1 . . . . . . . . . . . . . 34
3.5 Deelbaarheid in Zg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.1 Nuldelers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5.2 Wanneer kun je delen in Zg ? . . . . . . . . . . . . . . . . . . . . . 39
4 Formele invoering van het lichaam Qp 43
Hoofdstuk 1 Kennismaking met g-adische getallen
In de volgende hoofdstukken gaan we de g-adische getallen formeel defini¨eren en aan de hand daarvan een aantal stellingen bewijzen. Voordat we dit doen is het belangrijk dat we eerst een goed intu¨ıtief beeld hebben van wat deze getallen voorstellen. Dat doen we in dit hoofdstuk: alles wat hier wordt besproken is nog puur informeel. Maak je daarom geen zorgen over ‘vage’ definities en formules, het meer precieze werk komt later.
Merk op dat we hier g-adisch schrijven in plaats van p-adisch. g of p is een constante en stelt het grondtal voor; zo hebben de 10-adische getallen als grondtal 10. Later zal blijken dat het speciale geval dat g een priemgetal is, een belangrijke rol speelt. Voortaan als we p-adisch schrijven is p een willekeurig priemgetal; als er g-adisch staat, is g een willekeurig natuurlijk getal1 groter dan 1.
Door de tekst heen staan hier en daar oefeningen, die helpen je de stof beter te begrijpen. De antwoorden staan op pagina 61.
In dit werkstuk gebruiken we een decimale punt in plaats van een decimale komma, zoals in de wetenschappelijke literatuur gebruikelijk is.
1.1 Wat zijn g-adische getallen?
Voordat we de bizarre wereld van de g-adische getallen gaan verkennen, is het verhel- derend om eerst de bekende getallen eens nader te bekijken. Dan kunnen we daarna de analogie met de g-adische getallen gemakkelijker inzien.
We zijn gewend om met re¨ele getallen te werken, dat zijn getallen die als volgt kunnen worden geschreven (met eventueel een minteken ervoor).
an . . . a3a2 a1a0.a−1 a−2 . . . (1.1) Hier zijn ai de cijfers, niet-negatieve gehele getallen kleiner het grondtal2 g. De re¨ele
1 De natuurlijke getallen zijn de niet-negatieve gehele getallen, dus 0, 1, 2, 3, . . .
2 Voor het gemak gaan we voorlopig uit van grondtal 10.
veel cijfers hebben, en rechts oneindig veel. Bijvoorbeeld 1 = 0.25 = 0.25000 . . . is een
√ 4
re¨eel getal, net als π = 3.141592654 . . . en 100
2 = 141.42135 . . .. In het bijzonder zijn
alle gehele getallen, en alle breuken met gehele getallen in de teller en noemer3, ook re¨ele getallen. Andersom geldt het echter niet!
Het is van de meeste re¨ele getallen onmogelijk om hun getalwaarde exact te bepalen: ze zijn immers oneindig lang en ‘bijna’ allemaal onregelmatig. Nu liggen de meeste mensen daar niet wakker van. Het is duidelijk dat elk re¨eel getal willekeurig dicht benaderd kan worden door een getal met eindig veel cijfers; bijvoorbeeld 3.141592 is voor de meeste toepassingen een voldoende nauwkeurige benadering van π. Immers, twee re¨ele getallen die pas vanaf de zevende decimaal verschillen, liggen dicht bij elkaar, en nog dichter als ze pas vanaf de twintigste decimaal verschillen. Dit komt doordat in R de volgende limiet geldt:
lim
g−n = 0 (1.2)
en a0.a−1 a−2 . . . betekent niets anders dan a0g
i
+ a−1g−
+ a−2g−
+ . . . Hoe groter i,
des te kleiner de invloed van a−i g−
op de grootte van het getal.
In de volgende rij liggen twee opeenvolgende getallen steeds dichter bij elkaar. De rij
convergeert naar een limietwaarde ; die limietwaarde is een re¨eel getal.
300
310
314
314.1
314.15
314.159
314.1592
. . .
Het leuke is dat we met alleen deze kennis al een idee kunnen krijgen van wat g-adische getallen voorstellen. Het werkt namelijk net zo als bij de re¨ele getallen, alleen dan precies andersom! De g-adische getallen zijn getallen van de vorm
. . . a3 a2a1a0 .a−1a−2 . . . a−n (1.3)
lim
n→∞
gn = 0 (1.4)
Dit is wiskundig gezien natuurlijk onmogelijk omdat g > 1, maar omdat we nu nog informeel bezig zijn, maken we ons daar niet druk over. Ook stellen we: hoe verder een
3 Dit worden ook wel de rationale getallen genoemd.
cijfer naar links ligt, hoe minder invloed het heeft op de grootte van het getal. Zo liggen de opeenvolgende rationale getallen in de volgende rij steeds dichter bij elkaar.
0.003
0.013
0.413
1.413
51.413
951.413
2951.413
. . .
De rij convergeert 10-adisch gezien naar een limietwaarde ; deze limietwaarde is een 10- adisch getal.
Met deze nogal vreemde beschouwing van ‘grootte’ kunnen we verwachten dat er ook vreemde dingen gebeuren. Bekijk bijvoorbeeld het volgende rijtje dat 10-adisch gezien steeds dichter naar −1 nadert.
9 = −1 + 101
99 = −1 + 102
999 = −1 + 103
. . .
Volgens (1.4) is limn 10n
= 0, dus er moet wel gelden dat . . . 99999 = −1. Blijkbaar
kunnen positieve g-adische getallen een negatief (geheel) getal voorstellen! Later zal blijken dat alle tegengestelden van g-adische getallen zonder minteken geschreven kunnen worden. Het heeft daarom geen zin om negatieve getallen als − . . . a2a1a0 in te voeren,
want die bestaan allemaal al onder de g-adische getallen.
Voor de re¨ele getallen maakt het niet veel uit in welk grondtal je werkt; je kunt elk re¨eel getal in elk gewenst grondtal g ∈ N, g ≥ 2 schrijven. Bijvoorbeeld 1347 = 1024 + 256 +
64 + 2 + 1 = 10101000011 in grondtal 10 resp. 2. Bij de g-adische getallen blijkt het grondtal w´el uit te maken: je krijgt in sommige gevallen ´echt andere getallen als je op een ander grondtal overgaat.
In hoofdstuk 3 zullen we bewijzen dat er geen ‘nuldelers’ onder de g-adische getallen zijn, precies dan als g een priemgetal is. Nuldelers zijn getallen a en b ongelijk aan 0 waarvoor ab = 0, ofwel a = 0 en b = 0 . Het blijkt belangrijk te zijn dat er geen nuldelers
b a
voldoende dat g een natuurlijk getal groter dan 1 is.
Dan nog wat terminologie en afkortingen. Terloops hebben we de natuurlijke, de gehele, de rationale en de re¨ele getallen genoemd. De verzamelingen die uit precies al deze getal- len bestaan, duidt men aan met N, Z, Q resp. R. Wellicht ken je ook C, de verzameling complexe getallen. Later zullen we wat dieper ingaan op deze getalstelsels, evenals op het begrip verzameling.
De g-adische getallen die geen cijfers rechts van de komma hebben, noemen we de
g-adische gehele getallen. Volgens (1.3) zijn dit de getallen van de vorm
. . . a4 a3 a2a1a0 (1.5) De verzameling van alle g-adische gehele getallen noemen we Zg . Let op: welke getallen
deze verzameling bevat, hangt van het grondtal g af ! Er blijken zelfs oneindig veel verzamelingen Zg te zijn.
1.2 g-adisch rekenen
Het optellen en aftrekken in Zg gaat ongeveer hetzelfde als in R. We rekenen elements- gewijs en van rechts naar links, waarbij we naar links toe ‘overlenen’. Voor optelling in Z10 bijvoorbeeld houdt dat in dat je cijfer voor cijfer optelt, en als de som groter is dan
10, bijvoorbeeld 17, leen je de 1 van 17 over naar links zodat je 7 overhoudt. Hieronder
staan een paar voorbeelden van optellen en aftrekken in Z10 .
. . . 86951 +
. . . 26093
. . . 74801
. . . 95236 −
. . . 79565
. . . 00000
. . . 39802 −
. . . 60198
Je kunt op deze manier elk paar willekeurige g-adische gehele getallen a en b optellen of aftrekken. Op deze manier kun je van elke a de tegengestelde −a berekenen door a van
0 = . . . 00000 af te trekken, zoals in het laatste voorbeeld is gedaan. Ter controle kun je daar snel berekenen dat inderdaad a + (−a) = 0.
Oefening 1.2.1.
a. Bereken exact de 10-adische uitkomst van 0 − 1. Komt dit overeen met wat we op pagina 5 hebben geconstateerd over −1?
b. Benader in 5 decimalen nauwkeurig: . . . 41342 + . . . 30243, maar nu in grondtal
c. Stel dat de twee getallen die je bij b hebt opgeteld in 10 decimalen nauwkeurig waren gegeven. Had dat invloed kunnen hebben op de 5 decimalen die je daar hebt berekend?
Het lijkt er dus op dat als g-adische getallen a en b in n decimalen nauwkeurig bepaald zijn, we ook a + b ook in n decimalen nauwkeurig kunnen berekenen. Dat is handig, want als n naar oneindig gaat, weten we zeker dat a + b naar een g-adisch getal convergeert. In R zitten daar wat haken en ogen aan. Neem bijvoorbeeld de re¨ele getallen a = 2.19635 . . . en b = 3.23864 . . ., een simpele berekening leert dat a + b = 5.43499 . . .. Liggen deze zes
Tabel 1.2: Vermenigvuldigen en delen in Z10
. . . 22901
. . . 37586 ×
. . .37406
. . . 3208
. . . 505
. . . 07
. . . 3 +
. . .56986
3 / . . . 0000001 . . . 6667
21 −
. . .9999980
180 −
. . .9999800
1800 −
. . .9998000
18000 −
. . .
cijfers nu vast? Nee, dat hoeft niet. Stel dat we a en b iets beter benaderen, we vinden bijvoorbeeld a = 2.196358277 . . . en b = 3.238643530 . . .. Dan is a + b = 5.435001807 . . .; je ziet dat de eerste vijf decimalen niet allemaal overeenkomen met die van de eerder bepaalde waarde van a + b. In het algemeen is het zo dat tot en met de eerste decimaal van rechts die geen negen is, de cijfers onzeker zijn in een benadering in R. In Zg hebben we daar geen last van, omdat rechts altijd een eindig aantal decimalen staat.
We kunnen ook vermenigvuldigen in Zg , dit gaat net zoals in R. Zie de linker som in Tabel 1.2.
‘invloedrijke’ cijfers rechts staan. Je wilt eerst het meest rechtse cijfer weg hebben, in dit geval een 1. Dat kan, want 3 ×7 = 21; we zetten dus een 7 bij de uitkomst. Nu berekenen we 1 −21 = . . . 9999980 (ga maar na). Vervolgens willen we de 8 wegpoetsen, dit doen we met 3 × 6 = 18. We zetten daarom een 6 neer bij de uitkomst van het quoti¨ent, links van
de 7 die er al stond. (Zie je waarom?) Aftrekken levert . . . 9999800, weer hetzelfde getal als daarnet, maar nu met een nul erbij! De 8 kunnen we weer wegpoetsen met 3 × 6, dan krijgen we . . . 9998000, etc. Bij het quoti¨ent komen er steeds meer zessen bij, terwijl bij
de rest een steeds langere staart van nullen groeit; de rest wordt volgens de 10-adische beschouwing van grootte (zie vgl. (1.4)) steeds kleiner en nadert naar 0. Daarom is
3 = . . . 666667 in Z10 . En inderdaad, als we ter controle 3 × . . . 666667 berekenen komt
er 1 uit.
Bij het delen in Zg kom je al snel in de problemen. Probeer in Z10 maar eens 1 te
berekenen met een staartdeling. Je wilt net zoals in het vorige voorbeeld allereerst het meest rechtse cijfer a0 van het quoti¨ent zoeken waarmee je de 1 kan wegpoetsen. Dat is
echter onmogelijk, want a0 × 6 is altijd even en kan dus nooit 1 zijn! We kunnen nog wel andere dingen proberen, maar dat heeft geen zin. Immers, als x = 1 is 6x = 1; deze vergelijking is niet oplosbaar in Z10 , want het meest rechtse cijfer in 6x is even en in 1 is het oneven.
Voor delingen onder de g-adische getallen blijkt het handig zijn om kommagetallen toe te staan, die we al gezien hebben bij vgl. (1.3). De verzameling van deze g-adische kommagetallen noemen we Qg . Eigenlijk is dat wiskundige niet helemaal correct, want Qg heeft alleen ‘zin’ als g een priemgetal is. In hoofdstuk 4 zullen we zien waarom. Daar zullen we ons nu echter niet druk om maken.
is 1
zoals we gezien hebben. Dus 6x = 1. Dit konden we doen doordat 5 × 2 = 10 ≡ 0
(mod 10).4
Het optellen en vermenigvuldigen in Qg gaat hetzelfde als in Zg , waarbij je rekening moet houden met de plaats van de komma. Naar analogie van de voorbeelden op pagina
6 en 7 is bijvoorbeeld . . . 391.42 + . . . 869.514 = . . . 260.934, en . . . 2290.1 × . . . 375.86 =
. . . 56.986. Merk op dat het in R net zo gaat.
Delen door middel van een staartdeling in Qg gaat echter mis als g geen priemgetal is. Dat komt doordat er dan nuldelers in Zg zitten.
Oefening 1.2.2.
a. Bereken exact in Z5: (Let op: werk dus in grondtal 5.)
1421 × . . . 222222220413
Welk getal in Z stelt dit product voor (in grondtal 5)?
b. Bereken, indien mogelijk, 1 in Z10 . Heeft dit quoti¨ent een repeterende staart?
Dezelfde opdracht voor 1 .
Met andere woorden, is er een paar getallen uit de tafel van 7 met hetzelfde rechtercijfer, zodat een bepaald cijfer dus op meerdere manieren kan worden weggepoetst? En hoe zit dat met de tafel van 8?
1.3 Er zitten breuken verstopt in Qg
We hebben al gezien dat niet alle getallen in Qg per se als naar links oneindig doorlopende getallen hoeven te worden geschreven. Er bleken ook ‘normale’ getallen in te zitten, getallen die we al kenden. Bijvoorbeeld alle gehele getallen, en sommige rationale getallen
zoals 15.3, 1
en 1 . Dit zijn allemaal getallen die in de g-adische vorm een repeterende
4 Maak je geen zorgen als je niet weet wat (mod 10) is, hier komen we in hoofdstuk 3 op terug.
5 In de veronderstelling dat er geen rekenfouten zijn gemaakt.
1.3. ER ZITTEN BREUKEN VERSTOPT IN QG
staart hebben, namelijk . . . 00015.3, . . . 6667 en . . . 2857142857143. Men kan bewijzen dat een getal a uit Qg precies dan als getal in Q kan worden geschreven als a in de g-adische vorm een repeterende staart heeft. Er zijn natuurlijk heel veel onregelmatige g-adische getallen, deze kunnen dus niet als rationaal getal worden geschreven, en, zo kan men bewijzen, zelfs niet als re¨eel getal.
We focussen we ons nu op repeterende g-adische getallen. Hoe kunnen zij als rationaal
Voorbeeld 1.3.1. We nemen het 10-adische getal x = ...77777 en zijn benieuwd welk rationaal getal x voorstelt. Dat is niet moeilijk. Eerst berekenen 10x = . . . 77770. Ver- volgens berekenen we
−9x = x − 10x = . . . 77777 − 77770 = . . . 00007 = 7
waaruit volgt dat
x = −7
9
Wat we hier hebben gedaan was vrij intu¨ıtief en informeel; we zullen eens nader beschouwen wat we allemaal gebruikt hebben. Het blijkt dat de somformule van de meetkundige reeks hier belangrijk is. Een meetkundige reeks heeft te maken met een on- eindig lange getallenrij van de vorm a0 , a1, a2, a3, . . . waarin de opeenvolgende elementen steeds met dezelfde factor worden vermenigvuldigd. Er geldt dus steeds dat ai+1 = kai voor een zekere re¨ele constante k = 1. Je kunt makkelijk inzien dat de getallenrij ook geschreven kan worden als ak0, ak1, ak2, ak3, . . . waarbij a = a0 .
We willen alle oneindig veel elementen van de rij bij elkaar optellen. Of daar een
echt getal uitkomt of niet zien we later wel. Eerst beschouwen we een benadering van wat we willen berekenen, namelijk de som van de eerste n + 1 elementen. Deze noemen we xn . Dan berekenen we kxn , en vervolgens trekken we de twee van elkaar af. Hierbij vallen op twee na alle termen tegen elkaar weg.
xn = ak0 + ak1 + ak2 + ak3 + . . . + akn
(1 − k)xn = ak0 − akn+1
Hieruit volgt dat
xn =
a(k0 kn+1 )
(1.6)
1 − k
Deze deling kunnen we uitvoeren omdat k = 1.
We zijn niet op zoek naar een benadering, maar naar de exacte waarde van limn→∞ xn =
ak0 + ak1 + ak2 + . . . Om deze te bepalen laten we n in (1.6) naar oneindig gaan. Er zijn dan twee6 mogelijkheden. Als |k| > 1 gaat kn+1 naar (min) oneindig; dan divergeert xn
n+1
zodat x∞ geen getal kan zijn. Als −1 < k < 1 gaat k
a(k0 − 0) a
lim
n→∞
xn =
1 − k
=
1 − k
(1.7)
Een som van oneindig veel termen kan dus een rationaal getal opleveren! Dat wisten we eigenlijk al, want bijvoorbeeld 0.33333 . . . in grondtal 10 is niets anders dan een meetkundige reeks met a = 0.3 en k = 0.1. Uit (1.7) volgt dat
0.33333 . . . =
0.3
=
1 − 0.1
0.3 1
=
0.9 3
Nog een voorbeeld: 0.142857142857 . . . is een meetkundige reeks met a = 0.142857 en
k = 10−6 (ga dat na ), dus
0.142857
=
1 − 10−6
0.142857 1
=
0.999999 7
Hierboven hebben we gesteld dat de som van de meetkundige reeks alleen oplosbaar is
n+1
als |k| < 1, want alleen dan is limn→∞ k
= 0. Bij g-adische getallen is het echter
juist andersom, want volgens (1.4) gaat kn+1 naar 0 als k > 1! Daarom mogen we (1.7)
ook op repeterende getallen van Qg toepassen. Als voorbeeld nemen we weer . . . 77777 in Z10 , dit is een meetkundige reeks met a = 7 en k = 10.
. . . 77777 =
=
1 − 10 9
Je ziet dat er een negatieve breuk uitkomt! Omdat altijd geldt dat k > 1 en a > 0 is dat voor alle g-adische getallen het geval. Uiteraard zitten er ook positieve breuken in Qp , je kunt namelijk met de methode van pagina 6 de tegengestelde van bijv. . . . 77777 berekenen.
Alle g-adische getallen met repeterende staart zijn ook rationaal getal. Een voorbeeld laat zien hoe het algemene bewijs verloopt. We rekenen weer in Q10 .
. . . 2780527805139.46 = 103 . . . 2780527805 + 139.46 = 103 27805
1 − 105
+ 139.46
= 27805000 − 13945860.54 =
−99999
−1385913946
9999900
Men kan bewijzen dat alle rationale getallen als g-adisch getal te schrijven zijn, ofwel,
Q ∈ Zg voor alle g ∈ N, g > 1. Dat doen we hier echter niet.
6 Eigenlijk is er nog een derde mogelijkheid, namelijk k = −1. Dit is een geval apart, we bespreken het hier niet.
Hoofdstuk 2 Algebraïsche structuren en getalsystemen
2.1 Algebra in een notendop
Voor veel mensen betekent algebra zoiets als ‘rekenen met letters’. Algebra is echter veel meer dan dat. Heel globaal houdt de algebra zich bezig met het bestuderen van struc- tuur, zoals symmetrie¨en van regelmatige veelvlakken en de structuur van de verzameling priemgetallen in andere getalstelsels. De basisobjecten waar we altijd van uitgaan zijn verzamelingen waar inwendige bewerkingen op zijn gedefinieerd.
We geven een voorbeeld. Alle mensen op aarde vormen een verzameling V . Alle Nederlanders vormen een deelverzameling W daarvan, en alle Nederlanders met blauwe ogen vormen daar weer een deelverzameling X van. Een willekeurige Nederlander met blauwe ogen is een element van X , en dus ook van W en van V . Natuurlijk weten wij dat een mens weer is opgebouwd uit achtereenvolgens organen, cellen, organellen, moleculen etc., maar wiskundig gezien wordt de mens in V , W en X als element beschouwd.
Een verzameling wordt vaak afgekort met een hoofdletter, en aangeduid met ac- colades waarbinnen een wiskundige omschrijving van de verzameling staat. Bijvoor- beeld A = {1, 3, 105} is de verzameling bestaande uit de drie getallen 1, 3 en 105. De
volgorde waarin de elementen staan maakt niet uit, dus A = {1, 3, 105} = {105, 1, 3}. Verzamelingen mogen oneindig veel elementen bevatten, denk bijvoorbeeld aan N =
{0, 1, 2, 3, 4, 5, . . .}. Het symbool ∈ wordt uitgesproken als ‘. . . is een element van de
1 Bron: [8]
verzameling . . . ’, of kortweg als ‘in’. Als gegeven is dat x ∈ A weet je dus dat x ´e´en van de drie getallen 1, 3 en 105 is. Als x ∈ N is x een natuurlijk getal.
In het algemeen wordt een verzameling V als volgt aangeduid:
V = {f (x) | omschrijving van x}
Dit is de verzameling van precies alle elementen f (x) waarvoor x aan de omschrijving rechts van de verticale streep voldoet. Bijvoorbeeld {2x + 1 | x ∈ N} is de verzameling van alle 2x + 1 waarvoor x een natuurlijk getal is: de oneven natuurlijke getallen dus.
Met V≥k bedoelen we de verzameling W = {x ∈ V | x ≥ k}.
Operaties, samenstellingswetten en inwendigheid Laat V1 en V2 twee verza- melingen zijn. Een operatie of bewerking van V1 naar V2 is een functie waarmee een combinatie van elementen van V1 wordt afgebeeld naar een element van V2. Dit klinkt wat ingewikkeld, maar bijvoorbeeld optellen en vermenigvuldigen zijn operaties van N naar N. Zo wordt 4 + 7 afgebeeld naar 11. We noemen + en × binaire operaties, omdat het altijd om een combinatie van twee elementen gaat.
Er zit alleen een addertje onder het gras: samenstellingswetten mogen vaak alleen gecombineerd worden als ze inwendig zijn. Dat bijvoorbeeld + en × inwendig zijn in N, betekent dat a + b ∈ N resp. a × b ∈ N voor alle a, b ∈ N. Stel dat de operatie × niet
inwendig was in N, konden we er niet vanuit gaan dat ce een natuurlijk getal was, ook al waren c en e dat wel. Dit zou betekenen dat we niet zonder meer mochten beweren dat ce+b = b+ce. Gelukkig zijn + en × wel inwendig in N, zoals je gemakkelijk kunt nagaan. Daardoor zijn alle operaties samengesteld uit + en ×, zoals a(b + c), automatisch ook inwendig.
‘Aftrekken’ is een voorbeeld van een operatie die niet inwendig is in N. Bijvoorbeeld
5 − 7 = −2 is kleiner dan 0 en zit dus niet in N.
Om dubbelzinnigheden te voorkomen, gebruiken we in formele gedeelten overal waar dat nodig is haakjes. Alleen als er echt geen verwarring kan ontstaan, laten we ze weg. Zo gaat vermenigvuldiging bij afspraak vo´or optelling bij het ontbreken van haakjes. Verder laten we het ×-teken voor de overzichtelijkheid vaak weg, of schrijven we • ervoor in de plaats.
2.2 Symbolen
We zullen in dit werkstuk hier en daar gebruik maken van symbolen. E´en ervan zijn we al tegengekomen, namelijk ∈. Er zijn nog veel meer symbolen met een vaste betekenis,
Tabel 2.1: Enkele belangrijke symbolen
Symbool
Lees dit als:
∈
. . . (is een element) van de verzameling . . .
∀
Voor alle . . .
∃
Er is een . . .
:
. . . zodat geldt . . . ; of: . . . geldt het volgende: . . .
⊂
:=
. . . is per definitie gelijk aan . . .
⇒
. . . als . . . dan . . .
⇔
. . . dan en slechts dan als . . .
degene die wij gebruiken (behalve de bekende zoals ≥) hebben we opgesomd in Tabel
2.1 op pagina 13. De symbolen op zichzelf betekenen eigenlijk niets; ze worden altijd gecombineerd met andere symbolen.
Een paar voorbeelden van wat we met deze symbolen kunnen uitdrukken, maken veel duidelijk.
• ∀a ∈ A : a < 106 betekent: ‘Voor alle elementen a van de verzameling A geldt: a
is kleiner dan 106.’
zodat voor alle a in V geldt: als a groter is dan x, dan is a groter dan y.’ We doen een paar opmerkingen over Tabel 2.1.
• A := B of B =: A betekent: we kennen B al, en cre¨eren nu een A die per definitie gelijk is aan B.
• A ⇒ B betekent: Als bewering A waar is, dan volgt daaruit dat bewering B ook waar is. Het zegt dus niets over de waarheid van A.
• A ⇔ B betekent dat A en B of beide waar of beide onwaar zijn. Dit wordt vaak uitgesproken als: A is waar dan en sl´echts dan als B waar is.
• V ⊂ W betekent dat V een deelverzameling is van W of gelijk is aan W . In symbolen: ∀a ∈ V : a ∈ W . Je kunt gemakkelijk inzien dat uit V ⊂ W en W ⊂ V volgt dat V = W .
Optelling
Tabel 2.2: Enkele samenstellingswetten
1) Inwendigheid van de optelling. Als a, b ∈ V , dan is ook a + b ∈ V .
2) Associativiteit van de optelling. (a + b) + c = a + (b + c)
3) Nulelement. Er is een 0 ∈ V zodat a + 0 = 0 + a = a.
4) Tegengestelde. Voor alle a ∈ V is er een tegengestelde −a ∈ V , zodat a + (−a) = (−a) + a = 0.
5) Commutativiteit van de optelling. a + b = b + a
Vermenigvuldiging
2) Associativiteit van de vermenigvuldiging. (a × b) × c = a × (b × c)
3) Eenheidselement. Er is een 1 ∈ V zodat a × 1 = 1 × a = a.
4) Inverse. Voor alle a ∈ V, a = 0 is er een inverse a−1 ∈ V , zodat a × a−1 =
a−1 × a = 1.
5) Commutativiteit van de vermenigvuldiging. a × b = b × a
Combinatie
6) Distributiviteit. a(b + c) = ab + ac (links-distributiviteit), ´en (a + b)c = ac + bc
(rechts-distributiviteit).
7) Nul keer iets is nul. a × 0 = 0 × a = 0
8) V bevat geen nuldelers. Er kan alleen maar gelden dat ab = 0 als minstens
´e´en van beide a of b nul is.
2.3 Ringen en Lichamen
De ring en het lichaam zijn voorbeelden van algebra¨ısche structuren. Een algebra¨ısche structuur (V, +, ×) is een verzameling V waarop twee binaire operaties + en × zijn gedefinieerd, die aan bepaalde samenstellingswetten voldoen.2 Hoewel + en × niet per
se overeen hoeven te komen met de bekende optelling en vermenigvuldiging, is dat in dit werkstuk wel altijd zo. Een voorbeeld van een algebra¨ısche structuur is (N, +, ×). Op pagina 12 hebben we al een paar samenstellingswetten voor N gezien. In Tabel 2.2 op
Ook 0 en 1 hoeven niet per se overeen te komen met de bekende nul en ´e´en. In de algebra stellen het zelfs geen getallen voor. In dit werkstuk komen ze daarmee echter wel altijd overeen.
We zien drie soorten rekenregels in Tabel 2.2. Vijf regels gaan over de optelling, vijf soortgelijke regels gaan over vermenigvuldiging. De laatste drie regels gaan over de
2 Er zijn ook andere soorten algebra¨ısche structuren, maar die bestuderen we hier niet.
interactie tussen optellen en vermenigvuldigen.
Oefening 2.3.1.
a. Kunnen er algebra¨ısche structuren bestaan waarvoor wel de regels 7) en 8)
gelden, maar niet 3) voor optelling?
b. Welke van de samenstellingswetten uit Tabel 2.2 gelden voor V = N?
c. Dezelfde vraag voor Z, Q en R. Als je kunt rekenen met complexe getallen, kun je de vraag ook voor C beantwoorden.
Er zijn veel verschillende soorten algebra¨ısche structuren, afhankelijk van het aantal ope- raties en van de samenstellingswetten waaraan wordt voldaan. Veelgebruikte structuren hebben een naam gekregen; wij noemen er hier drie. De nummers verwijzen weer naar Tabel 2.2.
• Een algebra¨ısche structuur met een nulelement, waar optelling en vermenigvuldi- ging inwendig en associatief zijn en de optelling bovendien commutatief is, en waar de distributiviteit geldt, noemen we een halfring. Dit is dus een structuur die in
• Een halfring waarin bovendien ieder element een tegengestelde heeft, wordt een
ring genoemd. Dit is dus een halfring waar 4) geldt voor +.
• Een ring met een eenheidselement, waarin ieder element een inverse heeft en waarin bovendien vermenigvuldiging commutatief is, heet een lichaam. Dit is dus een ring waar 3), 4) en 5) gelden voor ×.
De begrippen ring en lichaam zullen we later nog vaak nodig hebben, daarom hebben we hun eigenschappen overzichtelijk in Tabel 2.4 gezet. Deze eigenschappen geleden in ieder geval, meer mag ook. Zo is elk lichaam automatisch ook een ring.
We kunnen bij de naam van een algebra¨ısche structuur de toevoegingen commuta- tieve, met 1 en zonder nuldelers plaatsen om aan te geven dat de regels 5) en 3) voor ×, en regel 8) gelden.3 Bijvoorbeeld een commutatieve ring met 1 waarvoor ook nog eens
ieder element een inverse heeft, is hetzelfde als een lichaam.
Oefening 2.3.2.
a. Ga na dat uit je antwoord bij opgave 2.3.1.a. volgt dat (N, +, ×) een commu- tatieve halfring met 1 zonder nuldelers is.
b. Welke algebra¨ısche structuren zijn Z, Q, R (en C)?
Het leuke is dat met enkel en alleen de samenstellingswetten uit Tabel 2.2 heel veel
3 Commutatieve gaat dan dus niet over optelling.
Tabel 2.4: Ring en Lichaam
Structuur
Samenstellingswetten
+: 1), 2), 3), 4), 5)
×: 1), 2); 6)
Lichaam
+: 1), 2), 3), 4), 5)
×: 1), 2), 3), 4), 5); 6)
(vaak zeer ingewikkelde) stellingen kunnen worden bewezen. Een aantal van de meest eenvoudige stellingen met bewijs kun je vinden in hoofdstuk 4 van [5]. Als bewezen is dat een stelling geldt voor bijvoorbeeld elke ring, mag deze op alle bekende ringen worden toegepast, bijvoorbeeld op Z, Q, R en C. Dat is de kracht van de algebra.
2.4 Enkele stellingen over algebra¨ısche structuren
In deze paragraaf bewijzen we drie stellingen die we later nog handig kunnen gebruiken. Bovendien geven de bewijzen een goed beeld van hoe je met algebra¨ısche structuren kunt werken. Als je algemene stellingen over bijvoorbeeld lichamen wilt bewijzen, kun je je niet beroepen op je intu¨ıtie over de lichamen Q, R en C die je al kent. Je wilt namelijk dat de stellingen gelden voor alle structuren die aan de eisen in Tabel 2.4 voldoen.
In dit werkstuk hebben we ervoor gekozen niet alle stellingen zo precies te bewijzen
In de volgende stelling mag je voor ◦ zowel + als × invullen. Als boven een =-teken
bijvoorbeeld 2)◦ staat, betekent dit dat deze stap volgt uit samenstellingswet 2) voor operatie ◦ uit Tabel 2.2.
Stelling 2.4.1. Voor elke commutatieve ring (V, +, ×) geldt:
∀a, b, c, d ∈ V : (a ◦ b) ◦ (c ◦ d) = (a ◦ d) ◦ (c ◦ b)
Bewijs. Voor willekeurige a, b, c, d ∈ V geldt:
2)◦
5)◦
(a ◦ b) ◦ (c ◦ d) = a ◦ b ◦ (c ◦ d) = a ◦ (c ◦ d) ◦ b
5)◦
2)◦
2)◦
= a ◦ (d ◦ c) ◦ b = a ◦ d ◦ (c ◦ b) = (a ◦ d) ◦ (c ◦ b)
Dat stelling 2.4.1 geldt is intu¨ıtief meteen duidelijk, maar het kost toch wat moeite om hem te bewijzen!
De volgende stelling voorkomt dat we verderop in dit werkstuk zowel de rechts- als de links-distributiviteit moeten bewijzen.
Stelling 2.4.2. Voor elke commutatieve structuur (V, +, ×) geldt: als de links-distributiviteit waar is, dan ook de rechts-distributiviteit.
Hieruit volgt:
a(b + c) = ab + ac (2.1)
(b + c)a
5)
= a(b + c)
(2.1)
= ab + ac
5)
= ba + ca
dus (b + c)a = ba + ca, de rechts-distributiviteit geldt dan dus ook. Hiermee is de stelling bewezen.
De laatste stelling gaat over eigenschap 7) uit Tabel 2.2 die zegt dat nul keer iets altijd nul is. Dit blijkt namelijk in elke commutatieve ring te gelden.4 In het bewijs laten we de verwijzingen boven de =-tekens weg; probeer zelf te achterhalen welke samenstel- lingswetten we gebruiken.
4 Het geldt zelfs voor elke ring, ook voor niet-commutatieve ringen. Geheel analoog aan het bewijs hier kun je namelijk aantonen dat 0 = 0 × a. In dit werkstuk vormt het echter geen beperking als de ring commutatief is.
∀a ∈ V : a × 0 = 0 × a = 0
Bewijs. Laat a een willekeurig element zijn van V . Er geldt:
0 = (a × 0) + −(a × 0) = (a(0 + 0) + −(a × 0) = a × 0 + a × 0 + −(a × 0)
= a × 0 + (a × 0 + −(a × 0) = a × 0 + 0 = a × 0
dus a × 0 = 0. Wegens de commutativiteit van × is dan ook 0 × a = 0, waarmee de stelling bewezen is.
2.5 Getalsystemen als algebra¨ısche structuren
We hebben tot nu toe zeven verschillende getalsystemen genoemd, nu zullen we daar wat meer over zeggen. De volgorde waarin ze staan, namelijk N, Z, Q, R, C, Zp , Qp , is niet willekeurig gekozen. Behalve Zp wordt elk van deze getalsystemen namelijk uit haar voorganger opgebouwd. Dat R wordt geconstrueerd vanuit Q is niet meteen duidelijk, maar in de wiskunde kunnen de re¨ele getallen gedefinieerd worden als limieten
van convergerende rijtjes rationale getallen. Zo is π/4 = arctan(1) = 1 − 1 + 1 −
1
7 + . . . Je kunt R ook construeren als oneindige decimale breuken, zoals we al hebben
aangeduid in hoofdstuk 1. Dat heeft wel twee bezwaren. Ten eerste moet je soms
verschillende decimale breuken identificeren. Zo is 1 = 0.99999 . . . Dat is lastig, maar niet onoverkomelijk. Ten tweede kun je je afvragen: “Als ik nu 8 vingers had, zou R er dan anders uit hebben gezien?” Gelukkig kan men bewijzen dat het voor de structuur van R niet belangrijk is welk grondtal je kiest.
Verder is elk hier genoemde getalstelsel deelverzameling van alle daaropvolgende stelsels (behalve Zp en Qp ), zoals je gemakkelijk intu¨ıtief kunt inzien.
Z ⊂ Zp
N ⊂ Z ⊂ Q ⊂ R ⊂ C
∩ ∩
Q ⊂ Qp
In het rechter schema zien we dat Z deelverzameling is van Zp , Q en Qp , en dat Qp de drie andere verzamelingen omvat. Maar bijvoorbeeld de inclusie Q ⊂ Zp is niet waar. Bijvoorbeeld 1 ∈ Q zit niet in Zp . Hier komen we in hoofdstuk 4 op terug.
N heeft in de volgorde die we aanhouden geen ‘voorganger’, maar je moet toch ergens beginnen. N wordt axiomatisch gedefinieerd en niet opgebouwd uit enig ander getalstelsel. Het staat aan de basis van alle ons bekende getalstelsels.
2.5.1 N, de Natuurlijke getallen
N is de verzameling natuurlijke getallen {0, 1, 2, 3, . . .}. Haar belangrijkste basiseigen- schappen zijn dat er een beginelement is (dat we 0 noemen), en dat ieder natuurlijk
een commutatieve halfring met 1 zonder nuldelers is.
Op het eerste gezicht hebben de natuurlijke getallen niet veel met p-adische getallen te maken, maar uiteindelijk is ook Zp , net als alle andere getalsystemen, gebaseerd op N.
2.5.2 Z, de Gehele getallen
Z is de verzameling gehele getallen {. . . , −3, −2, −1, 0, 1, 2, 3, . . .} bestaande uit de na- tuurlijke getallen, en voor elk natuurlijk getal zijn tegengestelde (0 is zijn eigen tegen- gestelde). Dat wil zeggen: Z = {a, −a | a ∈ N}.
Het grootste verschil tussen N en Z is dat Z geen beginelement heeft, en dat ieder getal een tegengestelde heeft. De gehele getallenlijn is als het ware symmetrisch ten opzichte van de 0.
We hebben N en Z formeel ingevoerd en bewezen dat ze een commutatieve halfring resp. ring met 1 zonder nuldelers vormen. Dit hebben we niet opgenomen in dit verslag. Men definieert Z op een heel andere manier dan N, en stellingen worden op een heel andere manier bewezen. Dit komt doordat N ‘uit het niets’ wordt opgebouwd, terwijl Z kan worden geconstrueerd vanuit N. De rekenregels die voor N bewezen zijn, kunnen handig worden gebruikt om stellingen over Z te bewijzen. Dit gaat voor de andere getalsystemen net zo.
In de uitbreiding van N naar Z hebben we geen eigenschappen gebruikt die spe- cifiek zijn voor N. Daarom kunnen we deze methode gebruiken om elke willekeurige commutatieve halfring met 1 uit te breiden naar een ring.
2.5.3 Q, de Rationale getallen
Q is de verzameling rationale getallen, ofwel breuken a , met in de teller en noemer een
geheel getal. Dat wil zeggen: Q = { a | a, b ∈ Z}.
In tegenstelling tot Z heeft een element in Q geen opvolger. Voor ieder paar a, b ∈ Q
met positieve lengte’ in de rationale getallenlijn.
In hoofdstuk 4 zullen we Q formeel construeren en bewijzen dat het een lichaam is.
2.5.4 R, de Re¨ele getallen
R is de verzameling re¨ele getallen, dat zijn alle getallen op de getallenlijn. R komt overeen met de verzameling van alle naar links eindig en naar rechts oneindig doorlopende decimale breuken in een willekeurig grondtal g ∈ N≥2 . Bijvoorbeeld 1.01100111000 . . . in grondtal 2, en 105π = 314159.2 . . . in grondtal 10 zijn re¨ele getallen. Formeler:
∀g ∈ N≥2 :
i=k
R = n X ai gi k ∈ Z, ∀i ∈ Z : (ai ∈ N, 0 ≤ ai ≤ g − 1)o
−∞
Een reden om N uit te breiden naar Z en Q is omdat er zo een ‘mooiere’ algebra¨ısche structuur ontstaat die aan meer axioma’s voldoet. Met Q is de mooiste structuur die we kennen (het lichaam) bereikt, dus we moeten andere redenen hebben om deze nog eens uit te breiden naar R en C.
We hebben eerder beweerd dat er geen ‘gaten’ in de rationale getallenlijn zitten: elk getal op de getallenlijn kan oneindig dicht benaderd worden door rationale getallen. Maar voor veel toepassingen, bijvoorbeeld in de analyse, blijkt benaderen niet goed genoeg te zijn. Daar is het namelijk belangrijk dat je limieten kunt nemen. Bovendien blijken
belangrijke re¨ele getallen zoals √2, e en π niet rationaal te zijn.
De verzameling complexe getallen kan worden geschreven als C = {a + bi | a, b ∈ R}. De constante i is een zogenaamd imaginair getal. Per definitie is i2 = −1. Blijkbaar is i geen re¨eel getal, want in R zijn kwadraten altijd positief. Met i mag wel gerekend worden alsof het een re¨eel getal is.
De belangrijkste reden om C in te voeren is omdat zo een algebra¨ısch gesloten getal- systeem ontstaat. Dat wil zeggen dat er voor elke functie f van de vorm
f (x) = a0x0 + a1x1 + a2x2 + . . . + an xn (ai ∈ C, n ∈ N )
een x ∈ C is zodat f (x) = 0. Zo’n x heet een nulpunt van f (x). Dat R niet algebra¨ısch gesloten is, is gemakkelijk in te zien: bijvoorbeeld f (x) = x2 + 3 heeft geen nulpunt in
R. In C is bijvoorbeeld i√3 een nulpunt van deze functie.
Dat C algebra¨ısch gesloten is, bewijzen we hier niet. In hoofdstuk 8 van [5] staat een bewijs dat ook voor 6VWO-leerlingen te begrijpen is.
2.5.6 Zp en Qp , de p-adische gehele en gebroken getallen
Wat Zp en Qp intu¨ıtief inhouden hebben we uitgebreid besproken. In hoofdstuk 3 en 4 zullen we ze formeel defini¨eren.
In hoofdstuk 3 zullen we bewijzen dat Zg , voor elk geheel grondtal g ≥ 2, een
commutatieve ring met 1 is, en bovendien zonder nuldelers als g priem is. In hoofdstuk
4 bewijzen we dat Qp voor elk priemgetal p een lichaam is. Dan blijkt dat we Qp op een
met in
de teller en noemer p-adische gehele getallen.
n a o
∀p ∈ P : Qp = b
a, b ∈ Zp , b = 0
Hier is P de verzameling priemgetallen. Uiteindelijk bewijzen we dat alle elementen van
Qp geschreven kunnen worden als p-adische kommagetallen van de vorm
. . . a3a2a1a0 .a−1a−2 . . . a−n
Bij deze schrijfwijze kunnen we ons tenminste iets voorstellen, en bovendien kunnen we op deze manier gemakkelijk met de getallen rekenen.
Hoofdstuk 3 Precieze invoering van de ring Zg
3.1 Voorbereiding
In dit hoofdstuk voeren we Zg formeel in, waarna we bewijzen dat het een commutatieve ring met 1 is, en bovendien zonder nuldelers als g priem is. Voordat we dat doen, willen we eerste intu¨ıtief inzien waarom dit zo is. Dat doen we in deze paragraaf. Let op: alle
‘bewijzen’ hier zijn nog informeel en niet strikt volgens wiskundige regels.
betekent intu¨ıtief hetzelfde als
. . . a3a2a1 a0
. . . + a3g3 + a2g2 + a1g1 + a0g0 (3.1)
Dit korten we voortaan af als1
∞
X ai gi (3.2)
i=0
In §1.2 hebben we gezien dat twee g-adische getallen cijfer voor cijfer opgeteld worden, dus
∞ ∞ ∞
X ai gi + X bi gi = X(ai + bi )gi (3.3)
i=0
i=0
i=0
Hier stuiten we echter op een probleem: de nieuwe cijfers ai + bi kunnen groter zijn dan g − 1. We kunnen nu naar links ‘overlenen’ om er een echt g-adisch getal van te maken, maar dan hebben we geen simpele formule voor optelling meer. Het hangt immers van de specifieke waarden van alle ai en bi af of er overgeleend moet worden, en ook van alle vorige keren dat is overgeleend. Daarom nemen we voorlopig maar voor lief dat sommige cijfers te groot zijn.
1 P is het zogenaamde sommatie-teken. Lees formule (3.2) als: de som van alle termen ai gi waarbij
Het is nu makkelijk in te zien dat de optelling commutatief is. Alle ai en bi zijn namelijk natuurlijke getallen waarvoor de commutativiteit geldt, dus
∞ ∞ ∞
∞ ∞ ∞
X ai gi + X bi gi = X(ai + bi )gi = X(bi + ai )gi = X bi gi + X ai gi
i=0
i=0
i=0
i=0
i=0
i=0
Voor het gemak noteren we P∞
ai gi voortaan als [ai ], analoog hieraan schrijven we
[bi ] en [ci ]. Zo stelt bijvoorbeeld [0] een oneindige rij nullen voor.
Ook de associativiteit van de optelling is gemakkelijk in te zien.
[ai ] + [bi ] + [ci ] = [ai + bi ] + [ci ] = (ai + bi ) + ci
= ai + (bi + ci ) = [ai ] + [bi + ci ] = [ai ] + [bi ] + [ci ]
Het bestaan van een nulelement is n´og eenvoudiger aan te tonen; immers, [ai ] + [0] = [ai + 0] = [ai ]
en wegens de commutativiteit van + is ook [0] + [ai ] = [ai ].
tussen 0 en g − 1) een ´echt g-adisch getal is. We kunnen daarom niet gewoon [−ai ]
nemen.
Oefening 3.1.1. Op pagina 6 hebben we van een g-adisch getal de tegengestelde be- rekend door het van 0 af te trekken. Wat is volgens deze methode in het algemeen de tegengestelde van . . . a3a2a1a0 ?
We vermoeden dus dat [bi ] de tegengestelde is van [ai ], waarbij b0 = g−a0 en bi = g−ai −1 voor de overige i. Als we [ai ] + [bi ] berekenen komt er [ci ] uit, met c0 = g en ci = g − 1 voor i > 0. Op het eerste gezicht lijkt dit niet veel op 0, maar we kunnen bewijzen dat wel degelijk [ci ] = 0. Hiervoor gebruiken we schrijfwijze (3.1) voor [ci ].
[ci ] = . . . + (g − 1)g3 + (g − 1)g2 + (g − 1)g1 + (g)g0
= . . . + g4 − g3 + g3 − g2 + g2 − g1 + g1
= . . . + 0 + 0 + 0 + 0 = 0
Gaan we vermenigvuldiging erbij betrekken, dan wordt de zaak ingewikkelder. Uit het voorbeeld van pagina 7 blijkt dat hoe verder een cijfer van het product naar links staat, hoe meer getallen bij elkaar opgeteld moesten worden om dit cijfer te verkrijgen. We willen een algemene formule vinden voor ci in het product [ai ] × [bi ] = [ci ]. Hiervoor schrijven we [ai ] en [bi ] weer zoals in vgl. (3.1).
[ci ] = (. . . a3g3 + a2g2 + a1g1 + a0g0) × (. . . b3g3 + b2g2 + b1g1 + b0g0)
5
c5 = a0 b5 + a1b4 + a2b3 + . . . + a5 b0 = X ak b5−k
k=0
Dit is de som van alle aj bk waarvoor j + k = 5. Voor andere cijfers ci gaat het analoog. We concluderen:
[ai ] × [bi ] =
i
h X
k=0
i
ak bi−k
(3.4)
Deze formule is heel wat lastiger dan formule (3.3) voor de optelling! De bewijzen van de rekenregels van vermenigvuldiging zijn dan ook een stuk lastiger. Dat van de commutativiteit is nog wel te overzien; het komt er op neer dat je moet bewijzen dat
a0bi + a1bi−1 + . . . + ai b0 = b0ai + b1ai−1 + . . . + bi a0
Dat is een kwestie van de som in omgekeerde volgorde schrijven en vervolgens alle pro- ducten omdraaien.
Oefening 3.1.2. Ga na dat uit formule (3.4) volgt dat [ei ] het eenheidselement van Zg is, waarbij e0 = 1 en ei = 0 voor de overige i. Dat wil zeggen: bewijs dat [ei ] × [bi ] = [bi ] voor alle [bi ].2
3.1.1 Bezwaren tegen de P methode
We hebben nu twee nadelen gezien van het schrijven van g-adische gehele getallen als een oneindige som. Ten eerste zijn de eigenschappen van vermenigvuldiging vrij moeilijk te bewijzen, zeker als je dat strikt volgens de regels van algebra¨ısche structuren wilt doen.
Ten tweede kunnen cijfers groter zijn dan g − 1.
Wat misschien nog wel een belangrijker bezwaar is, is dat het niet wiskundig correct is om zomaar een oneindige som te nemen en daarmee te gaan rekenen zoals in (3.3) en (3.4). We zouden eerst moeten bewijzen dat deze sommen convergeren, en vervolgens dat (3.3) en (3.4) waar zijn. Daar hebben we te weinig voorkennis voor, daarom pakken we het anders aan. We defini¨eren g-adische getallen als abstracte rijtjes van ‘cijfers’, die op zichzelf niets voorstellen. Optelling en vermenigvuldiging worden vastgelegd met algoritmen (rekenvoorschriften). Het rekenvoorschrift voor optelling bijvoorbeeld doet
2 Dat ook [bi ] × [ei ] = [bi ] hoef je niet te bewijzen, want dat volgt direct uit de commutativiteit van vermenigvuldiging in Zg .
eigenlijk niets anders dan stap voor stap ‘onder elkaar staande’ cijfers optellen, zoals we ook in §1.2 hebben gedaan. Het verschil is dat we eerst het overlenen laten zitten, we staan cijfers groter dan g − 1 en kleiner dan 0 toe. Vervolgens laten we hier een algoritme op los dat kan overlenen, zodat een echt g-adisch getal ontstaat.
De verzameling van alle g-adisch-achtige getallen waar alle gehele getallen als cijfers zijn toegestaan, noemen we Z∗. We zullen bewijzen dat dit een commutatieve ring met
1 is. Vervolgens beelden we de elementen van Z∗ met het overleen-algoritme af naar Zg , en beredeneren dat Zg ook een commutatieve ring met 1 moet zijn. Daarna laten we zien dan Zg geen nuldelers heeft als g priem is, en kijken we waneer delen mogelijk is binnen Zg . Als toetje geven we uitleg bij een algoritme dat kan delen in Zp .
3.2 Formele definitie van Z∗ en Zg
We zullen Z∗ en Zg nu formeel defini¨eren. Met (ai ) : i ∈ N bedoelen we een geordende
operaties optellen en vermenigvuldigen op gedefinieerd hebben, heeft de rij strikt gezien geen enkele betekenis. Toch houden we in ons achterhoofd wat we eigenlijk bedoelen met zo’n rij, namelijk een g-adisch geheel getal van de vorm
. . . a3a2a1a0
Zo wordt het veel gemakkelijker om intu¨ıtief in te zien wat in de bewijzen nou eigenlijk gedaan wordt. We zullen in de rest van dit hoofdstuk (ai ) vaak afkorten tot a, analoog voor andere letters dan a. Als iets anders bedoeld wordt met zo’n letter, wordt dat expliciet vermeld.
Definitie 3.2.1. We defini¨eren de verzameling Z∗ als volgt.
∀g ∈ N≥2 : Z∗ := {(ai ) | i ∈ N, ai ∈ Z}
Optelling en vermenigvuldiging in Z∗ zijn zo gedefini¨eerd als in algoritme 1 resp. 2, zie
§3.3.1 en §3.3.2. Dat wil zeggen: ∀a, b ∈ Z∗ is
a + b = add(a, b) en a × b = mult(a, b)
Definitie 3.2.2. Zg is de deelverzameling van Z∗
waarvoor alle ai tussen 0 en g − 1
liggen.
∀g ∈ N≥2 : Zg := {(ai ) | i ∈ N, ai ∈ Z, 0 ≤ ai ≤ g − 1}
Hoewel dit een deelverzameling van Z∗
is, zijn optelling en vermenigvuldiging anders
gedefinieerd.3 Nadat algoritme 1 of 2 is toegepast, laten we op de uitkomst namelijk ook nog algoritme 3 los, zie §3.4. Dat wil zeggen: ∀a, b ∈ Zg is
3 Strikt gezien zijn het dan ook andere operaties.
3.3. ALGORITMES VOOR Z∗
3.3 Algoritmes voor Z∗
We hebben de bewerkingen in Zg en Z∗ dus gedefini¨eerd met algoritmen.4 Het is alsof je
een hypersnelle computer programmeert die bij twee oneindige rijtjes een nieuw oneindig rijtje oplevert. Natuurlijk bestaan zulke computers alleen in gedachten.
Hoewel onze hersenen niet als een computer werken, kunnen we toch inzien hoe zo’n algoritme werkt, en daarmee kunnen we bepaalde rekenregels bewijzen.
3.3.1 Optelling
Algorithm 1 Add
1: function add(a, b ∈ Z∗) ∈ Z∗
g g
2: c ∈ Z∗
3: begin
4: for i := 0 to ∞ do
5: ci := ai + bi
6: result := c
7: end
Met algoritme 1 kan de som c van twee elementen a en b uit Z∗ worden berekend.
Bij dit eerste algoritme zullen we uitleggen hoe je het kunt lezen.
Regel 1 vertelt de computer dat de functie die tussen begin en end staat afgekort wordt als add(a, b). De functie heeft als domein Z∗ en als bereik ook Z∗. Op regel 2
g g
met regel 6 aanmoest.
Bij de regels 4 t/m 6 wordt de daadwerkelijke berekening uitgevoerd. Hierbij moeten we vermelden dat a gelijk is aan (a0, a1, a2, • • • ), analoog zijn ook b en c zulke rijtjes.5 De for-lus in regel 4 vertelt dat het volgende gedeelte moet worden uitgevoerd voor i = 0 tot i = ∞. In regel 5 worden de afzonderlijke elementen (de ‘cijfers’) van (ai ) en (bi ) bij elkaar opgeteld; het resultaat (ci ) wordt in regel 6 opgeslagen als c.
Wat het algoritme doet kan worden samengevat als
(ai ) + (bi ) = (ai + bi ) (3.5)
zoals je gemakkelijk kunt nagaan. De inwendigheid van + in Z∗ is wel duidelijk, optelling is immers ook inwendig in Z (bedenk dat ai , bi ∈ Z). Ook de associativiteit van optelling is makkelijk te bewijzen.
(ai ) + (bi ) + (ci ) = (ai + bi ) + (ci ) = (ai + bi ) + ci
= ai + (bi + ci ) = (ai ) + (bi + ci ) = (ai ) + (bi ) + (ci )
4 De taal waarin de algoritmen geschreven zijn is afgeleid van Pascal.
5 Natuurlijk moet de computer dat ook weten, maar voor de overzichtelijkheid hebben we dit uit het algoritme weggelaten.
Maar dit bewijs lijkt wel heel veel op dat van pagina 22! Het enige verschil is dat de vierkante haakjes [ ] vervangen zijn door ronde haakjes ( ), maar dat is slechts een kwestie van notatie. En natuurlijk is de interpretatie van het bewijs anders, [ai ] stelde immers een oneindige som voor terwijl (ai ) ‘slechts’ een abstracte rij getallen is. Dat maakt algebra¨ısch echter niet uit, de manier van bewijzen blijft hetzelfde. Verder is hier
ai ∈ Z, terwijl we in de voorbereiding met ai ∈ N werkten. Ook dat is niet erg, want in
Voor de bewijzen van de andere samenstellingswetten voor optelling in Z∗ gaat dit ook op. Dat komt doordat de optelling op pagina 21 hetzelfde is ‘gedefinieerd’ als hier, namelijk als [ai ] + [bi ] = [ai + bi ]. Daarmee zijn de commutativiteit en de associativiteit van +, het bestaan van een nulelement, en het bestaan van een tegengestelde voor elk element bewezen; dit hebben we immers allemaal in §3.1 gedaan. Voor de tegengestelde van (ai ) mogen we nu zelfs (−ai ) nemen, omdat we met ai ∈ Z werken.
3.3.2 Vermenigvuldiging
Algorithm 2 Mult
1: function mult(a, b ∈ Z∗) ∈ Z∗
g g
2: c ∈ Z∗
3: begin
4: c := (0, 0, 0, • • • )
5: for i := 0 to ∞ do
6: begin
7: for z := 0 to i do
8: ci := ci + az • bi−z
9: end
10: result := c
11: end
Ook algoritme 2 komt op hetzelfde neer als de formule voor vermenigvuldiging zoals we die in §3.1 hebben afgeleid, namelijk vgl. (3.4). Dit zullen we beredeneren nadat we wat uitleg bij het algoritme hebben gegeven.
In regel 4 wordt c opgeslagen als een rij nullen: we beginnen met een schone lei. In regel 5 begint een oneindige lus, die op zijn beurt een eindige lus bevat, namelijk die van regel 7. Regel 8 ziet er wat vreemd uit, je zou zeggen dat dit alleen kan als az • bi−z = 0. Dat hoeft echter niet, want in computertaal betekent ci := ci + az • bi−z iets anders dan in de wiskunde. De rechter ci is het getal dat al in het geheugen van de computer stond (in het begin dus 0), die wordt vervangen door de linker ci . Eigenlijk betekent regel 8 dus: tel az • bi−z op bij ci .
(ai ) • (bi ) =
i
X
z=0
az bi−z
(3.6)
en dat is precies dezelfde formule als (3.4).6 Omdat we in §3.1 de commutativiteit van
× en het bestaan van een eenheidselement hebben bewezen, zijn we daar klaar mee. De inwendigheid is duidelijk. Blijft over de associativiteit en de distributiviteit.7
Stelling 3.3.1. De vermenigvuldiging is associatief in Z∗.
Bewijs. We willen bewijzen dat (ab)c = a(bc) voor alle a, b, c ∈ Z∗. Hiervoor voegen we twee mult-algoritmes8 samen tot ´e´en. Het begin en eind van het algoritme dat alleen voor de computer van belang is laten we voor het gemak weg. De uitkomst van a • b noemen we q; vervolgens berekenen we de uitkomst k = q • c van het algoritme. Het algoritme berekent dus (ab)c.
for i := 0 to ∞ do begin
qi := qi + az • bi−z ; (a) {Hier wordt q = a • b berekend zoals in algoritme 2.}
for z := 0 to i do
ki := ki + qz • ci−z ; (b) {Hier wordt k = qc = (ab)c berekend.}
end
In for-lus (b) is qz gelijk aan de bij (a) berekende som van i termen, dus we kunnen het algoritme als volgt korter opschrijven.
for i := 0 to ∞ do begin
for y := 0 to i do
for z := 0 to i − y do
ki := ki + az • bi−y−z • cy {Let op: z vervult hier een andere functie dan in for-lus (a).}
end
Hier wordt elk ‘cijfer’ ki berekend als de som van alle ap bq cr waarvoor p + q + r = i. Immers, z + (i − y − z) + y = i, en omdat z, i − y − z en y niet kleiner dan nul mogen zijn is het voldoende om y van 0 tot i te laten lopen en z van 0 tot i − y. Omdat dit een eindige som is in Z, doet de volgorde van de optelling er niet toe. Zolang we maar alle
6 Dat k vervangen is door z en [ ] door ( ) is slechts een kwestie van notatie.
8 d.i. algoritme 2 combinaties van ap bq cr waarvoor p + q + r = i een keer optellen bij ki , komt er dezelfde
k uit. We kunnen het algoritme dus ook als volgt schrijven.
for i := 0 to ∞ do begin
for y := 0 to i do
for z := 0 to i − y do
ki := ki + ay • bz • ci−y−z
end
Wegens de commutativiteit van vermenigvuldiging in Z mogen we in het laatste algoritme ook schrijven: ki := ki + bz • ci−y−z • ay . Als we dat doen, hebben we precies het tweede algoritme van dit bewijs teruggekregen, alleen nu met a, b en c omgewisseld. De uitkomst van dit algoritme is dus gelijk aan (bc)a en dat is a(bc). Maar we begonnen met een algoritme dat (ab)c berekende, en omdat de algoritmes steeds zo zijn omgeschreven dat de uitkomst gelijk blijft, mogen we concluderen dat (ab)c = a(bc).
Nu bewijzen we de distributiviteit.
Bewijs. We willen bewijzen dat a(b + c) = ab + ac en dat (a + b)c = ac + bc voor alle a, b, c ∈ Z∗. Hiervoor voegen we weer twee functies samen, dit keer de add-functie en de mult-functie (algoritme 1 en 2). Dit samengestelde algoritme berekent, zoals je gemakkelijk kunt nagaan, a(b + c).
for i := 0 to ∞ do begin
qi := bi + ci ; (a) {Hier wordt q = add(b, c) berekend.}
for z := 0 to i do
ki := ki + az • qi−z ; (b) {Hier wordt k = mult(a, q) berekend.}
end
Volgens (a) is qi = bi + ci , dus (b) kunnen we schrijven als ki := ki + az (bi−z + ci−z ), en dat is wegens de distributiviteit in Z gelijk aan ki + az bi−z + az ci−z . We kunnen dit algoritme dus schrijven als
for i := 0 to ∞ do begin
for z := 0 to i do
ki + az bi−z + az ci−z (a)
end
We kunnen (a) in twee¨en splitsen, zodat we het volgende algoritme krijgen:
for i := 0 to ∞ do for z := 0 to i do
ki := ki + az • bi−z ; (a)
ki := ki + az • ci−z ;
end
In dit laatste algoritme kunnen we (a) als het ware buiten haakjes halen door deze berekening als eerst uit te voeren. De uitkomst noemen we q; die tellen we aan het eind bij ki op. Ga voor jezelf na dat het volgende algoritme echt dezelfde uitkomst zal geven als het vorige.
for i := 0 to ∞ do begin
for z := 0 to i do
qi := qi + az • bi−z ; (a)
for z := 0 to i do
ki := ki + az • ci−z ; (b)
ki := qi + ki ; (c)
end
Bij (a) wordt ab berekend, bij (b) wordt ac berekend, en bij (c) worden de uitkomsten daarvan bij elkaar opgeteld. De uitkomst k van het algoritme is dus gelijk aan ab + ac, en omdat het algoritme waarmee we begonnen a(b + c) berekende, hebben we bewezen dat a(b + c) = ab + ac, dat is de links-distributiviteit. Omdat de commutativiteit van × al is bewezen, geldt volgens stelling 2.4.2 ook de rechts-distributiviteit. Hiermee stelling
3.3.2 bewezen.
We hebben in deze paragraaf bewezen dat voor Z∗ de volgende samenstellingswetten uit Tabel 2.2 gelden. Voor + gelden 1), 2), 3), 4) en 5); voor × gelden 1), 2), 3) en 5); verder geldt ook 6). Met Tabel 2.4 volgt hieruit dat Z∗ een commutatieve ring met 1 is.
We hebben nu bewezen dat Z∗ een ring vormt, maar dat willen we uiteindelijk natuurlijk bewijzen voor Zg . Om dit te bereiken komen we terug op het idee dat een element a van Zg te schrijven is als een oneindige som van de vorm
∞
a = X ai gi , ai ∈ Z (3.7)
i=0
Algorithm 3 Norm
1: function norm(a ∈ Z∗) ∈ Zg
2: d−1
:= 0 {Dit is nodig omdat de computer anders bij 6 in de knoop komt.}
3: begin
4: for i := 0 to ∞ do
5: begin
6: ai := ai + di−1 {Hier wordt als het ware overgeleend van ai−1.}
7: di := ai div g {a div b geeft het quoti¨ent bij de restdeling a .}
8: ai := ai − g • di {Dit is de rest bij die deling.}
9: end
10: result := a
Nu gaan we de volgende zeer fundamentele stelling gebruiken. Voor een bewijs verwijzen we naar §2.2 van [1].
Stelling 3.4.1. (Deling met rest) Stel a, b ∈ Z en b > 0. Dan zijn er gehele getallen
q en r z´o dat
a = bq + r, 0 ≤ r < b
We noemen q het quoti¨ent en r de rest van de restdeling a . De stelling zegt dus niets anders dan dat deze restdeling altijd kan worden uitgevoerd (mits b = 0), waarbij een positieve rest kleiner dan b ontstaat.
We kunnen volgens stelling 3.4.1 restdeling van de ‘cijfers’ ai van a (zie formule 3.7)
door g uitvoeren. Het quoti¨ent noemen we di en de rest ci . We krijgen:
ai gi = (di g + ci )gi = di gi+1 + ci gi , 0 ≤ ci < g
ci wordt het nieuwe cijfer van a op positie i; we tellen di wegens de factor gi+1 op bij het cijfer op positie i + 1, dit wordt de nieuwe ai+1 . Nu kunnen we restdeling op ai+1 toepassen, hierbij blijft ci onveranderd. Als we op deze manier vanaf a0 restdeling toepassen, krijgen we
∞ ∞
i=0
i=0
We hebben een getal a ∈ Z∗ omgevormd tot een een getal uit Zg ; immers, de cijfers ci liggen tussen 0 en g − 1. Dit is precies wat algoritme 3 (zie pagina 30) doet, het komt eigenlijk op hetzelfde neer als het ‘overlenen’ zoals we in §1.2 hebben gedaan.
Met algoritme 3 kunnen we Z∗ afbeelden naar Zg . We zullen in deze paragraaf de
volgende stelling bewijzen.
Stelling 3.4.2. Voor alle g ∈ N≥2 is Zg een commutatieve ring met 1.
Allereerst voeren we een notatie in.
Definitie 3.4.3. Voor alle (ai ) ∈ Z∗ defini¨eren we voor alle i > 0:
a0 0
i := ai−1 en a0 := 0
Verder duiden we (a0 ) aan met (ai )0 ofwel a0.
Het is intu¨ıtief duidelijk dat a0 overeenkomt met g × a. Alle cijfers van a schuiven immers
´e´en positie naar links op, en de lege plek wordt opgevuld met een 0. Deze bewering zullen we in het volgende hoofdstuk nodig hebben, daarom geven we een bewijs. In plaats van g schrijven we y = . . . 00010 ofwel (0, 1, 0, 0, 0, • • • ); het is duidelijk dat y = norm(g).
Stelling 3.4.4. De afbeelding a 7→ a0 in Zg komt overeen met vermenigvuldiging van a
Bewijs. We hebben eerder gezien dat de mult-functie van algoritme 2 dezelfde uitkomst geeft als formule (3.6) op pagina 27. In deze formule vullen we voor b het getal (yi ) in, zo krijgen we de volgende formule voor (ai ) × (yi ).
i
X az yi
z=0
(3.8)
Als z = i − 1 is yi−z = y1 = 1, dan is az yi−z dus gelijk aan ai−1 × 1 = ai−1. Voor de overige z is yi−z = y1 , dan is yz = 0. We concluderen dat de uitkomst van (3.8) alleen
9 0 0
bepaald wordt door z = i − 1, dus de uitkomst is (ai−1 ),
is bewezen dat a0 = a × (yi ).
ofwel (ai ), ofwel (ai ) . Hiermee
Om stelling 3.4.2 te bewijzen, hebben we eerst een paar lemma’s (hulpstellingen) nodig.
3.4.1 Lemma’s
Lemma 3.4.5. Voor alle a ∈ Z∗ is er een d ∈ Z∗ zodat norm(a) = a + d0 − gd, waarbij
g g
bovendien di = ai + di−1 div g voor alle i ≥ 0.
Bewijs. Beschouw algoritme 3. In regel 6 wordt di−1 bij ai opgeteld; in regel 8 wordt vervolgens g maal de in regel 7 berekende waarde van di , van ai afgetrokken. Dit betekent dat het genormaliseerde cijfer ai gelijk is aan ai +di−1 −gdi , en omdat bovendien d−1 := 0 is dat gelijk aan ai + d0 − gdi . We concluderen dat norm(a) = (ai + d0 − gdi ), en met
behulp van vgl. (3.5) volgt hieruit dat
norm(a) = (ai + d0 + −gdi ) = (ai ) + (d0 ) + (−gdi ) = a + d0 − gd
i i
Bovendien blijkt uit regel 6 en 7 dat di = ai + di−1 div g.
9 en het eerste cijfer is a0 y0 = 0
Lemma 3.4.6.
∀b, e ∈ Z∗ : norm(b) = norm(b + e0 − ge)
Bewijs. Volgens lemma 3.4.5 is er een z ∈ Z∗ zodat
norm(b) = b + z0 − gz (3.9)
zi = bi + zi−1 div g (3.10) We gaan norm(b + e0 − ge) voor een willekeurige e ∈ Z∗ berekenen, en willen bewijzen
dat dat dit gelijk is aan norm(b). We doorlopen de norm-functie voor a = b + e0
− ge.
Eerst bereken we het nulde cijfer a0
. In regel 6 van algoritme 3 gebeurt er nog niets van
d0 = a0 div g = b0 + e0 − ge0 div g = b0 − ge0 div g = −e0 + (b0 div g)
= −e0 + (b0 + z−1 div g) Regel 8 berekent:
(3.10)
= −e0 + z0 (3.11)
a0 := a0 − gd0 = (b0 + e0 − ge0) − g(−e0 + z0 ) = b0 − ge0 + ge0 − gz0 = b0 − gz0
en dat is volgens vgl. (3.9) gelijk aan het nulde cijfer van norm(b), want z0 = 0.
Nu kijken we naar het algemene geval. Stel dat we voor een zekere i > 0 weten dat
di−1 = −ei−1 + zi−1 (3.12)
Regel 6 geeft dan
Regel 7 berekent
ai := ai + di−1 = (bi + e0 − gei ) + (−ei−1 + zi−1)
= bi + ei−1 − gei − ei−1 + zi−1 = bi − gei + zi−1 (3.13)
di := ai div g
(3.13)
= (bi − gei + zi−1) div g
(3.10)
= − ei + (bi + zi−1) div g
Regel 8 geeft vervolgens:
ai := ai − gdi
(3.13)
= (bi − gei + zi−1) − gdi
(3.14)
= (bi − gei + zi−1) − g(−ei + zi )
= bi − gei + gei + zi−1 − gzi = bi + z0 − gzi
en dat is volgens vgl. (3.9) precies gelijk aan het i-de cijfer van norm(b). Bovendien blijkt uit (3.14) dat opnieuw de gelijkheid in (3.12) geldt, alleen nu met i eentje opgehoogd. We kunnen het hele verhaal dus opnieuw toepassen voor i + 1, dan voor i + 2, etc; telkens blijkt dat ai , het i-de cijfer van norm(b + e0 − ge), gelijk is aan het i-de cijfer van norm(b). Volgens (3.11) mogen we de redenering beginnen bij i = 1.10 Bovendien zagen we eerder al dat ook de nulde cijfers aan elkaar gelijk zijn. We concluderen dat alle cijfers van norm(b + e0 − ge) en norm(b) overeenkomen, waarmee de stelling bewezen is.
10 Bedenk dat er i − 1 staat bij vgl. (3.12).
∀a, b ∈ Z∗ : a0 + b0 = (a + b)0
Bewijs. In formule (3.5) hebben we gezien dat (ai ) + (bi ) = (ai + bi ). Als we het i-de cijfer van (ai ) + (bi ) voor het gemak (a + b)i noemen, volgt hieruit dat (a + b)i = ai + bi . Nu zien we dat voor alle i > 0 geldt:
(a + b)0 = (a + b)i−1 = ai−1 + bi−1 = a0 + b0 = (a0 + b0)i
i i i
Nu moeten we de stelling alleen nog maar bewijzen voor i = 0. Dat is zo gedaan:
(a + b)0
= 0 = 0 + 0 = a0 + b0
= (a0 + b0)0
0 0 0
Hiermee is bewezen dat (a + b)0 = (a0 + b0)i voor alle i, dus alle cijfers van (a + b)0 en a0 + b0 komen met elkaar overeen, deze getallen zijn dus gelijk. Hiermee is de stelling bewezen.
Lemma 3.4.8.
∀a, b ∈ Z∗ : a0 × b = (a × b)0
Bewijs. Volgens formule (3.6) geldt voor de cijfers ai en bi van de getallen (ai ) en (bi ):
i
z=0
Hieruit volgt dat voor alle i > 0:11
i−1 i i
(ab)0 = (ab)i−1 = X az bi−1−z = X ak−1bi−k = X a0 bi−k = (a0b)i
i
z=0
k=1
k
k=1
We kunnen gemakkelijk aantonen dat bovenstaande gelijkheid ook geldt voor i = 0.
(ab)0
0
= 0 = 0 × b0 = a0 b0 = X a0 b0 = (a0b)0
0 0 0
z=0
Conclusie: voor alle i is (ab)0
= (a0b)i , dus de getallen (ab)0 en (a0b) zijn aan elkaar
gelijk.
Lemma 3.4.9.
∀a, b ∈ Z∗ : norm norm(a) + b = norm(a + b)
Bewijs. Volgens lemma 3.4.5 kunnen we norm(a) schrijven als a + d0 − gd voor een zekere
d ∈ Z∗. Nu kunnen we afleiden:12
11 In de derde stap wordt k gesubstitueerd voor z + 1.
12 een nummer boven een =-tekens verwijst naar het lemma dat bij die stap gebruikt wordt.
Lemma 3.4.10.
∀a, b ∈ Z∗ : norm norm(a) • b = norm(a • b)
Bewijs. We kunnen norm(a) schrijven als a + d0 − gd voor een d ∈ Z∗.
norm norm(a) • b = norm (a + d0 − gd)b = norm(ab + d0b − gdb)
3.=4.8 norm ab + (db)0 − g(db) 3.=4.6 norm(ab)
3.4.2 Bewijs: Zg is een commutatieve ring met 1
Om stelling 3.4.2 te bewijzen, hebben we nog twee belangrijke maar eenvoudig te bewij- zen stellingen nodig.
Stelling 3.4.11.
∀a, b ∈ Z∗ : norm(a + b) = norm norm(a) + norm(b)
Bewijs. De eerste gelijkheid volgt met behulp van het feit dat norm(b) ∈ Z∗, de tweede
met de commutativiteit van optelling in Z∗.
norm norm(a) + norm(b) 3.=4.9 norm a + norm(b) 3.=4.9 norm(a + b)
Stelling 3.4.12.
∀a, b ∈ Z∗ : norm(a • b) = norm norm(a) • norm(b)
Bewijs. Dit gaat geheel analoog aan dat van de vorige stelling.
norm norm(a) • norm(b) 3.=4.10 norm a • norm(b) 3.=4.10 norm(a • b)
Nu hebben we genoeg gereedschap om te bewijzen dat Zg een commutatieve ring met 1 is.
Laat a, b, c elementen zijn van Zg . Omdat Zg ⊂ Z∗ is ook a, b, c ∈ Z∗, dus op a, b en
g g
c mogen we de regels van een commutatieve ring met 1 al toepassen.
De optelling en vermenigvuldiging in Zg zijn anders gedefini¨eerd dan in Z∗, zie de-
finitie 3.2.2 op pagina 24. Om onderscheid tussen de operaties te maken, duiden we optelling en vermenigvuldiging in Zg aan met ⊕ resp. ⊗, in Z∗ schrijven we gewoon +
en ×. Volgens definitie 3.2.2 geldt:
a ⊕ b = norm(a + b), a ⊗ b = norm(a × b).
Verder geldt voor alle z ∈ Zg natuurlijk dat
norm(z) = z (3.15) Immers, alle cijfers zi van z liggen tussen 0 en g − 1, dus in algoritme 3 geldt voor alle i
dat di = zi div g = 0. Hierdoor blijven alle zi onveranderd.
Als eerste bewijzen we de inwendigheid van ⊕ en ⊗ in Zg . Dat is zo gedaan. Immers,
a ⊕ b = norm(a + b), en omdat + inwendig is in Z∗, is dit de norm-functie toegepast
op een element van Z∗. Volgens definitie 3.2.2 is het resultaat weer een element van Zg . Voor vermenigvuldiging gaat het analoog: vervang overal ⊕ door ⊗ en + door ×, en je bent er.
Nu bewijzen we de commutativiteit van ⊕ en ⊗ in Zg . Ook dat is eenvoudig:
a ⊕ b = norm(a + b) = norm(b + a) = b ⊕ a
Voor vermenigvuldiging gaat het weer analoog.
Voor de associativiteit moeten we wat meer moeite doen, omdat we met drie ele- menten te maken hebben. Het bewijs voor ⊕ gaat als volgt.13 We korten norm af tot n.
a ⊕ (b ⊕ c) = a ⊕ n(b + c) = n a + n(b + c)
(3.15)
= n n(a) + n(b + c)
3.=4.11 n a + (b + c) = n (a + b) + c = n n(a + b) + n(c)
= n n(a + b) + c = n(a + b) ⊕ c = (a ⊕ b) ⊕ c
Het bestaan van een nulelement en een eenheidselement in Zg is gemakkelijk te bewijzen: het zijn dezelfde 0 en 1 als in Z∗. Voor ⊕ 0 hebben we het bewijs uitgewerkt,
voor ⊗
1 gaat het analoog.
a ⊕ 0 = n(a + 0) = n(a) = a
Omdat we de commutativiteit voor ⊕ en ⊗ al hebben bewezen, is ook 0 ⊕ a = a en
1 ⊗ a = a, waarmee is aangetoond dat 0 en 1 inderdaad de gezochte elementen zijn.
Het bestaan van een tegengestelde van elke (ai ) ∈ Zg is makkelijk aan te tonen, het is vergelijkbaar met de manier waarop we de tegengestelde op pagina 6 hebben berekend. De kleinste i waarvoor ai = 0 noemen we k. We nemen het getal (bi ) ∈ Zg waarbij bi = 0 voor alle i < k, bk = g − ak en bi = g − ai − 1 voor alle i > k. Ga na dat inderdaad (bi ) ∈ Zg . Algoritme 1 berekent:
(ai ) + (bi ) = (0, 0, • • • , 0, g, g − 1, g − 1, g − 1, • • • ) := (ci )
Nu berekenen we (ai ) ⊕ (bi ) = norm(ci ). Alle cijfers ci met i < k blijven natuurlijk 0. Dan wordt dk = g div g = 1 berekent, daarna ck = g − g • 1 = 0. Dan wordt dk bij ck+1 opgeteld zodat dit g wordt, deze wordt weer 0 waarbij weer 1 wordt overgeleend, etc. Zo wordt (ci ) = 0, dus (bi ) is de tegengestelde van (ai ).
13 Opnieuw gaat het voor ⊗ analoog, maar nu moet wel stelling 3.4.11 vervangen worden door 3.4.12.
Het bestaan van een inverse bespreken we in de volgende paragraaf, evenals het (niet)
bestaan van nuldelers.
Tot slot bewijzen we de distributiviteit.
a ⊗ (b ⊕ c) = a ⊗ n(b + c) = n a • n(b + c) 3.=4.10 n a(b + c)
= n(ab + ac) 3.=4.12 n n(ab) + n(ac) = n(a ⊗ b + a ⊗ c) = a ⊗ b ⊕ a ⊗ c
Nu hebben we de eigenschappen 1), 2), 3), 4) en 5) voor optelling bewezen, zie Tabel 2.2. We hebben 1), 2), 3) en 5) voor vermenigvuldiging en bovendien 6) bewezen. Volgens Tabel 2.4 is hiermee stelling 3.4.2 bewezen: Zg is een commutatieve ring met 1.
In het vervolg werken we vooral met Zg . Daarom schrijven we gewoon weer + en ×
in plaats van ⊕ en ⊗, tenzij anders vermeld.
3.5 Deelbaarheid in Zg
Wanneer is delen mogelijk in Zg ? En in welke gevallen zijn er nuldelers? Daarover gaat deze paragraaf.
3.5.1 Nuldelers
Laten we met die laatste vraag beginnen. Zoals al eerder is gezegd, zijn nuldelers getallen a, b ongelijk aan 0 waarvoor a × b = 0. In de getalsystemen waarmee we bekend zijn bestaan geen nuldelers, maar we zullen laten zien dat deze er in Zg w´el zijn voor bepaalde grondtallen g.
Hiervoor hebben we eerst wat basiskennis nodig over modulorekenen14 , ook wel klok- rekenen genoemd. Iedereen leert als kind rekenen met de klok van twaalf. Als het nu 8 uur is, is het 7 uur later natuurlijk 3 uur. Dit noteren15 we als 8 + 7 = 15 ≡ 3 (mod 12). In het algemeen is a ≡ b (mod g) precies dan als a en b dezelfde rest hebben bij deling door g.
Met b mod g bedoelen we het kleinste positieve getal a waarvoor a ≡ b (mod g). Je kunt makkelijk inzien dat b mod g de rest is van de restdeling van b door g. Hierdoor is altijd 0 ≤ b mod g < g.
Maar wat heeft modulorekenen nou met g-adische getallen te maken? Bij het optellen of vermenigvuldigen van twee (g-adische) getallen gebruik je, wellicht zonder dat je het door hebt, modulorekenen. Bereken bijvoorbeeld 13 • 8 in grondtal 10. Het eerste cijfer
4 van het product heb je berekend met 3 • 8 = 24 ≡ 4 (mod 10), ofwel, door 2 • 10 naar links over te lenen. Bij g-adische getallen werkt het net zo. Als . . . a2a1a0 × . . . b2b1 b0 =
. . . c2c1 c0, dan is c0 = a0b0 mod g.
Nu gaan we laten zien dat Z10 nuldelers heeft. We zoeken hiervoor een x ∈ Z10
ongelijk aan 0 of 1 met de op het eerste gezicht absurde eigenschap x2 = x. Zo’n getal
14 Zie ook [10] voor meer uitleg hierover.
15 Spreek uit: ‘vijftien en drie zijn congruent modulo twaalf ’.
blijkt echt te bestaan. We beginnen met het vaststellen van het eerste cijfer:
x0 = 5.
Dan is ook het nulde cijfer van x2 gelijk aan 52 = 25 = 5 mod 10; dit cijfer voldoet dus aan de eis. Nu blijkt dat alle volgende cijfers vastliggen; we laten zien hoe we ze stap voor stap kunnen construeren.
Stel dat we in de k-de stap het cijfer xk willen bepalen zodat aan de eis wordt
voldaan.16 In de vorige stappen hebben we dus als benadering x = . . . xk
−1x
k−2
. . . x0
gevonden, waarbij x2 = . . . xk
−1 x
k−2
. . . x0 . Deze k cijfers kunnen niet meer be¨ınvloed
worden door volgende cijfers, deze zijn dus in elk geval goed.
Dit alles schrijven we iets duidelijker op. We weten dat
(xk−1 . . . x2x1x0)
en we zoeken xk zodat
≡ xk−1 . . . x2 x1 x0 (mod 10 )
(xk . . . x2 x1x0)2 ≡ xk . . . x2x1 x0 (mod 10k+1 )
We moeten modulo een macht van 10 rekenen omdat de volgende cijfers nog niet bekend zijn. Bedenk dat hoe groter k, hoe kleiner de invloed is van 10k , dus x wordt steeds nauwkeuriger bepaald.
Als we het i-de cijfer van x2 aanduiden met ai , dan volgt uit vgl. (3.6) en de norm- functie dat
k k−1
ak = X xz xk−z + dk−1 = x0xk + X(xz xk−z ) + xk x0 + dk−1 = yk−1 + 2x0 xk mod 10
z=0
k−1
z=1
waarbij yk−1 = Pz=1 (xz xk−z ) + dk−1. Omdat dk−1 met overlenen te berekenen is, en er
verder alleen termen met xi in voorkomen waarbij 0 < i < k, is yk−1 een bekend (geheel)
getal. Omdat x2 = x moeten alle i-de cijfers van x en x2 overeenkomen, dus
xk = ak ≡ 2x0xk + yk−1 (mod 10)
⇒ xk ≡ 2 • 5 • xk + yk−1 (mod 10)
⇒ − 9xk ≡ 1yk−1 ≡ 81yk−1 = 9 yk−1 (mod 10)
⇒ xk = −9yk−1 mod 10 (3.16)
Hiermee hebben we de gevraagde waarde van xk gevonden.17
Door steeds de waarde van yk−1 te bepalen om vervolgens xk te berekenen met
vgl. (3.16), kun je het getal x construeren; voor de eerste vijf decimalen vinden we
x = . . . 90625. Met een vermenigvuldiging kun je controleren dat inderdaad x2 = x op een veelvoud van 106 na.
16 De nulde stap is dus het vaststellen van x0 = 5.
17 In vgl. (3.16) mogen we mod 10 schrijven in plaats van (mod 10), want omdat xk een cijfer is weten we dat 0 ≤ xk < 10.
Nu berekenen we het getal y = 1 − x = . . . 09376. Als we dit met zichzelf vermenig- vuldigen, rijst het vermoeden op dat ook y2 = y. En inderdaad,
y2 = (1 − x)2 = 12 − 2x + x2 = 1 − 2x + x = 1 − x = y.
Er geldt:
xy = x(1 − x) = x − x2 = x − x = 0
dus x en y zijn nuldelers in Z10 .
In dit voorbeeld hebben we gebruik gemaakt van speciale eigenschappen van het begin- cijfer 5 van x, bijvoorbeeld bij de aanloop naar vgl. (3.16). Het is daarom niet meteen duidelijk of we deze methode ook bij andere grondtallen dan 10 kunnen toepassen, en zo ja, hoe. Het lijkt daarom een onbegonnen werk om te zoeken naar een g waarvoor de ring Zg geen nuldelers heeft. Toch blijkt dat heel gemakkelijk te zijn als we handig gebruik maken van eigenschappen van priemgetallen.18
Stelling 3.5.1. Voor alle p ∈ P bevat Zp geen nuldelers.
Bewijs. Beschouw twee p-adische getallen a en b ongelijk aan 0, waarbij p ∈ P. We schrijven a = . . . a2a1 a0 en b = . . . b2 b1 b0. Omdat a, b = 0 is er een kleinste ai en een kleinste bi die niet nul zijn, zeg ar en bs .
We berekenen ab = c door achtereenvolgens de mult-functie en de norm-functie toe
te passen. Volgens formule (3.6) is het door de mult-functie berekende cijfer cr+s gelijk aan
r+s
X az b(r+s) z
z=0
Als z < r is az = 0, deze termen vallen dus weg. Als z > r is (r + s) − z < s zodat b(r+s)−z = 0, ook deze termen vallen weg. Het enige wat overblijft is de situatie z = r, dus
cr+s = ar bs (3.17) Op dezelfde manier kun je gemakkelijk inzien dat ci = 0 voor alle i < r + s. Bij het
berekenen van a⊗b = norm(ab) wordt er vo´or cr+s dus niet overgeleend. cr+s zelf kan w´el
groter zijn dan p − 1, van dit cijfer kan dus een deel worden overgeleend. Kan het zijn dat
cr+s daardoor nul wordt? Dat zou betekenen dat cr+s veelvoud van p is.19 Maar ar en bs zijn cijfers tussen 1 en p − 1, dus cr+s = ar bs is niet nul en haar priemfactorontbinding kan nooit p bevatten, tegenspraak! We concluderen dat cr+s niet 0 kan zijn, ook niet nadat de norm-functie is toegepast. Daardoor kan ab = c niet 0 zijn, dus Zp heeft geen nuldelers.
In dit bewijs zie je ook waarom het voor samengestelde grondtallen mis kan gaan.
In hoofdstuk 4 zal blijken dat het van belang is dat Zg geen nuldelers heeft, daarom zullen we daar alleen kijken naar Zp met p priem.
18 P is de verzameling priemgetallen.
19 Dit volgt uit regel 7 en 8 van algoritme 3.
3.5.2 Wanneer kun je delen in Zg ?
Deze vraag moeten we wat nauwkeuriger formuleren. Stel a, b ∈ Zg . Zijn er grondtallen
g waarvoor we precies kunnen zeggen voor welke a en b geldt dat a ∈ Zg ?
Allereerst merken we op dat er geen enkele g is waarvoor elke a weer element is van
Zg ; geen enkele ring Zg is dus een lichaam.20 Stel namelijk dat x = a , dan is a = gx
zodat het eerste cijfer a0 van a gelijk is aan nul.21 In bijvoorbeeld Z10 is dus voor minstens 90% van alle a deze deling niet mogelijk. In het algemeen doet dit probleem zich voor bij a waarbij ggd(b, g) > 1.
In §1.2 hebben we al gezien dat delen in Z10 lang niet altijd mogelijk is, ook als b
niet deelbaar is door 10. Op pagina 8 constateerden we dat bijvoorbeeld x = a
nooit
element van Z10 kan zijn als a ‘oneven’ is en b ‘even’.22 Dit komt doordat als b even is, ook a = bx altijd even is; dit heeft te maken met het feit dat ggd(b0, 10) = 2. In het
algemeen is a
geen element van Zg als ggd(b0 , g) = d en bovendien d geen deler is van
a0 .
Als g priem is, is dat geen enkel probleem. Dan is ggd(b0, g) = 1 voor alle b met
b0 = 0, en dat 1 deler is van a0 vormt zeker geen beperking. We kunnen zelfs de volgende stelling bewijzen.
Stelling 3.5.2. Stel p ∈ P en a, c ∈ Zp . Als het eerste cijfer c0 van c ongelijk is aan 0, dan is a ∈ Zp .
Om dit te kunnen bewijzen, hebben we de volgende stelling nodig. Hierbij maken we weer gebruik van modulorekenen.
Stelling 3.5.3. Stel c, s ∈ Z en g ∈ N≥2. De verzameling {0, 1, 2, . . . , g − 1} noemen we Ag . We laten de variabele b alle elementen van Ag precies ´e´en keer doorlopen. Dan doorloopt ook bc + s mod g alle elementen a van Ag precies ´e´en keer, dan en slechts dan als ggd(c, g) = 1. Dit komt op hetzelfde neer als
∀a ∈ Ag : ∃b ∈ Ag : (bc + s) mod g = a ⇔ ggd(c, g) = 1
Bewijs. We onderscheiden twee gevallen.
Stel dat ggd(c, g) = d = 1. Dan zijn bc en g beide deelbaar door d, en daardoor is ook bc mod g deelbaar door d. Er is dus geen b ∈ Ag zodat bc mod g = 1, want 1 is deelbaar door geen enkel getal groter dan 1. Het element 1 + s mod g van Ag wordt dus niet bezocht door bc + s mod g.
20 In een lichaam bestaat immers voor alle b een element 1 , en wegens de inwendigheid van vermenig-
vuldiging bestaan ook alle a .
21 Dit is intu¨ıtief al duidelijk, maar we hebben het ook bewezen, namelijk in stelling 3.4.3. Daar concludeerden we dat ga = a0 en per definitie is a0 = 0.
22 Met even en oneven bedoelen we, ook in Zg , dat het meest rechtse cijfer (niet) deelbaar is door 2.
Dan nu het tweede geval, waarin ggd(c, g) = 1. Optelling en vermenigvuldiging volgens het modulorekenen zijn inwendig in Ag , dus alle bc + s mod g zijn element van Ag . Omdat b precies g elementen van Ag doorloopt, doet bc + s mod g dat ook, waarvan er nog een aantal gelijk kunnen zijn. Aanname: Stel dat er twee gelijk zijn, zodat b1c + s ≡ b2 c + s (mod g) en b1 = b2. Hieruit volgt dat (b1 − b2 )c ≡ 0 (mod g), dus (b1 − b2)c is een veelvoud van g. Omdat c en g geen priemfactoren gemeenschappelijk hebben en c = 0,23 moet (b1 − b2) een veelvoud zijn van g, en omdat b1, b2 ∈ Ag weten we ook dat 0 ≤ b1, b2 ≤ g − 1. Hieruit volgt dat |b1 − b2| ≤ g − 1. Dan kan alleen (b1 − b2) = 0, zodat b1 = b2, tegenspraak! Dus alle g getallen bc + s mod g zijn verschillend. En omdat Ag maar g elementen geeft, moeten alle elementen van Ag worden bezocht door bc + s mod g.
Met deze twee gevallen hebben we bewezen dat bc + s mod g alle elementen van Ag
doorloopt, dan en slechts dan als ggd(c, g) = 1. Hiermee is de stelling bewezen.
Met dit resultaat is het een kleine moeite om stelling 3.5.2 te bewijzen. Dit zullen we nu doen.
Bewijs. Laat p een priemgetal zijn, en a, c ∈ Zp . We willen bewijzen dat a
∈ Zp als
c0 = 0.
We berekenen het product a van twee getallen b, c ∈ Zp door er achtereenvolgens de
mult- en de norm-functie op los te laten. Het tussenproduct mult(b, c) duiden we aan met k.
a = norm(k) = norm mult(b, c)
Omdat Zp ⊂ Z∗ geldt ook dat b, c ∈ Z∗. We schrijven b, c en k uit in cijfers, bijvoorbeeld
p p
b = . . . b2
b1 b0
= (bi ). Uit vgl. (3.6) volgt dat elk cijfer ki
van k te schrijven is als
i
ki = X bz ci−z
z=0
Nu berekenen we a = norm(k). Als we nog eens naar algoritme 3 kijken, zien we dat in de regels 6 t/m 8 elk berekende cijfer ai gelijk is aan ki + di−1 mod 10. In de regels 7 en
8 wordt namelijk als het ware restdeling van ki + di−1 door p uitgevoerd; het quoti¨ent
wordt di genoemd, de rest wordt de nieuwe ai . Er geldt dus:
i i−1
ai = ki + di−1 = X bz ci−z + di−1 = X(bz ci−z ) + bi c0 + di−1 = bi c0 + s mod p
z=0
Hier is s = Pi−1 (bz ci
z ) + d
z=0
; omdat dit een eindige som in Z is, is s een geheel
z=0 −
i−1
getal, net als bi en c0. En omdat p priem is en c0 = 0, is ggd(ci , p) = 1. Hierdoor is er volgens stelling 3.5.3 voor alle mogelijke ai ∈ Ap een geschikte bi ∈ Ap te vinden
zodat ai = bi c0 + s mod g. Omdat Ap de verzameling is van alle mogelijke cijfers van
23 want als c = 0 is ggd(c, g) = g = 1
elementen van Zp , is er voor elk mogelijk cijfer ai een geschikt cijfer bi te vinden.24 We concluderen dat voor alle a, c ∈ Zp , c0 = 0 de vergelijking bc = a oplosbaar naar b is in Zp . Met andere woorden, voor alle a, c ∈ Zp waarbij c niet eindigt op het cijfer 0, is b = a ∈ Zp .
In hoofdstuk 4 zal blijken dat we handig gebruik kunnen maken van deze stelling.
3.6 Algoritme voor deling
Als afsluiting van dit hoofdstuk geven we een algoritme dat kan delen in Zg . Dit algoritme is gebaseerd op de staartdeling zoals we die in §1.2 hebben uitgevoerd. Laten we de werking van zo’n staartdeling eens nauwkeuriger bekijken. Als voorbeeld nemen we weer de berekening van 1 in Z10 die op pagina 7 staat uitgewerkt. De uitkomst van deze deling duiden we aan met c = . . . c2 c1c0, dit is dus gelijk aan . . . 667.
Om c te construeren, zochten we stap voor stap cijfers ci z´o dat het meest rechtse cijfer van 3ci gelijk was aan ai ; hiermee kon ai worden weggepoetst.25 Met andere woorden, we zochten ci zodat 3ci ≡ ai (mod 10). Zo vonden we bijvoorbeeld c0 = 7, want 3 • 7 = 21 ≡ 1 (mod 10). Hierna trokken we 21 af van a om een nieuw tussentijds product a te vinden.
In het algemeen gaat het net zo. Als we voor a, b ∈ Zg de getalwaarde van c = a ∈ Zg willen bepalen (voor zover c bestaat natuurlijk), moeten we de vergelijking ci b0 ≡ ai (mod g) oplossen naar ci . Merk op dat hier alleen het meest rechtse cijfer van b een rol speelt.
We lossen deze vergelijking op met behulp van het zogenaamde ‘uitgebreide algoritme van Euclides’. Dat is een algoritme dat voor ieder paar gehele getallen a, b de vergelijking ax + by = ggd(a, b) oplost naar x, y. Hoe en vooral waarom het algoritme werkt kunnen we hier niet in detail uitleggen; hiervoor verwijzen we naar §3.4 van [1] of hoofdstuk 1 van [5]. Het uitgebreide algoritme van Euclides hebben we (in computertaal) opgenomen als algoritme 4.
Algorithm 4 Uitgebreid algoritme van Euclides
function eucl(a, b ∈ Z) : (x, y) ∈ Z
begin
if a mod b = 0 then
result := (0, 1)
else
(x, y) := eucl(b, a mod b) result := (y, x − y • (a div b)) end
24 Bedenk dat alle cijfers van getallen in Zp tussen 0 en p − 1 liggen.
25 a = . . . a2 a1 a0 is hier het ‘tussentijdse product’ dat in het begin . . . 0001 was, vervolgens . . . 9998, et cetera.
Met dit algoritme kun je voor elke b0 , g ∈ Z de vergelijking b0 x+gy = ggd(b0, g) oplossen. Als bovendien ggd(b0 , g) = 1, dan is b0x + gy = 1 waaruit volgt dat b0x ≡ 1 (mod g). Volgens een regel van het modulorekenen geldt dan dat b0xai ≡ ai (mod g). Hiermee hebben we een mogelijkheid gevonden voor het gezochte cijfer ci dat moest voldoen aan ci b0 ≡ ai (mod g), namelijk ci = xai mod g.
Het mooie van dit algoritme is dat het je precies vertelt hoe je ci kunt construeren als ggd(b0, g) = 1. In de praktijk is het voor kleine g natuurlijk handiger om gewoon de tafel van b0 op te schrijven met grondtal g, en de ci te kiezen waarvoor het laatste cijfer van ci b0 gelijk is aan ai . Voor grote waarden van g is het algoritme van Euclides echter v´e´el sneller.
Aan de hand van het uitgebreide algoritme van Euclides cre¨eren we de functie divide(a, b), zie algoritme 5.
Algorithm 5 Divide
1: function divide(a, b ∈ Zg ) ∈ Zg
2: c := (0, 0, 0, • • • )
3: begin
4: (x, y) := eucl(b0 , g)
5: for i = 0 to ∞ do
6: begin
7: ci := xai mod g
8: a := norm(a − cb)
9: end
10: end
11: Result := c
Dit algoritme voert als het ware een staartdeling uit. In regel 7 wordt ci berekend met behulp van 4, waarna in regel 8 de waarde van het nieuwe tussenproduct a wordt bepaald.
Dit werkt alleen als ggd(b0 , g) = 1, anders geeft eucl(b0, g) de verkeerde uitkomst. Het gaat dus in ieder geval goed als g priem is en b0 ongelijk aan nul. Dit is in overeen- stemmingen met wat we eerder gezien hebben in §3.5.2.
Hoofdstuk 4 Formele invoering van het lichaam Qp
In §1.2 hebben we laten zien dat het bij deling handig is om g-adische kommagetallen toe te staan, getallen van de vorm . . . a2a1 a0.a−1a−2 . . . a−n . We zeiden toen dat we de verzameling van al deze kommagetallen Qg noemen, en dat deze verzameling eigenlijk alleen ‘zin’ heeft als g een priemgetal is. Waarom dat zo is, zal in dit hoofdstuk duidelijk worden. We veronderstellen vanaf nu dat p priem is. We defini¨eren Qp heel anders dan je zou verwachten, namelijk niet als kommagetallen maar als breuken met in de teller en noemer elementen van Zp . Later zal blijken dat deze twee ‘definities’ overeenkomen, dus al die breuken zijn als kommagetallen te schrijven.
Behalve dat Qp in sommige gevallen voordeel heeft bij het uitvoeren van delingen, heeft het een nog veel belangrijker voordeel ten opzichte van Zp . We kunnen namelijk bewijzen dat (Qp , +, ×) een lichaam is. In lichamen gaat alles erg mooi, omdat je altijd
kunt delen. Daardoor kunnen veel stellingen voor lichamen worden bewezen die voor ringen niet altijd opgaan.1 Daar gaan we hier verder niet op in; we verwijzen naar hoofdstuk 4 van [5] voor een aantal eenvoudige stellingen over ringen en lichamen.
Met de methode die we gebruiken, kun je elke willekeurige commutatieve ring met
1 zonder nuldelers (laten we deze ring Ξ noemen) uitbreiden naar een lichaam L. Dat is handig, want zo hebben we ook gelijk een formele invoering van Q vanuit Z. In dit hoofdstuk zullen we vooral in ons achterhoofd houden dat Ξ staat voor Zp en L voor Qp .
4.1 Definitie van L
We defini¨eren nu de algebra¨ısche structuur (L, +, ×), lees (Qp , +, ×)
Definitie 4.1.1.
L = n a | a, b ∈ Ξ, b = 0
b
1 Dit betekent niet dat lichamen per se rijkere structuren zijn dan ringen. In ringen kan delen soms wel en soms niet. Dat levert, voor een geschikte klasse van ringen, de mogelijkheid om iets in de trant van priemgetallen te defini¨eren en te bestuderen.
Twee ‘breuken’ a1 , a2 ∈ L worden als gelijk beschouwd volgens de regel:
b1 b2
a1 = a2
a b = a b
(4.1)
b1 b2 ⇔ 1 2 2 1
Op alle elementen a
∈ L defini¨eren we de operaties optelling en vermenigvuldiging als
volgt.
a1 + a2 := a1 b2 + a2b1
(4.2)
b1 b2
a1
b1b2
a2 := a1 a2
(4.3)
b1 × b2
b1b2
Voordat we van deze definitie uit mogen gaan, willen we eerst aantonen dat ze wel zinvol is. In dit geval komt het erop neer dat we twee stellingen moeten bewijzen.
1. De optelling en vermenigvuldiging zijn inwendig in L.
Bewijs. Wegens de inwendigheid van + en × in Ξ geldt dat a1b2 + a2b1 ∈ Ξ, dat
a1a2 ∈ Ξ en dat b1 b2 ∈ Ξ. Bovendien heeft Ξ geen nuldelers, dus b1b2 = 0. Hierdoor
zijn a1 b2 +a2 b1
1 2
b1 b2 elementen van L, dus + en × zijn inwendig in L.
2. De definitie van de som en het product zijn ondubbelzinnig. Dit houdt in dat
als a1
1
en a2
2
vervangen worden door andere elementen van Ξ die hieraan volgens
(4.1) gelijk zijn, de uitkomsten van de som en het product niet veranderen. Eerst
bewijzen we dit voor de optelling.
Bewijs. Stel dat voor de volgende vier elementen van L geldt:
a1 = c1
a2 c2
en =
(4.4)
b1 d1
b2 d2
We willen dus het volgende aantonen:
a1 + a2 = c1 + c2
(4.5)
b1 b2
d1 d2
Dit is volgens (4.2) gelijkwaardig met:
a1b2 + a2 b1 = c1d2 + c2d1
(4.6)
b1b2
d1d2
Volgens (4.1) is dit bewezen als we hebben aangetoond dat
(a1b2 + a2b1)(d1 d2) = (c1d2 + c2d1 )(b1 b2 ) (4.7) Uit (4.4) volgt bovendien met behulp van (4.1) dat
a1 d1 = c1 b1 en a2d2 = c2b2 (4.8)
Nu hebben we genoeg gegevens verzameld om te bewijzen dat vgl. (4.5) waar is.2
6)
(a1b2 + a2b1 )(d1 d2) = (a1b2)(d1d2 ) + (a2 b1 )(d1d2)
5)×
5)
= (d1d2)(a1b2) + (a2b1)(d1d2 )
= (d1d2 )(b2 a1) + (a2b1)(d1 d2) 2.=4.1 (d1a1 )(b2 d2) + (a2 d2)(d1b1)
5)
= (a1 d1)(b2d2) + (a2d2 )(d1 b1)
5)×
(4.8)
= (c1 b1)(b2d2) + (c2 b2 )(d1b1)
= (b1c1)(d2b2 ) + (b2c2)(d1b1) 2.=4.1 (b1b2)(d2c1 ) + (b2b1)(d1c2 )
5)×
6) 5)×
= (b1b2)(c1d2 ) + (b1 b2)(c2d1) = (b1 b2)(c1d2 + c2d1)
= (c1d2 + c2d1)(b1b2)
Hiermee hebben we de geldigheid van (4.7) aangetoond, en daarmee ook die van
(4.6) en (4.5). Dat laatste is precies wat we wilden bewijzen.
Nu bewijzen we de stelling voor vermenigvuldiging.
Bewijs. We gaan weer uit van de situatie in vgl. (4.4); daardoor geldt automatisch ook vgl. (4.8). We willen nu het volgende aantonen:
a1 a2 = c1 c2
(4.9)
b1 × b2
d1 × d2
Dit komt volgens (4.3) op hetzelfde neer als:
a1a2 = c1 c2
(4.10)
b1b2
d1 d2
Volgens (4.1) is dit bewezen als we hebben aangetoond dat
(a1a2 )(d1d2) = (c1c2)(b1b2) (4.11) Nu hebben we genoeg gereedschap om de stelling te bewijzen.
(a1 a2 )(d1 d2)
(4.8)
= (a1a2)(d2d1) 2.= (a1 d1)(d2a2)
5)×
5)
= (a1d1)(a2d2)
5)×
= (c1 b1 )(c2b2)
= (c1 b1 )(b2 c2) 2.=4.1 (c1c2)(b2b1)
= (c1c2)(b1b2)
Hiermee hebben we de geldigheid van (4.11) aangetoond, en daarmee ook die van
(4.10) en (4.9). En laat dat laatste nou juist ons doel zijn.
Samenvattend komt het er op neer dat we nu de algebra¨ısche structuur (L, +, ×) formeel hebben gedefinieerd, en bovendien bewezen dat de definities van + en × zinvol zijn.
2 Nummers met ´e´en haakje rechts verwijzen naar een eigenschap uit Tabel 2.2 die geldt voor Ξ. Bij- voorbeeld 5)× boven een =-teken betekent dat eigenschap 5), de commutativiteit, geldt voor de verme- nigvuldiging. Nummers met twee haakjes verwijzen naar een vergelijking, nummers zonder haakjes naar een stelling.
4.2 Lemma’s
Om te bewijzen dat L een lichaam is, hebben we twee lemma’s (hulpstellingen) nodig.
Lemma 4.2.1.
ca a
∀a, b, c ∈ Ξ, b, c = 0 :
=
cb b
Bewijs. Uit de associativiteit en commutativiteit van vermenigvuldiging in Ξ volgt dat
(ca)b = (ac)b = a(cb),
dus (ca)b = a(cb). Hieruit volgt met (4.1) dat ca = a .
cb b
Overigens geldt het lemma niet andersom. Niet voor elk paar gelijkwaardige breuken
a1 a2
b1 , b2 ∈ L is er een c ∈ Ξ te vinden zodat
ca1 = a2 en cb1 = b2
Als we bijvoorbeeld naar Ξ = Z en L = Q kijken, zien we dat 3 = 4 . Natuurlijk is
9 12
4
3 ×
4
maar 4 is geen element van Z.
3 × 9 12
Lemma 4.2.2.
∀a1, a2 , b ∈ Ξ :
a1 +
b
a2 =
b
a1 + a2
b
Bewijs. Uit (4.2), Lemma 4.2.1 en de distributiviteit in Ξ volgt:
a1 + a2 = a1b + a2b
(a1 + a2 )b
a1 + a2
b b b2 =
b2 = b
4.3 Bewijs: L is een lichaam
We gaan nu bewijzen dat (L, +, ×) een lichaam is. Hierbij maken we onder meer gebruik van de formules (4.1) t/m (4.3), van de twee lemma’s en van het feit dat (Ξ, +, ×) een commutatieve ring met 1 zonder nuldelers is.
4.3.1 Bewijzen van de eigenschappen van optelling
Als je niet meer weet wat de eigenschappen die we hier bewijzen inhouden, kun je altijd terugblikken naar Tabel 2.2.
We laten vanaf nu de verwijzingen boven de =-tekens weg, het is aan jou om te achterhalen welke eigenschappen worden toegepast. Bijna overal wordt de inwendigheid van + en × in Ξ en L, gebruikt, net als het niet bestaan van nuldelers in Ξ.
Inwendigheid. Dit hebben we al bewezen in §4.1.
Commutativiteit.
a1 + a2 = a1b2 + a2b1 = a2b1 + a1b2 = a2 + a1
b1 b2
b1 b2
b2b1
b2 b1
Associativiteit.
( a1 + a2 ) + a3
b1 b2 b3
= a1b2 + a2b1
b1b2
+ a3
b3
= (a1b2 + a2b1)b3 + a3 (b1b2) (b1b2)b3
= (a1b2)b3 + (a2b1 )b3 + a3(b1 b2 ) (b1b2)b3
= a1(b2b3) + (a2b1)b3 + (a3b1)b2
(b1 b2 )b3
= a1(b2b3) + (b3a2)b1 + (b2a3)b1
b1(b2 b3)
= a1(b2b3 ) + b3(a2 b1 ) + b2(a3 b1 ) (b1b2)b3
= a1(b2b3 ) + (b3a2 + b2a3 )b1
b1(b2b3)
= a1
b1
+ b3 a2 + b2a3
b2b3
= a1
b1
+ a2b3 + a3b2
b2 b3
= a1
b1
+ ( a2
b2
+ a3 )
b3
Nulelement van L. We duiden het nulelement van Ξ aan met 0, en het eenheidselement met 1. Hieruit leiden we af:3
a a + 0
= =
b b × 1
a × 1 + 0 × b = a + 0
b × 1 b 1
Wegens de commutativiteit van + in L geldt ook dat 0 + a
= a . Hiermee is bewezen
dat 0 het nulelement is van L.
1 b b
Tegengestelde. Voor alle a ∈ Ξ is er ook een −a ∈ Ξ zodat a + −a = 0. Nu leiden we af:
a + −a =
b b
a + −a =
b
0 = 0 × b =
b b
0 × b = 0
1 × b 1
Wegens de commutativiteit van + in L geldt ook dat −a + a
= 0 . En omdat 0
het
b b 1 1
nulelement is van L, is hiermee aangetoond dat elk element a
∈ L een tegengestelde
b ∈ L heeft.
3 Bij het bewijs van deze en de volgende stelling wordt stelling 2.4.3 gebruikt.
4.3.2 Bewijzen van de eigenschappen van vermenigvuldiging
Inwendigheid. Dit is al bewezen in §4.1.
Commutativiteit. a1
a2 = a1a2
= a2a1
= a2 × a1
b1 × b2
b1b2
b2b1
b2 b1
Associativiteit.
( a1
b1
a2 a3
× b2 b3
= a1 a2
b1 b2
a3
× b3
= (a1a2)a3
(b1b2 )b3
= a1(a2a3)
b1(b2b3)
= a1
b1
a2 a3
× b2 b3
= a1
b1
( a2
× b2
a3 )
× b3
Eenheidselement van L. We duiden het eenheidselement van Ξ weer aan met 1.
a = a × 1 =
b b × 1
a 1
b × 1
Wegens de commutativiteit van × in L geldt ook dat 1 × a = a . We concluderen dat 1
het eenheidselement van L is.
1 b b 1
Inverse. We willen bewijzen dat elke a
∈ L ongelijk aan het nulelement 0
van L, een
inverse heeft in L. Uit Lemma 4.2.1 volgt dat
0 = 0 × b = 0
1 1 × b b
voor alle b ∈ Ξ. We zijn dus klaar als we hebben bewezen dat er voor elke a ∈ L met
a = 0 een inverse is. Dat is niet moeilijk. Omdat a = 0 is namelijk b ∈ L.
a b ab
1 × (ab) 1
b × a = ba = 1 × (ab) = 1
Omdat vermenigvuldiging commutatief is in L, is ook b × a = 1 , het eenheidselement
a b 1
van L. Hiermee is bewezen dat elk element a ∈ L ongelijk aan 0 een inverse b
heeft.
b 1 a
4.3.3 Bewijs van de distributiviteit
Distributiviteit. We bewijzen eerst de links-distributiviteit:
a1 a2 a3 a1 a2b3 + a3b2 a1 (a2 b3 + a3b2)
( + ) = × =
b1 × b2 b3 b1
b2b2
b1 (b2b3)
= a1(a2 b3 ) + a1(a3b2)
b1(b2 b3)
= (a1a2)b3 + (a1a3)b2
(b1b2)b3
= (a1a2)b3
(b1b2)b3
+ (a1a3 )b2
(b1b2)b3
= (a1 a2 )b3
(b1 b2)b3
+ (a1 a3)b2
b3(b1 b2)
= (a1a2)b3
(b1b2 )b3
+ (a1a3)b2
(b3b1)b2
= a1 a2
b1 b2
+ a1 a3
b3 b1
= a1a2
b1b2
+ a1a3
b1b3
= a1
b1
a2
× b2
+ a1
b1
a3
× b3
Omdat × commutatief is in L, mogen we stelling 2.4.2 toepassen. De rechts-distributiviteit geldt daarom ook.
Met dit alles hebben we bewezen dat L een lichaam is. In het bijzonder zijn dus Q en
Qp lichamen. Dit zetten we tot slot nog even overzichtelijk in een tabel.
Commutatieve ring met 1 zonder nuldelers Daaruit geconstrueerd lichaam
Algemeen
Ξ
L
Voorbeelden
Z Zp
Q Qp
4.4 Koppeling tussen Ξ en L
We weten intu¨ıtief dat Ξ een deelverzameling is van L. Immers, voor alle a ∈ Ξ is a/1 ∈ L, en voor ons gevoel is a = a/1. Hoe logisch dat ook lijkt, het is niet echt te bewijzen. Dat komt doordat we de operaties in L heel anders gedefinieerd hebben dan
in Ξ, en je kunt in de wiskunde geen appels met peren vergelijken.
Wel kunnen we laten zien dat ons idee om a en a/1 als gelijk te beschouwen, ‘zinvol’ is. Hiervoor cre¨eren we een ‘afbeeldingsfunctie’ f , die elk element a ∈ Ξ aan het element a/1 ∈ L koppelt.
Definitie 4.4.1.
a
∀a ∈ Ξ : f (a) := 1
Het nagaan dat het zin heeft om a aan a/1 (ofwel f (a)) te koppelen, komt in dit geval hierop neer. We bewijzen drie dingen, namelijk dat f (a)+f (b) = f (a+b), dat f (a)f (b) = f (ab), en dat uit a = b volgt dat f (a) = f (b). Dat zijn drie vereisten die natuurlijk in elk geval zouden moeten gelden als f (a) op te vatten is als a. Als hieraan voldaan wordt, zegt men ook wel dat f de bewerkingen + en × in Ξ en L ‘respecteert’.
Stelling 4.4.2. De som van de afbeeldingen is gelijk aan de afbeelding van de som.
∀a, b ∈ Ξ : f (a) + f (b) = f (a + b)
Bewijs.
a b f (a) + f (b) = + =
1 1
a × 1 + b × 1 =
1 × 1
a + b
1
= f (a + b)
Stelling 4.4.3. Het product van de afbeeldingen is gelijk aan de afbeelding van het product.
∀a, b ∈ Ξ : f (a) × f (b) = f (ab)
Bewijs.
a b a × b ab
f (a) × f (b) = 1 × 1 = 1 × 1 =
= f (ab)
1
Stelling 4.4.4. Verschillende elementen hebben verschillende afbeeldingen.
∀a, b ∈ Ξ : a = b ⇒ f (a) = f (b)
Bewijs. Laat a ongelijk zijn aan b. Aanname: Stel dat f (a) = f (b). Hieruit volgt:
a b
f (a) = f (b) ⇒ 1 = 1 ⇒ a × 1 = b × 1 ⇒ a = b
Maar we hadden gesteld dat a = b, tegenspraak! We concluderen dat de aanname onjuist is, dus de stelling is juist.
We hebben nu aangetoond dat f de bewerkingen van Ξ en L respecteert. Nu heeft het zin om de verzameling Ξ als deelverzameling van L op te vatten, waarbij a en a/1 als gelijk worden beschouwd. Gelukkig maar dat we konden bewijzen dat dat ‘zin’ heeft, anders was er iets vreemds aan de hand!
4.5 Komen verschillende definities van Qp overeen?
We hebben tot nu toe twee idee¨en van Qp door elkaar heen gebruikt. In de informele beschouwing van hoofdstuk 1 kwam ons beeld van Qp hierop neer:
∀p ∈ P : Qp = {. . . a3a2a1a0 .a−1a−2 . . . a−n | ai ∈ N, 0 ≤ ai < p} (4.12) In de formele definitie van Qp in §4.1 hebben we juist gesteld dat
n a o
∀p ∈ P : Qp =
b | a, b ∈ Zp , b = 0
(4.13)
In deze paragraaf bewijzen we dat beide definities van Qp op hetzelfde neerkomen. Bo- vendien bewijzen we dat er nog een derde definitie mogelijk is die ook op hetzelfde neerkomt.
4.5.1 Plan van aanpak
We gaan uit van de formele definitie van Qp , dus van (4.13) en niet van (4.12).
We defini¨eren de deelverzameling Vp van Qp als de verzameling van breuken die
geschreven worden als a
met a ∈ Zp
en n ∈ N. Dit is duidelijk een deelverzameling van
Qp , want omdat Z ⊂ Zp is ook pn ∈ Zp ; bovendien is pn nooit nul.
Vp :=
a
pn | a ∈ Zp , n ∈ N
(4.14)
Op een soortgelijke manier defini¨eren we de deelverzameling Wp van Qp als de verzame-
ling van breuken die geschreven worden als a met a ∈ Zp en d ∈ Z .
Wp := n
d
| a ∈ Zp ; d ∈ Z≥1
o (4.15)
Omdat pn ∈ Z
is bovendien Vp
een deelverzameling van Wp , zodat
Vp ⊂ Wp ⊂ Qp (4.16)
Hierdoor gelden ook voor elementen uit Vp en Wp de vergelijkingen (4.1), (4.2) en (4.3). We willen de volgende stelling bewijzen.
Stelling 4.5.1.
Vp = Wp = Qp
Je vraagt je misschien af wat dit te maken heeft met wat bovenaan §4.5 staat, namelijk dat we bewijzen dat de verzamelingen bij (4.12) en (4.13) overeenkomen. Toch komt het bewijzen van stelling 4.5.1 op hetzelfde neer, zoals later zal blijken. Vp komt namelijk overeen met de verzameling bij (4.12).4 De verzameling Wp is de derde mogelijke definitie van Qp .
We bewijzen de stelling door aan te tonen dat Qp ⊂ Vp . Omdat Vp ⊂ Qp volgt daaruit5 dat Vp = Qp . Uit (4.16) volgt dan natuurlijk ook dat Vp = Wp = Qp , waarmee de stelling bewezen is.
Om de stelling te bewijzen hebben we een lemma nodig.
4.5.2 Lemma: goochelen met nullen
Lemma 4.5.2 is een uitbreiding van stelling 3.4.4 (zie pagina 31). Voor elk p-adisch getal
a, is pa volgens stelling 3.4.4 gelijk aan a met een nul erachter geplakt.
p × . . . a2a1 a0 = . . . a2a1 a00
4 Behalve dat we nu nog niet mogen beweren dat verzameling (4.12) gelijk is aan Qp , want dat willen we juist bewijzen.
5 zie pagina 13
Vermenigvuldigen met pn kan worden opgevat als het n keer herhaald vermenigvuldigen met p. Dus pn a is gelijk aan a met n nullen erachter geplakt.
Een eigenschap van deling in Qp is dat het vermenigvuldiging ongedaan maakt. Immers,
a × b = (a × 1) × b = a × 1 = a = a (4.17)
b 1 × b 1 1
Daarom moet deling door pn in Zp op hetzelfde neerkomen als een verschuiving van alle cijfers n plaatsen naar rechts, waarbij een rij van n nullen waar a op eindigt, wordt verwijderd. Deze nullen moeten er natuurlijk wel zijn, anders is het resultaat geen element van Zp . We mogen eventuele andere cijfers dan nullen niet “achter de komma” plaatsen en zeggen dat dit een element van Qp is, want we hebben de elementen van Qp niet gedefinieerd als rijtjes van cijfers. Dus als a eindigt op z nullen (waarbij z ook 0 kan zijn), moet gelden dat n ≤ z willen we kunnen delen door pn binnen Zp .
Lemma 4.5.2. Voor alle a = . . . a2a1 a0 ∈ Zp en n ∈ N komt vermenigvuldiging met pn
op hetzelfde neer als n nullen achter a plakken.
n nullen
pn × . . . a2a1a0 = . . . a2a1a0 0z 00}.|. . 0{
Als ai = 0 voor alle i ≤ z, en bovendien z ≥ n, dan komt deling door pn op hetzelfde neer als een rij van n nullen achter a schrappen.
. . . a2a1a0
pn = . . . an+2 an+1 an
4.5.3 Bewijs: Vp = Wp = Qp
Allereerste een verkorte notatie. De verzameling {x | x ∈ N, x ≤ p − 1}, dat zijn alle mogelijke cijfers van getallen in Zp , noemen we weer Ap .
We beschouwen een element c = a
∈ Qp . De p-adische gehele getallen a, b en c
schrijven we als . . . a3a2a1a0 , . . . b3b2 b1 b0 resp. . . . c3 c2c1c0 waarbij ai , bi , ci ∈ Ap . De
kleinste i waarvoor bi = 0 noemen we z. Het is makkelijk na te gaan dat z het aantal nullen is waar b op eindigt.
We onderscheiden 2 gevallen.
i. z = 0, dus b0 = 0. Omdat bovendien p priem is, volgt uit stelling 3.5.2 dat a ∈ Zp .
Omdat6 Zp ⊂ Vp is ook a ∈ Vp .
ii. z = 0, dus b0 = 0. Stelling 3.5.2 mogen we nu niet toepassen, want die geldt alleen als b0 = 0. Wat we wel kunnen doen, is b delen door pz . Dit komt op hetzelfde neer als bij b direct links van de komma z nullen verwijderen, zie Lemma 4.5.2. En
6 Immers, als n = 0 is a
= a = a, een vrij te kiezen element uit Zp .
omdat b op precies z nullen eindigt, is het eerste cijfer van b/pz ongelijk aan nul. Nu mogen we stelling 3.5.2 w´el gebruiken, dus
a
b/pz =: y ∈ Zp (4.18)
Omdat Vp ⊂ Qp mogen we de rekenregels voor Qp natuurlijk ook toepassen op Vp . Daarvan zullen we nu gebruik maken. De derde gelijkheid volgt uit vgl. (4.17).
y = Hieruit volgt:
a b/pz
a pz
= = (b/pz ) × pz
a × pz
b
a pz
=
b × 1
a pz
= b × 1
= a pz
b
y a
pz = b
Volgens vgl. (4.18) is y ∈ Zp , dus y/pz ∈ Vp .7 Hieruit blijkt dat a ∈ Vp .
In beide gevallen i en ii, dus voor alle a ∈ Qp ,8 is a ∈ Vp . We concluderen dat Qp ⊂ Vp .
b b
Uit vgl. (4.16) volgt dat
Hiermee is stelling 4.5.1 bewezen.
Vp = Wp = Qp (4.19)
4.5.4 Qp beschouwd als rijtjes van cijfers
Met dit resultaat kunnen we Qp voortaan beschouwen als Vp , zodat elk element van Qp kan worden opgevat als een p-adisch geheel getal gedeeld door een macht van het grondtal p. In Zp hebben we gezien dat a/pn overeenkomt met een verschuiving van alle cijfers n plaatsen naar rechts, mits a eindigt op minstens n nullen. We kunnen dit idee uitbreiden naar Qp . Hiervoor voeren we in Zp een decimale punt in rechts van elk getal, zo kunnen we bijvoorbeeld a = . . . k3k2k1 k0. schrijven. Deling door pn kunnen we weer opvatten als een verschuiving van alle cijfers n plaatsen naar rechts, waarbij cijfers ook rechts van de komma mogen staan. Zodoende kunnen we elk element a/pn ∈ Qp opvatten als een rij cijfers . . . kn+3 kn+2 kn+1 kn .kn−1 kn−2 . . . k0. Voor m ∈ N, m ≤ n komt vermenigvuldiging met pm overeen met een verschuiving van alle cijfers m plaatsen naar links, want
m a pm
a × pm
a × pm
. . . kn+1 kn .kn−1 . . . k0 × p
= =
pn 1
=
pn × 1 (pn−m × pm ) × 1
a pm
=
pn−m × pm
a
= pn−m
= . . . kn−m+1 kn−m .kn−m−1 . . . k0
Dit kan ook worden opgevat als een verschuiving van de komma m plaatsen naar rechts. Deling door pm in Qp kan dan worden opgevat als een verschuiving van de komma m
7 Immers, z is het aantal nullen is waarop b eindigt, dus z ∈ N.
8 want als i niet geldt, dan geldt ii en andersom plaatsen naar links. Een eventuele rij nullen aan het eind van het getal rechts van de komma mag worden weggedacht.
Als m ∈ N, m ≥ n is
a pm
. . . kn+1 kn .kn−1 . . . k0 × p = pn 1 =
a pm
=
pn × 1
a × (pm−n × pn )
1 × pn
m−n nullen
(a × pm−n ) × pn
1 × pn
a pm−n
=
1
= a × pm−n = . . . k3 k2k1k0 0 000}|. . . 0{
Dit komt overeen met een verschuiving van de komma m plaatsen naar rechts, waarbij de m − n lege plaatsen van een nul worden voorzien.
De gevonden resultaten ordenen we in formules. Laat c ∈ Qp , q ∈ N. We schrijven c uit in cijfers als . . . k3k2k1k0 .k−1k−2 . . . k−n . Let op: het laatste cijfer is nu k−n en niet k0, zoals hiervoor steeds het geval was.
c × pq =
. . . k−n+3 k−n+2 k−n+1 k−n
q−n nullen
z0 00}.|. . 0{
als n < q
. . . k−n+3 k−n+2 k−n+1 k−n als n = q
. . . k−q+2 k−q+1 k−q .k−q−1 k−q−2 . . . k−n als n > q
Voor deling door pq in Qp gelden de volgende formules. Het is mogelijk dat n = 0 zodat c ∈ Zp , dan is dus c = . . . k3k2 k1k0. Als in dat geval c bovendien rechts eindigt op z nullen, dan mogen de nullen achter de komma natuurlijk weggedacht worden in c/pq . In formule:
c
. . . kz+3 kz+2 kz+1 kz
z−q nullen
0 00}.|. . 0{
als n = 0, z > q
pq =
. . . k
q+3
kq+2
kq+1 kq
als n = 0, z = q
. . . kq+2 kq+1 kq .kq−1kq−2 . . . kz als n = 0, 0 ≤ z < q
. . . kq+2 kq+1 kq .kq−1kq−2 . . . k−n als n = 0
Dat laatste geval, n = 0, is natuurlijk het meest voorkomend. De eerste drie gevallen zijn uitzonderingen.
Een voordeel van getallen uit Qp voorstellen als rijtjes van cijfers
. . . k3k2 k1k0.k−1k−2 . . . k−n
is dat er gemakkelijk mee kan worden gerekend. Stel dat we twee willekeurige p-adische getallen a1/pn1 en a2 /pn2 bij elkaar willen optellen. Zoals we weten geldt:
a1 a2
a1pn2 + a2pn1
pn1 + pn2 =
pn1 +n2
a1pn2 en a2 pn1 zijn de oorspronkelijke p-adische getallen waarbij de komma n1 + n2
plaatsen naar links geschoven is, en de n2 resp. n1 lege plekken met nullen zijn opgevuld.
Deze p-adische gehele getallen tellen we op volgens het optel-algoritme, en vervolgens “delen” we door pn1 +n2 , ofwel we plaatsen de komma n1 + n2 stappen naar links. Nu hebben we de gevraagde som berekend.
Deze optelling klinkt misschien ingewikkeld, maar het gaat eigenlijk net zo als we bij (afgeronde) re¨ele getallen gewend zijn. Op pagina 8 hebben we zelfs al zo’n optelling uitgevoerd.
Ook vermenigvuldigen is makkelijk als elementen a/pn ∈ Qp als rijtjes voorgesteld
worden. We weten namelijk:
a1 a2
a1 a2
pn1 × pn2 = pn1 pn2
a1 en a2 zijn de oorspronkelijke p-adische getallen waarbij “de komma weggedacht wordt”. We berekenen a1a2 met het vermenigvuldig-algoritme en plaatsen de komma links van het (n1 + n2 )-de cijfer, waarmee het gevraagde product gevonden is. Ook dit gaat eigenlijk net zo als vermenigvuldiging van (afgeronde) re¨ele getallen.
Hoofdstuk 5 Weergave van g-adische getallen
Hoe kun je Zg of Qp grafisch weergeven? En welke problemen treden daarbij op? Daar- over gaat dit hoofdstuk.
5.1 Chaos
De verzamelingen N, Z, Q en R kunnen we afbeelden op een getallenlijn. In principe kunnen we dit ook met C doen, we zouden bijvoorbeeld 523.7104 . . . + 8.9076 . . . i kunnen afbeelden naar het punt 502038.79100746 . . . van de re¨ele getallenlijn. In het algemeen zouden we C kunnen afbeelden naar R met de afbeeldingsfunctie
an . . . a0 .a−1 . . . + bn . . . b0.b−1 . . . i 7→ an bn . . . a0b0.a−1b−1 . . .
Op deze manier stelt elk punt op de re¨ele getallenlijn precies ´e´en complex getal voor. De vraag is alleen wat deze afbeelding voor zin heeft. Het blijkt veel waardevoller te zijn om C af te beelden naar een getallenvlak door een imaginaire as loodrecht op de re¨ele as toe te voegen.
Iets dergelijks doet zich voor bij de p-adische getallen. We zouden simpelweg een afbeeldingsfunctie f : Qp → R kunnen defini¨eren die elk getal omkeert.
f : . . . a2a1a0.a−1 . . . a−n 7→ a−n . . . a−1.a0a1a2 . . .
Dit hebben we eens uitgeprobeerd met Q5, voor het gemak hebben we alleen naar de deelverzameling Z5 daarvan gekeken. Met Microsoft Excel hebben we voor alle elementen x ∈ Z5, afgerond op 5 decimalen, de waarde van f (x) berekend en die op de getallenlijn uitgezet. Vervolgens lieten we een grafiek van de functie g(x) = x + b tekenen, waarbij b een constant 5-adisch geheel getal was. Dit is een lineaire functie; als je deze grafiek voor x, b ∈ R zou tekenen, zou er een rechte lijn ontstaan. In Zg blijkt dat niet het
geval te zijn, zie Figuur 5.1 op pagina 57. De x-as is de re¨ele getallenlijn op het interval [0, 1) in grondtal 5, voor de y-as geldt hetzelfde. Voor b hebben we hier . . . 42424244 genomen. Op het eerste gezicht ziet dit er best ordelijk uit, hoewel minder dan een rechte lijn. Toch heeft elk schuin ‘streepje’ op zijn beurt ook weer een grillige structuur.
Figuur 5.1: Grafiek van g(x) = x + b met x, b ∈ Z5
Ook blijkt dat op hoe meer decimalen nauwkeurig je de getallen benadert, hoe grilliger deze structuur is. Als je op ´e´en streepje van de grafiek inzoomt, lijkt dit heel veel op de grafiek zelf. We vermoeden dat het plaatje een fractal is als je de getallen met oneindige nauwkeurigheid zou benaderen.
Vervolgens hebben we de punten van Figuur 5.1 laten verbinden door een vloeiende lijn. Hierbij werd de volgorde x = . . . 001, . . . 002, . . . 003, . . . 010, • • • aangehouden. Op deze manier is Figuur 5.2 ontstaan, zie pagina 58. Het is een prachtig en bizar plaatje, maar het is niet duidelijk wat de betekenis ervan is. In ieder geval ziet het er chaotisch uit, het is bepaald geen rechte
lijn zoals bij de re¨ele getallen het geval zou zijn. De afbeelding doet denken aan de zogenaamde Lorenz-attractor, een oplossing van een bepaalde differentiaalvergelijking die oorspronkelijk is opgesteld om een natuurkundig verschijnsel te modelleren. De Lorenz-attractor blijkt een fractal te zijn.1 Of dit werkelijk iets met de afbeelding van p-adische getallen te maken heeft weten we niet; misschien heeft het vooral te maken met de vreemde volgorde van het verbinden van punten, en met de manier waarop Excel vloeiende lijnen tekent.
1 Bron: [2], hoofdstuk 20
Figuur 5.2: Opnieuw de grafiek van g(x) = x + b, nu verbonden door een lijn.
5.2 Het g-adische getallenvlak
We hebben gezien dat een poging om 5-adische getallen op een getallenlijn uit te zetten, absurde resultaten oplevert. Uit Figuur 5.1 blijkt bijvoorbeeld dat er problemen ontstaan als we een bepaalde grootte aan een 5-adisch getal willen toekennen. Het is voor de hand liggend om af te spreken dat het meest rechtse cijfer het meeste invloed heeft op de grootte van het getal, gevolgd door het cijfer links daarvan, et cetera. Dan is bijvoorbeeld . . . 13 > . . . 11 en . . . 29 > . . . 31. Maar ook geldt:
. . . 13 + . . . 18 = . . . 31 < . . . 29 = . . . 11 + . . . 18
Blijkbaar gaat, volgens deze definitie van de relatie >, de regel a > b ⇒ a + c > b + c niet altijd op. Dit verschijnsel wordt goed ge¨ıllustreerd door Figuur 5.1.
Voor een beter begrip van g-adische getallen is het afbeelden op een getallenlijn dan ook geen goed idee, het schept alleen maar verwarring. Daarom pakken we het anders aan. In plaats van een getallenlijn tekenen we een getallenvlak.
We werken weer in Z5 , voor andere Zg en voor Qp gaat het analoog. Allereerst tekenen we een grote cirkel, hierin bevinden zich alle elementen van Z5 . Deze cirkel delen we op in vijf kleinere cirkels, zie Figuur 5.3. Deze vijf cirkels stellen de mogelijkheden voor van a0 waarbij a = . . . a2 a1 a0 een willekeurig element van Z5 is. Voor het gemak nummeren we de cirkels met
0, 1, . . . , 4.
Laten we bijvoorbeeld a0 = 2 kiezen. Binnen cirkel 2 tekenen we weer vijf cirkels, zij geven de mogelijkheden van a1 weer. Hieruit kiezen we weer een cirkel en delen deze ook op. Zo kunnen we in theorie oneindig lang doorgaan. Met ieder cijfer wordt a beter benaderd, evenals de plaats van het getal in het 5-adische getallenvlak.
We zien nu grafisch weergegeven dat hoe verder een cijfer van een g-adisch getal naar links staat, hoe minder invloed het heeft op (de plaats van) het getal. Opnieuw is het resultaat een prachtig plaatje, dit keer is het duidelijk dat het een fractal is. Het behoeft geen uitleg hoe het g-adische getallenvlak er in het algemeen uitziet voor andere g.
Figuur 5.3: Het 5-adische getallenvlak
Antwoorden
1.2.1 a. . . . 99999, dit is inderdaad wat we op blz. 5 gezien hebben. b. . . . 22140 c. Nee. Het overlenen gebeurt van rechts naar links, dit kan daarom geen invloed hebben op cijfers die je eerder hebt berekend.
1.2.2 a. . . . 00001423423 = 1423423 in grondtal 5 in Z. b. 1
= . . . 2857142857143, dit heeft
285714 als repeterende staart. 1 is niet te berekenen in Z10 , het eerste cijfer 1 van . . . 00001 is namelijk niet weg te poetsen met een getal uit de tafel van 8. c. In de tafel van 7 heeft ieder getal in grondtal 10 een ander rechtercijfer; elk rechtercijfer komt precies 1 keer voor. Daardoor is elk cijfer op precies ´e´en manier weg te poetsen in een deling. In de tafel van 8 komt elk even rechtercijfer twee keer voor, en elk oneven rechtercijfer nul keer. Dit alles heeft te maken met het feit dat ggd(7, 10) = 1 en ggd(8, 10) = 2 = 1.
2.3.1 a. Nee. 7) en 8) zijn geen zinvolle beweringen als er geen nulelement is vastgelegd. b. Allemaal behalve 4) voor optelling en 4) voor vermenigvuldiging. c. Z: allemaal behalve 4) voor vermenigvuldiging. Voor Q, R en C gelden alle regels.
2.3.2 b. Z is een commutatieve ring met 1 zonder nuldelers. Q, R en C zijn lichamen.
3.1.1 . . . b3 b2 b1 b0 waarbij b0 = g − a0 , en bi = g − ai − 1 voor alle i > 0.
3.1.2 Er geldt: [ei ] × [bi ] = [ Pi
ek bi
k ] = [e b
] = [1b ] = [b ], want als k > 0 is e
= 0 en
dan is ook ek bi−k = 0.
k=0 −
0 i−0 i i k
Bibliografie
[1] Frits Beukers, Getaltheorie voor Beginners, Epsilon Uitgaven 2008
[2] Jan van de Craats, Vervolgboek Wiskunde, Pearson Education 2009
[3] David A. Madore, A first introduction to p-adic numbers, 2000
[4] Fernando Quadros Gouvˆea, p-adic Numbers: An Introduction, Springer-Verlag 2003
[5] M. Riemersma, Algebra, Epsilon Uitgaven 2003
[6] http://en.wikipedia.org/wiki/P-adic number
[7] http://en.wikipedia.org/wiki/Algebraic structure
[8] http://nl.wikipedia.org/wiki/Verzameling %28wiskunde%29
[9] http://nl.wikipedia.org/wiki/Polynoom
[10] http://en.wikipedia.org/wiki/Modular arithmatic#The congruence relation
(Zie de genoemde pagina’s van Wikipedia voor de primaire bronnen.)
REACTIES
:name
:name
:comment
1 seconde geleden