p-adische getallen

Wiskunde D

Profielwerkstuk

7.7 / 10
6e klas vwo
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.)

Log in op Scholieren.com

Maak een profiel aan of log in om te stemmen.

Geef dit een cijfer

Omdat je geen profiel hebt kan je stem niet aangepast worden.
Maak hier een profiel aan.

bijlagen1

249_p-adisch_getallen.pdf

Let op

De verslagen op Scholieren.com zijn gemaakt door middelbare scholieren en bedoeld als naslagwerk. Gebruik je hoofd en plagieer niet: je leraar weet ook dat Scholieren.com bestaat.

Heb je een aanvulling op dit verslag? Laat hem hier achter.

voeg reactie toe

Sneller en makkelijker reageren?
Login of maak een profiel aan

9757
 

reacties