4
Modulair rekenen
Oefening 4.1. Merk op dat 25 ·92 = 2592. Bestaat er een ander getal van de vorm 25ab dat gelijk is aan 25 ·ab ? (Met 25ab bedoelen we een getal waarvan a het cijfer voor de tientallen voorstelt en b het cijfer voor de eenheden.) Oplossing 4.1 We zoeken een a en b uit N[0, 9] waarvoor geldig is dat 32 · ab = 2500 + 10a + b. We kunnen dit oplossen via trial and error. We zoeken dus een veelvoud van 32 dat gelegen is tussen 2500 en 2600. De enige mogelijkheden zijn 79 · 32 = 2528, 80 · 32 = 2560 en 81 · 32 = 2592. We zien dat de enige oplossing de gegeven oplossing is. Een meer gestructureerde oplossingingsmethode gaat als volgt. Bekijk de gelijkheid 32ab = 2500 + 10a + b nu modulo 2. Dan vinden we dat b even moet zijn: we kunnen b vervangen door 2b, met b ∈ N[0, 4]. Dan volgt er 32a2b = 2500 + 10a + 2b. Bekijken we nu deze gelijkheid modulo 5, dan vinden we 2a2b = 2b (mod 5), of dus a2b ≡ b (mod 5): we mogen delen door 2 omdat ggd(2, 5) = 1. Dit betekent dat b een kwadraat moet zijn modulo 5, maar de enige kwadraten modulo 5 zijn 1 en −1 = 4. Immers, modulo 5 is 12 ≡ 1, 22 ≡ 4, 32 ≡ 4, 42 ≡ 1 (mod 5). Hieruit volgt ook dat 1 de enige vierde macht is, want (−1)2 ≡ 1 (mod 5). Als we b = 4 proberen, dan vinden we dat a8 ≡ 4 (mod 5), maar zoals net opgemerkt, is 4 geen vierde macht modulo 5, dus dit kan niet. Rest ons enkel nog b = 1, dus b = 2, en we vinden 32a2 = 2500 + 10a + 2. We hebben echter a = 9 nodig om met 32a2 boven de 2500 uit te tornen (32 · 82 = 2048 < 2500), zodat we met (a, b) = (9, 2) de enige oplossing hebben. Oefening 4.2. Vind alle m zodanig dat 1066 ≡ 1776 (mod m). Oplossing 4.2 We zoeken een m waarvoor geldt dat 1066 + x · m = 1776. Dit kunnen we herschrijven als x · m = 710. We vinden dat m een deler moet zijn van 710 en dat alle delers van 710 in aanmerking komen. Oefening 4.3. Zoek een positief natuurlijk getal zodanig dat de helft een kwadraat is, een derde is een derdemacht en een vijfde is een vijfdemacht. Oplossing 4.3 Stel dat x een oplossing is, dan volgt uit de opgave dat zowel 2, 3 als 5 het getal x delen. Stellen we nu x = 2a 3b 5c , dan moet 2a−1 3b 5c een kwadraat zijn, waaruit volgt dat a − 1, b en c even zijn. Wegens de tweede voorwaarde moet 2a 3b−1 5c een derde macht zijn waardoor a, b − 1 en c deelbaar moeten zijn door 3. Volgens de laatste voorwaarde besluiten we analoog dat a, b en c − 1 deelbaar zijn door 5. Samengevat is a ≡ a ≡ a ≡
a oplossing van 1 0 0
(mod 2) (mod 3) , (mod 5)
b is oplossing van b ≡ 0 (mod 2) b ≡ 1 (mod 3) , b ≡ 0 (mod 5)
en a = 15 is de kleinste oplossing
en b = 10 is de kleinste oplossing
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
12
en c is oplossing van c ≡ 0 (mod 2) c ≡ 0 (mod 3) , c ≡ 1 (mod 5)
en c = 6 is de kleinste oplossing
We vinden dus als kleinste oplossing x = 215 310 56 . Oefening 4.4. Zoek de oplossing(en) (x, y) van het volgende stelsel over Z7 . ( x + 2y = 4 4x + 3y = 4 Zoek eveneens de oplossingen over Z5 . Oplossing 4.4 De determinant van de co¨effici¨entenmatrix is gelijk aan −5. Over Z7 : De rang van het stelsel is 2 want −5 ≡ 2 (mod 7) 6≡ 0 (mod 7). Er is dus een unieke oplossing. Beschouw deze vergelijkingen nu modulo 7: x + 2y = 4 4x − 4y = 4 Uit de laatste x = y + 1, wat na invullen in de eerste geeft: 3y = 3. Hieruit volgt y = 1 en x = 2. We vinden de unieke oplossing (x, y) = (2, 1). Over Z5 : De rang van het stelsel is 1 want −5 ≡ 0 (mod 5). Het stelsel betekent modulo 5 x + 2y = 4 −x − 2y = 4, dus het is strijdig (4 = -4).
4.1
Stelling van Fermat
Oefening 4.5. Bereken de rest na deling van 347 door 23. Oplossing 4.5 Aangezien ggd(3, 23) = 1, kunnen we de kleine stelling van Fermat toepassen, met name 322 ≡ 1 (mod 23). Dus 347 ≡ 322·2+3 ≡ 33 (mod 23) ≡ 27 (mod 23) ≡ 4 (mod 23). Dus de rest van 347 na deling door 23 is 4. Oefening 4.6. Wat is het laatste cijfer van het getal 794 ? Er wordt gevraagd naar 794 (mod 10). Omdat 7 en 10 copriem zijn, kunnen we de kleine stelling van 92 92 Fermat toepassen: 7Φ(10) = 74 ≡ 1 (mod 10). Bijgevolg is 794 = 74 4 · 72 ≡ 1 4 · 49 ≡ 9 (mod 10). Het laatste cijfer van 794 is dus een 9. Meteen hebben we bewezen dat elke macht van 7, waarbij de exponent 2 modulo 4 is, eindigt op een 9. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
13
Oefening 4.7. Bereken de kleinste positieve macht n zodat voor elke a ∈ Z, met ggd(a, 1020) = 1, n a ≡ 1 (mod 15) an ≡ 1 (mod 20) an ≡ 1 (mod 17) Oplossing 4.7 Merk vooreerst op dat kgv(15, 20, 17) = 1020. Elk element dat inverteerbaar is modulo 1020 is dus ook inverteerbaar modulo 15, 17 en 20 (omdat inverteerbaar zijn modulo hetzelfde is als onderling ondeelbaar zijn met). We kunnen de vraag dan ook herformuleren als volgt: zoek het kleinste gemeen veelvoud van k1 , k2 en k3 waarbij k1 , k2 en k3 de kleinste positieve natuurlijke getallen zijn waarvoor ak1 ≡ 1 (mod 15), ak2 ≡ 1 (mod 20) en ak3 ≡ 1 (mod 17). Gebruikmakend van de stelling van Euler vinden we gemakkelijk k1 = Φ(15) = 8, k2 = Φ(20) = 8 en k3 = Φ(17) = 16. Het antwoord op de vraag is dus n = 16.
4.2
Lineaire congruenties
Oefening 4.8. Los op a. b. c. d.
e. 10x ≡ 25 (mod 38) f. 10x ≡ 25 (mod 35) g. 10x ≡ 25 (mod 37)
40x ≡ 777 (mod 1777) 3x ≡ 6 (mod 18) 15x ≡ 26 (mod 51) 7x ≡ 27 (mod 200)
Oplossing 4.8 a. (a) Aangezien ggd(40, 1777) = 1, zal de congruentie juist ´e´en oplossing hebben. We moeten eerst het invers element van 40 in Z1777 bepalen, bijvoorbeeld via het algoritme van Euclides – zeg maar de algemene oplossingsmethode.
1777 − 44 · 40 = 17 40 − 2 · 17 = 6 17 − 2 · 6 = 5 6−5=1 5−5·1=0 1=6−5 = 6 − (17 − 2 · 6) = 3 · 6 − 17 = 3 · (40 − 2 · 17) − 17 = 3 · 40 − 7 · 17 = 3 · 40 − 7 · (1777 − 44 · 40) = 311 · 40 − 7 · 1777. Beschouw deze laatste vergelijking modulo 1777 en we bekomen 311 · 40 ≡ 1 (mod 1777). We vinden dus, omdat ggd(40, 1777) = 1, dat 40x ≡ 777 (mod 1777) equivalent is aan x ≡ 311 · 777 (mod 1777), wat op zijn beurt equivalent is aan x ≡ 1752 (mod 1777). Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
14
(b) Veel korter vinden we dat 40x ≡ 777 ≡ −1000 (mod 1777). Hieruit volgt dat x ≡ −25 ≡ 1752 (mod 1777). b. Aangezien ggd(3, 18) = 3 een deler is van 6 is 3x ≡ 6
(mod 18)
gelijkwaardig met x≡2
(mod 6)
c. d. e. f.
Geen oplossingen: ggd(15, 51) = 3 - 26. Dit is equivalent met 7x ≡ 427 (mod 200), dus x ≡ 61 (mod 200). Geen oplossingen: ggd(10, 38) = 2 - 25. Verschillende oplossingen: ggd(10, 35) = 5 | 25, dus we delen zowel a, b als de modulus door 5. We vinden 2x ≡ 5 (mod 7), of dus 2x ≡ 12 (mod 7) en dus x ≡ 6 (mod 7). g. 10 is inverteerbaar modulo 37. We kunnen al vereenvoudigen tot 2x ≡ 5 (mod 37) of 2x ≡ 42 (mod 37) dus de oplossingen zijn x ≡ 21 (mod 37).
4.3
Chinese Reststelling
Oefening 4.9. Los op 2x ≡ 1 3x ≡ 2 4x ≡ 3
(mod 5) (mod 7) (mod 11)
Oplossing 2x 3x 4x
x ≡ 3 (mod 5) (mod 5) x ≡ 3 ⇔ ⇔ (mod 7) x ≡ 10 (mod 7) x ≡ 3 x ≡ 9 (mod 11) x ≡ 9 (mod 11)
4.9 ≡ 1 ≡ 2 ≡ 3
(mod 5) (mod 7) (mod 11)
De inverse van 2 in Z5 is 3, aangezien 2 · 3 ≡ 1 (mod 5). De andere worden analoog berekend. We stellen een uitdrukking als de volgende voorop als oplossing voor dit stelsel: x ≡ 3 · y1 · 7 · 11 + 3 · y2 · 5 · 11 + 9 · y3 · 5 · 7
(mod 5 · 7 · 11)
Substitutie van deze uitdrukking in het stelsel geeft: 77y ≡ 1 (mod 5) 2y ≡ 1 (mod 5) 1 1 y1 ≡ 3 55y2 ≡ 1 (mod 7) ⇔ 6y ≡ 1 (mod 7) ⇔ y ≡ 6 2 2 35y ≡ 1 (mod 11) 2y3 ≡ 1 (mod 11) y3 ≡ 6 3
(mod 5) (mod 7) (mod 11)
Hieruit volgt dat x ≡ 3 · 3 · 7 · 11 + 3 · 6 · 5 · 11 + 9 · 6 · 5 · 7 ≡ 3573 ≡ 108 (mod 385). Oefening 4.10. Zoek het kleinste natuurlijk getal x dat aan het volgend stelsel voldoet. 2x ≡ 3 (mod 5) 7x ≡ 11 (mod 13) 6x ≡ 8 (mod 14)
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
15
Oplossing 4.10 2x ≡ 3 (mod 5) 7x ≡ 11 (mod 13) 6x ≡ 8 (mod 14) Dit is snel x x x
2x ≡ 3 (mod 5) ⇔ 7x ≡ 11 (mod 13) 3x ≡ 4 (mod 7)
te herleiden tot het volgend equivalent stelsel ≡ 4 ≡ 9 ≡ 6
(mod 5) (mod 13) (mod 7).
Toepassen van het algoritme bij de Chinese reststelling geeft dan x = 4 · y1 · 13 · 7 + 9 · y2 · 5 · 7 + 6 · y3 · 5 · 13 met y1 · 13 · 7 ≡ 1 y2 · 5 · 7 ≡ 1 y · 5 · 13 ≡ 1 3
(mod 5) y1 ≡ 1 (mod 13) ⇔ y2 ≡ 3 (mod 7) y3 ≡ 4
(mod 5) (mod 13) (mod 7)
Dus x ≡ 4 · 13 · 7 + 9 · 3 · 5 · 7 + 6 · 4 · 5 · 13 ≡ 2869 (mod 455) ≡ 139 (mod 455). Oefening 4.11. Zoek het kleinste 5x ≡ −2x ≡ 8x ≡ Oplossing 4.11 We reduceren het 5x ≡ −2x ≡ 4x ≡
(mod 5 · 13 · 7)
natuurlijk getal dat oplossing is van 13 (mod 17) 3 (mod 5) 12 (mod 14)
stelsel achtereenvolgens tot: 13 (mod 17) 5x ⇔ 3 (mod 5) 3x 4x 6 (mod 7) x ⇔ x x
≡ 30 (mod 17) ≡ 3 (mod 5) ≡ 20 (mod 7) ≡ 6 ≡ 1 ≡ 5
(mod 17) (mod 5) (mod 7)
Hieruit volgt dan dat x ≡ 6 · y1 · 5 · 7 + 1 · y2 · 17 · 7 + 5 · y3 · 17 · 5 (mod 17 · 5 · 7), waarbij (mod 17) y1 · 5 · 7 ≡ 1 (mod 17) y1 ≡ 1 y2 · 17 · 7 ≡ 1 (mod 5) ⇐⇒ y2 ≡ 4 (mod 5) y · 17 · 5 ≡ 1 (mod 7) y ≡ 1 (mod 7) 3 3 Hieruit volgt dat x ≡ 6 · 1 · 5 · 7 + 1 · 4 · 17 · 7 + 5 · 1 · 17 · 5 ≡ 1111 (mod 595) ≡ 516 (mod 595).
(mod 17 · 5 · 7)
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
16
Oefening 4.12. a. Ga na welke van de volgende congruenties oplosbaar zijn: 18x ≡ 6
(mod 12)
x≡8
(mod 13)
35x ≡ 25
(mod 14)
25x ≡ −5
(mod 15)
28x ≡ 13
(mod 16)
b. Los het stelsel, gevormd door de oplosbare congruenties, op. Oplossing 4.12
1. We weten dat ax ≡ b (mod m) oplosbaar is als ggd(a, m)|b. We gaan na in welke congruenties deze voorwaarde is voldaan. 18x x 35x 25x 28x
≡ 6 ≡ 8 ≡ 25 ≡ −5 ≡ 13
(mod (mod (mod (mod (mod
12) 13) 14) 15) 16)
: : : : :
ggd(18, 12) ggd(1, 13) ggd(35, 14) ggd(25, 15) ggd(28, 16)
= = = = =
6 1 7 5 4
en en en en en
6|6 1|8 7 6 | 25 5| − 5 4 6 | 13.
Dit betekent dat de derde en de vijfde congruentie niet oplosbaar zijn. 2. We lossen het volgende stelsel op: 6 18x ≡ x ≡ 8 25x ≡ −5
(mod 12) (mod 13) (mod 15)
3x ⇐⇒ x 5x x ⇐⇒ x x
≡ 1 (mod 2) ≡ 8 (mod 13) ≡ −1 (mod 3) ≡ 1 ≡ 8 ≡ 1
(mod 2) (mod 13) (mod 3).
Aangezien 2, 13 en 3 onderling priem zijn, kunnen we het algoritme bij de Chinese reststelling toepassen. De oplossing van het stelsel is dus van de vorm: x ≡ 1 · y1 · 13 · 3 + 8 · y2 · 2 · 3 + 1 · y3 · 2 · 13 We bekomen y · 13 · 3 ≡ 1 (mod 2) 1 1 · y1 ≡ 1 y2 · 2 · 3 ≡ 1 (mod 13) ⇐⇒ 6 · y2 ≡ 1 y · 2 · 13 ≡ 1 (mod 3). 2·y ≡ 1 3 3
(mod 2 · 3 · 13).(∗)
(mod 2) (mod 13) (mod 3).
We vinden snel y1 ≡ 1, y2 ≡ 11 en y3 ≡ 2. Substitutie van deze waarden in (∗) geeft x ≡ 39 + 8.11.6 + 2.26 ≡ 619 ≡ 73
(mod 78).
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
17
Oefening 4.13. Zoek het kleinste natuurlijk getal dat een oplossing is van volgend stelsel. ( 5x ≡ 36 (mod 91) ≡ 38
x
(mod 70)
Oplossing 4.13 We brengen het stelsel eerst naar de vorm x ≡ bi (mod mi ). Hiertoe zoeken we het invers element van 5 in Z91 . (36 + 4 · 91 = 400) Het stelsel herleidt zich tot ( x ≡ 80 (mod 91) (∗) x ≡ 38 (mod 70) Om de Chinese reststelling te kunnen toepassen, moeten 91 en 70 copriem zijn. Maar we vinden dat ggd(91, 70) = 7, waarbij 91 = 7 · 13 en 70 = 7 · 10. We kunnen nu de Chinese reststelling in de omgekeerde richting toepassen en vinden dat x ≡ 80 (mod 91) gelijkwaardig is met het stelsel ( x ≡ 80 (mod 7) x
≡ 80
(mod 13)
Om dit in te zien, kunnen we x ≡ 80 (mod 91) ook schrijven als x = 80 + a · 91 = 80 + a · 7 · 13. Als we deze uitdrukking modulo 7 nemen, bekomen we x ≡ 80 (mod 7) en analoog x ≡ 80 (mod 13). Anderzijds heeft het stelsel gevormd door deze twee vergelijkingen juist 1 oplossing modulo 7 · 13 = 91. We vinden dat x ≡ 80 (mod 91) noodzakelijk gelijk moet zijn aan de unieke oplossing van het stelsel. Analoog is x ≡ 38 (mod 70) gelijkwaardig met het stelsel ( x ≡ 38 (mod 7) x
≡ 38
(mod 10)
Wanneer we nu stelsel (*) willen oplossen, bekomen we een stelsel met 4 congruenties. We zouden deze stap de ontbinding van het stelsel kunnen noemen. x ≡ 80 (mod 7) x ≡ 3 (mod 7) x ≡ 80 (mod 13) x ≡ 2 (mod 13) ⇔ x ≡ 38 (mod 7) x ≡ 3 (mod 7) x ≡ 38 (mod 10) x ≡ 8 (mod 10) Aangezien de eerste en de derde congruentie dezelfde restklasse modulo 7 hebben, is dit geen strijdig stelsel. We kunnen dus 1 van deze congruenties weglaten en stellen volgende oplossing voorop: x ≡ 3 · y1 · 130 + 2 · y2 · 70 + 8 · y3 · 91 Het stelsel herleidt zich tot 130y1 ≡ 1 (mod 7) 70y2 ≡ 1 (mod 13) 91y ≡ 1 (mod 10) 3
⇔
4y1 5y2 y 3
(mod 7 · 10 · 13)
≡1
(mod 7)
≡1
(mod 13)
≡1
(mod 10)
⇔
y1 y2 y 3
≡2
(mod 7)
≡8
(mod 13)
≡1
(mod 10)
We vinden nu als oplossing x ≡ 3 · 2 · 130 + 2 · 8 · 70 + 8 · 1 · 91 ≡ 2628 ≡ 808
(mod 910).
Met andere woorden, als we geen stijdigheid bekomen bij het ontbinden van het stelsel, vinden we een unieke oplossing modulo kgv(m1 , m2 ). Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
18
Oefening 4.14. Zoek het kleinste natuurlijk getal dat een oplossing is van volgend stelsel. ( x ≡ 15 (mod 32) x
≡ 12
(mod 72)
Uit de eerste vergelijking volgt dat x ≡ 15 ≡ 7 (mod 8). Uit de tweede vergelijking volgt dat x ≡ 12 ≡ 4 (mod 8). Deze zijn in tegenspraak met elkaar, dus het stelsel is strijdig: de verzameling oplossingen van dit stelsel is ledig en bezit dus geen kleinste element. Oefening 4.15. Zoek het kleinste natuurlijk getal dat een oplossing is van volgend stelsel. ( x ≡ 5 (mod 62) x ≡ 17 (mod 14)
(4)
Omdat de moduli 62 en 14 niet copriem zijn, kunnen we de Chinese reststelling niet toepassen. We kunnen echter wel ´e´en van de moduli, bijvoorbeeld 62, delen door 2, zodat we wel onderling ondeelbare moduli hebben. Inderdaad: als x een oplossing is van (4), zal x zeker een oplossing zijn van ( x ≡ 5 (mod 31) (5) x ≡ 17 (mod 14). Omgekeerd, als x voldoet aan (5), dan zijn er twee mogelijkheden modulo 62: x ≡ 5 (mod 62) ∨ x ≡ 36 (mod 62). Wegens de tweede vergelijking weten we echter dat x ≡ 1 (mod 2), zodat noodzakelijk het eerste geval geldt. Bijgevolg voldoet x aan (4). We kunnen het gereduceerde stelsel oplossen. We hebben wegens de Chinese reststelling een unieke oplossing modulo 31 · 14 = 434. We mogen op zoek gaan naar een oplossing van de vorm x = 5 · y1 · 14 + 3 · y2 · 31. Invullen hiervan in (5) geeft:
(
14y1 ≡ 1 ≡ 32 (mod 31) 31y2 ≡ 1 (mod 14)
( ⇔
7y1 ≡ 16 ≡ −77 (mod 31) 3y2 ≡ 15 (mod 14)
We vinden dus y1 = −11, y2 = 5 en dit geeft x = 5 · (−11) · 14 + 3 · 5 · 31 = −305 ≡ 129
(mod 434).
129 zal dus het kleinste natuurlijk getal zijn dat aan de gegeven congruenties voldoet. Oefening 4.16. Toon aan dat het berekenen van 56791 (mod 391) te herleiden valt tot het oplossen van het stelsel ( X ≡ 10 (mod 17) X ≡ 19 (mod 23). Zoek de oplossingen van dit stelsel. Oplossing 4.16 Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
19
Deel 1 Reductie van de vergelijking tot lineaire congruenties. We zoeken een oplossing voor de vergelijking X ≡ 56791
(mod 391)
Omdat 391 = 17 · 23, is het berekenen van 56791 (mod 391) equivalent met het zoeken naar een oplossing van het stelsel ( X ≡ 56791 (mod 17) X ≡ 56791 (mod 23) We willen gebruik maken van de stelling van Euler. Omdat Φ(17) = 16 hebben we dat 516 ≡ 1 (mod 17). We kunnen berekenen dat 6791 = 424 · 16 + 7, dus 56791 ≡ 57 (mod 17). Analoog, omdat Φ(23) = 22 en 6791 ≡ 15 (mod 22), is het stelsel equivalent met ( X ≡ 57 (mod 17) X ≡ 515 (mod 23) Nu is 57 ≡ 5 · 253 ≡ 5 · 83 ≡ 40 · 64 ≡ 6 · (−4) ≡ −24 ≡ 10 (mod 17). Analoog is 515 ≡ 257 · 5 ≡ 27 · 5 ≡ 32 · 20 ≡ 9 · (−3) ≡ −27 ≡ −4 ≡ 19 (mod 23). Het stelsel is dus equivalent met ( X ≡ 10 (mod 17) X ≡ 19 (mod 23). Deel 2 Oplossing van de stelsels lineaire congruenties. We zoeken een oplossing hiervan met behulp van de Chinese reststelling. Stel X = 10 · y1 · 23 + 19 · y2 · 17. Dan is (
23y1 ≡ 1 17y2 ≡ 1
(mod 17) (mod 23)
(
6y1 ≡ 18 (mod 17) 17y2 ≡ 1 (mod 23)
(
y1 ≡ 3 (mod 17) y2 ≡ 19 (mod 23).
⇐⇒ ⇐⇒
Na substitutie van y1 en y2 vinden we dat X ≡ 180 (mod 391) de oplossing is van het stelsel. Oefening 4.17. Stel dat een jaar een schrikkeljaar is, m.a.w. 366 dagen bevat, als en slechts als het jaartal een veelvoud is van 4. Veronderstel ook dat een maancyclus bestaat uit 29 dagen. Op zaterdag 1 juni 1991 was het volle maan. In welk jaar, volgend op een schrikkeljaar, zal het voor het eerst volle maan zijn op een dinsdag 2 juni? Oplossing 4.17 Deel 1: Het stelsel congruentievergelijkingen. Zij x het aantal dagen na 1 juni 1991 waarop het voor de eerste maal volle maan is op een dinsdag 2 juni, in een jaar volgend op een schrikkeljaar. Dan voldoet x aan x ≡ 0 (mod 29) x ≡ 3 (mod 7) x ≡ 732 (mod 1461),
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
20
want een maancyclus bestaat uit 29 dagen, wat de eerste vergelijking geeft. De volle maan moet op een dinsdag zijn, dus 3 dagen na een zaterdag, waaruit de tweede vergelijking volgt. De derde vergelijking wordt als volgt bekomen: De eerst mogelijke oplossing is 2 juni 1993 en dit is 732 dagen na 1 juni 1991. De volgende kandidaat-oplossingen zijn 2 juni 1997, 2 juni 2001, . . . Tussen twee mogelijke oplossingen liggen er dus 4 jaar en 4 jaar bestaat uit 3 · 365 + 366 = 1461 dagen. Dus x ≡ 732 (mod 1461). Deel 2: De oplossing van het stelsel. 1461 = 3 · 487, dus de drie moduli zijn onderling ondeelbaar, zodat de Chinese reststelling van toepassing is. We zoeken een oplossing voor x van de vorm x = 3 · 29 · 1461 · y1 + 732 · 7 · 29 · y2 . Invullen in het stelsel geeft ons om te beginnen 29 · 1461 · y1 ≡ 1
(mod 7)
⇔ 1 · 5 · y1 ≡ 15 ⇔ y1 ≡ 3
(mod 7) (mod 7),
maar het bepalen van de inverse van 203 = 7 · 29 modulo 1461 zal niet zo vlot gaan. We gebruiken het algoritme van Euclides: 1461 = 7 · 203 + 40 203 = 5 · 40 + 3 40 = 13 · 3 + 1 3 = 3 · 1. 1 = 40 − 13 · (203 − 5 · 40) = 66 · 40 − 13 · 203 = 66 · (1461 − 7 · 203) − 13 · 203 = 66 · 1461 − 475 · 203. Uit de laatste gelijkheid volgt dat −475 ≡ 986 de gezochte inverse is van 203 (mod 1461), dus y2 ≡ 986 (mod 1461). We vinden x ≡ 3 · 29 · 1461 · 3 + 732 · 7 · 29 · 986 ≡ 88392
(mod 7 · 29 · 1461)
(mod 296583).
Daar 88392 = 60 · 1461 + 732, is het voor de eerste keer volle maan op dinsdag 2 juni, in een jaar volgend op een schrikkeljaar, in het jaar 1991 + 60 · 4 + 2 = 2233.
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
21
4.4
Hogeregraadscongruenties
Oefening 4.18. Zoek de oplossingen van Z 6 ≡ 29 (mod 35). Oplossing 4.18 Merk op dat 35 = 5 · 7. De vergelijking is dus equivalent met het stelsel ( ( Z 6 ≡ 29 (mod 5) Z 6 ≡ 4 (mod 5) ⇐⇒ 6 Z ≡ 29 (mod 7) Z 6 ≡ 1 (mod 7) De laatste vergelijking is wegens de stelling van Fermat altijd voldaan, van zodra Z 6≡ 0 (mod 7). Anderzijds, aangezien terug wegens de stelling van Fermat, Z 4 ≡ 1 (mod 5) (indien inverteerbaar) is de eerste vergelijking Z 6 ≡ 4 (mod 5) gelijkwaardig met Z 2 ≡ 4 (mod 5) en dus Z ≡ ±2 (mod 5). Er volgt dus dat alle oplossingen van de gegeven vergelijking precies deze waarden van Z zijn waarvoor Z ≡ ±2 (mod 5) en die geen 7-voud zijn. Oefening 4.19. Zoek alle oplossingen van de vergelijking y 2 = 2158
(mod 2479),
als je weet dat 2479 = 37 · 67. Oplossing 4.19
Aangezien 2479 = 37 · 67, is deze congruentie gelijk aan volgend stelsel: ( y 2 ≡ 2158 ≡ 12 (mod 37) y 2 ≡ 2158 ≡ 14 (mod 67). Deel 1 Reductie van de vergelijkingen tot lineaire congruenties. We zoeken met behulp van het Legendresymbool of 12 en 14 een kwadraatrest zijn respectievelijk modulo 37 en 67. " # " # " # " # " # " # 12 4 3 3 37 1 = · =1· = = =1 37 37 37 37 3 3 "
14 67
#
" =
2 67
# " ·
7 67
#
" = (−1) ·
7 67
#
" = (−1) · (−1) ·
67 7
#
" =
4 67
# = 1.
Beide Legendresymbolen zijn 1. Beide vergelijkingen hebben dus oplossingen in y. We hadden dit ook onmiddellijk kunnen vinden, want het stelsel kunnen we herschrijven als ( y 2 ≡ 12 (mod 37) ≡ 49 (mod 37) y 2 ≡ 14 (mod 67) ≡ 81 (mod 67). De eerste equivalantie heeft als oplossingen y ≡ ±7 (mod 37), de tweede heeft als oplossingen y ≡ ±9 (mod 67). Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
22
Dit geeft dan vier stelsels lineaire congruenties: ( ( y ≡ 7 (mod 37) y ≡ −7 (mod 37) ∨ ∨ y ≡ 9 (mod 67) y ≡ −9 (mod 67) (
y ≡ 7 (mod 37) ∨ y ≡ −9 (mod 67)
(
y ≡ −7 (mod 37) y ≡ 9 (mod 67).
Deel 2 Oplossing van de stelsels lineaire congruenties. Het eerste en tweede, net zoals het derde en vierde stelsel, hebben tegengestelde oplossingen die, wegens de Chinese reststelling, uniek zijn modulo 37 · 67 = 2479. S1 Een oplossing voor het eerste stelsel is y = 7 · 67 · y1 + 9 · 37 · y2 . Substitutie in het eerste stelsel geeft ( ( 67y1 ≡ 1 (mod 37) y1 ≡ 21 ⇔ 37y2 ≡ 1 (mod 67) y2 ≡ 29
(mod 37) (mod 67),
immers: de inverse van 30 (mod 37) volgt uit het algoritme van Euclides, analoog als de inverse van 37 (mod 67) uit dezelfde berekening volgt. We berekenen namelijk 67 = 1 · 37 + 30 37 = 1 · 30 + 7 30 = 4 · 7 + 2 7 = 3 · 2 + 1. 1 = 7−3·2 = 7 − 3 · (30 − 4 · 7) = −3 · 30 + 13 · 7 = −3 · 30 + 13 · (37 − 30) = 13 · 37 − 16 · 30 = 13 · 37 − 16 · (67 − 37) = −16 · 67 + 29 · 37. Deze laatste vergelijking modulo 67 nemen levert ons het ene resultaat, terwijl modulo 37 we het andere gezochte resultaat vinden. Beide waarden voor y1 en y2 geven y ≡ 7 · 67 · 21 + 9 · 37 · 29 ≡ 2153
(mod 37 · 67)
(mod 2479).
S2 De oplossing voor het tweede stelsel is dan y ≡ −2153
(mod 2479) ≡ 326
(mod 2479).
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
23
S3 Het derde stelsel heeft als oplossing: y = 7 · 67 · y1 − 9 · 37 · y2 Substitutie in het derde stelsel geeft ( 67 · y1 ≡ 1 (mod 37) 37 · y2 ≡ 1 (mod 67) Deze vergelijkingen werden reeds opgelost bij stelsel 1, namelijk y1 = 21 en y2 = 29. We vinden dus y ≡ 7 · 67 · 21 − 9 · 37 · 29 ≡ 192
(mod 2479)
(mod 2479).
S4 De oplossing voor het vierde stelsel is dan y ≡ −192
(mod 2479) ≡ 2287
(mod 2479).
Oefening 4.20. Los het volgende stelsel op: ( z2 ≡ 2 (mod 7) z 2 ≡ 81
(mod 101)
Oplossing 4.20 Deel 1: Reductie van de vergelijkingen tot lineaire congruenties. De eerste vergelijking is equivalent met z2 ≡ 9
(mod 7)
⇔
z ≡ ±3
(mod 7).
De tweede vergelijking impliceert z ≡ ±9
(mod 101).
Deel 2: Oplossing van de stelsels lineaire congruenties. We zoeken dus een oplossing van de vier stelsels (voor elke mogelijke combinatie van + en − in ±): ( z ≡ ±3 (mod 7) z ≡ ±9
(mod 101).
We zoeken de vier oplossingen van de vorm z = (±3) · 101 · y1 + (±9) · 7 · y2 . Invullen van deze gedaante van z levert ( 101y1 ≡ 1 (mod 7) 7y2
≡1
(mod 101)
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
24
Om de inversen te bepalen, voeren we het algoritme van Euclides uit: 101 = 14 · 7 + 3 7=2·3+1 1=7−2·3 = 7 − 2 · (101 − 14 · 7) = −2 · 101 + 29 · 7. We vinden dus dat ( y1 ≡ −2 ≡ 5 y2
≡ 29
(mod 7)
(mod 101)
Na substitutie van y1 en y2 in de vorm van z geeft dit z ≡ (±3) · 101 · 5 + (±9) · 7 · 29
(mod 7 · 101)
≡ {514, 312, 193, 395} (mod 707).
Oefening 4.21. Los op: ( x4 ≡ 17 (mod 19) x2 ≡ 5 (mod 59) Oplossing 4.21
Deel 1 Reductie van de vergelijkingen tot lineaire congruenties. De eerste vergelijking is equivalent met x4 ≡ 17
(mod 19) ≡ 36
(mod 19)
m x2 ≡ ±6
(mod 19).
Dus x2 ≡ 6 (mod 19) of x2 ≡ −6 (mod 19) ≡ 13 (mod 19). We onderzoeken met behulp van het Legendre symbool of 6 en 13 kwadraatresten zijn (mod 19). " # " # " # " # " # " # 6 3 2 19 2 1 = · = (−1) · · = (−1) · · (−1) = 1 19 19 19 3 19 3 en "
13 19
#
" =
19 13
#
" =
6 13
#
" =
2 13
# " ·
3 13
#
" =
2 13
# " ·
13 3
#
" = (−1) ·
1 3
# = −1.
We vinden dat 6 een kwadraatrest is (mod 19), maar dat 13 geen kwadraatrest is (mod 19). De vergelijking x2 ≡ 13 (mod 19) heeft geen oplossingen.
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
25
Het origineel stelsel is herleid tot ( x2 ≡ 6 (mod 19) x2 ≡ 5 (mod 59). De eerste vergelijking is equivalent met x2 ≡ 25 (mod 19), dus x ≡ ±5 (mod 19), en de tweede vergelijking kan herschreven worden als x2 ≡ 64 (mod 59) zodat x ≡ ±8 (mod 59). Besluit: de vergelijkingen ( x ≡ ±5 (mod 19) x ≡ ±8 (mod 59) geven vier stelsels lineaire congruenties. Deel 2 Oplossing van de stelsels lineaire congruenties. S1 Beschouw ( x ≡ 5 x ≡ 8
(mod 19) (mod 59).
Een oplossing hiervoor is x = 5 · 59 · y1 + 8 · 19 · y2 . Substitutie in het eerste stelsel geeft ( ( y1 ≡ 10 59 · y1 ≡ 1 (mod 19) ⇔ y2 ≡ 28 19 · y2 ≡ 1 (mod 59).
(mod 19) (mod 59).
Waarbij we het algoritme van Euclides gebruikt hebben: 59 − 3 · 19 = 2 19 − 9 · 2 = 1 1 = 19 − 9 · (59 − 3 · 19) = 28 · 19 − 9 · 59. Hieruit volgt dat y1 = 10 en y2 = 28. Substitutie van deze waarden in de uitdrukking van x geeft x ≡ 5 · 59 · 10 + 8 · 19 · 28 ≡ 480
(mod 19 · 59)
(mod 1121).
S2 Als een onmiddellijk gevolg heeft het stelsel ( x ≡ −5 (mod 19) x ≡ −8 (mod 59) x ≡ −480 (mod 1121) ≡ 641 (mod 1121) als oplossing. S3 Analoog is een oplossing voor ( x ≡ 5 (mod 19) x ≡ −8 (mod 59) gelijk aan x ≡ 5 · 59 · y1 − 8 · 19 · y2
(mod 19 · 59).
Substitutie van y1 = 10 en y2 = 28 geeft x ≡ 936 (mod 1121). Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
26
S4 Tenslotte is het tegengestelde van deze oplossing, de oplossing van ( x ≡ −5 (mod 19) x ≡ 8 (mod 59). Oefening 4.22. Los op: ( x3 ≡ 5 (mod 11) x4 ≡ 38 (mod 43). Oplossing 4.22
Deel 1 Reductie van de vergelijkingen tot lineaire congruenties. De eerste vergelijking oplossen in Z11 geeft X3 ≡ 5
(mod 11) ⇔ X ≡ 3
(mod 11)
x 1 2 3 4 5 6 7 8 9 10 x2 1 4 9 5 3 3 5 9 4 1 x3 1 8 5 9 4 7 2 6 3 10 Voor de tweede vergelijking vinden we dat X 4 ≡ 38 ≡ 81 (mod 43), waaruit volgt dat X 2 ≡ 9 (mod 43) of X 2 ≡ 34 (mod 43). We moeten nu onderzoeken of 34 al dan niet een kwadraat is modulo 43 aan de hand van de Legendresymbolen. 2 17 43 9 34 We berekenen 34 = = (−1) · = (−1) · = −1. We vinden 43 43 43 17 17 43 = −1 waaruit volgt dat X 2 ≡ 34 (mod 43) geen oplossingen heeft. Besluit We bekomen twee stelsels lineaire congruenties: ( ( X ≡ 3 (mod 11) X ≡ 3 (mod 11) ∨ X ≡ 3 (mod 43) X ≡ 40 (mod 43). Deel 2 Oplossing van de stelsels lineaire congruenties. S1 Voor het eerste stelsel is de oplossing X ≡ 3 (mod 11 · 43) ≡ 3 (mod 473). S2 Een oplossing voor het tweede stelsel is X = 3 · y1 · 43 + 40 · y2 · 11. Substitutie in het stelsel geeft ( 43y1 ≡ 1 (mod 11) 11y2 ≡ 1 (mod 43)
( ⇔
y1 ≡ 10 (mod 11) y2 ≡ 4 (mod 43).
Het algoritme van Euclides geeft 1 = 4 · 11 − 43. We vinden X ≡ 3 · 10 · 43 + 40 · 4 · 11 ≡ 212 (mod 473). Oefening 4.23. Geef alle oplossingen van x2 = 1526 (mod 1829).
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
27
Oplossing 4.23 Aangezien 1829 = 59 · 31 kan de opgave herleid worden tot het volgende stelsel: ( x2 ≡ 1526 (mod 59) ≡ 51 (mod 59) x2 ≡ 1526 (mod 31) ≡ 7 (mod 31). Deel 1 Reductie van de vergelijkingen tot lineaire congruenties. We zoeken met behulp van het Legendresymbool of 51 een kwadraatrest is modulo 59 en of 7 een kwadraatrest is modulo 31. " # " # " # 51 17 3 = · . 59 59 59 We bekijken deze twee Legendresymbolen afzonderlijk: " # " # " # " # " # 17 59 8 4 2 = = = · = 1. 59 17 17 17 17
"
3 59
#
" = (−1) ·
59 3
#
" = (−1) ·
2 3
# = (−1) · (−1) = 1.
We vinden dat " # 51 = 1. 59 Anderzijds is " # " # " # " # " # 7 31 3 7 1 = (−1) · = (−1) · = = = 1. 31 7 7 3 3 De twee Legendresymbolen zijn 1, waaruit volgt dat beide vergelijkingen hebben oplossingen in x. We vinden voor de eerste vergelijking dat x2 ≡ 51 (mod 59) ≡ 169 (mod 59), dus x ≡ ±13 (mod 59). De tweede vergelijking levert het volgende op: x2 ≡ 7 (mod 31) ≡ 100 (mod 31), dus x ≡ ±10 (mod 31). We bekomen de volgende vier stelsels lineaire congruenties: ( ( x ≡ 10 (mod 31) x ≡ −10 (mod 31) ∨ ∨ x ≡ 13 (mod 59) x ≡ −13 (mod 59) (
x ≡ −10 (mod 31) ∨ x ≡ 13 (mod 59)
(
x ≡ 10 (mod 31) x ≡ −13 (mod 59).
Deel 2 Oplossing van de stelsels lineaire congruenties. Het eerste en tweede, net zoals het derde en vierde stelsel, hebben tegengestelde oplossingen die, wegens de Chinese reststelling, uniek zijn modulo 31 · 59 = 1829.
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
28
S1 Een oplossing voor het eerste stelsel is x = 13 · 31 · x1 + 10 · 59 · x2 . Het Algoritme van Euclides geeft 1 = 10 · 59 − 19 · 31. Substitutie van de oplossing in het stelsel geeft ( ( 59y1 ≡ 1 (mod 31) y1 ≡ 10 (mod 31) ⇔ 31y2 ≡ 1 (mod 59) y2 ≡ 40 (mod 59)
x ≡ 13 · 31 · 40 + 10 · 59 · 10 ≡ 72
(mod 59 · 31)
(mod 1829).
S2 De oplossing voor het tweede stelsel is dan x ≡ −72
(mod 1829) ≡ 1757
(mod 1829).
S3 Het derde stelsel heeft als oplossing: x = 13 · 31 · x1 − 10 · 59 · x2 Substitutie in het derde stelsel geeft ( ( y1 ≡ 10 59y1 ≡ 1 (mod 31) ⇔ y2 ≡ 40 31y2 ≡ 1 (mod 59)
(mod 31) (mod 59)
De oplossing van het stelsel wordt nu: x ≡ 13 · 31 · 40 − 10 · 59 · 10 ≡ 1075
(mod 1829)
(mod 1829).
S4 De oplossing voor het vierde stelsel is dan x ≡ −1075
(mod 1829) ≡ 754
(mod 1829).
Oefening 4.24. Los het volgende stelsel met lineaire en kwadratische congruenties over Z op. (mod 12) 5x ≡ 7 6x ≡ 15 x2 ≡ 9
(mod 21)
(mod 20)
Oplossing 4.24 De eerste vergelijking is equivalent met x = −1 (mod 12). Bij de tweede delen we co¨effici¨ent, constante en modulus door 3 en vinden we 2x ≡ 5 (mod 7). Wegens de Chinese reststelling (omgekeerd toegepast) kunnen we dit stelsel equivalent ontbinden in x ≡ −1 (mod 3) (mod 4) x ≡ −1 x ≡ −1 x2 ≡ 9 ≡ 1 2 x ≡9≡4
(mod 7)
(mod 4) (mod 5).
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
29
Om hiervan een oplossing te zoeken, bekijken we de laatste vergelijkingen. We vinden dat 9 een kwadraatrest is, zowel modulo 4 als modulo 5. We vinden alvast dat x moet voldoen aan ( x ≡ ±1 (mod 4) x ≡ ±2
(mod 5).
Echter, modulo 4 is er geen andere keuze dan x ≡ −1, want dit wordt ge¨eist door een andere vergelijking. We zoeken dus de (twee) oplossingen van het stelsel (mod 12) x ≡ −1 x ≡ −1 x ≡ ±2
(mod 7)
(mod 5).
Zoeken we een x = −1 · y1 · 7 · 5 + (−1) · y2 · 12 · 5 + (±2) · y3 · 12 · 7, dan vinden we (mod 12) 35y1 ≡ 1 12 · 5y2 ≡ 1 12 · 7y ≡ 1 3
(mod 7) (mod 5)
ofte y1 ≡ −1 y2 ≡ 2 y ≡ −1 3
(mod 12) (mod 7) (mod 5).
en we vinden x = 83, 167
(mod 420).
Oefening 4.25. Zoek alle oplossingen voor de congruentie X 2 + 6X − 31 ≡ 0
(mod 72).
Oplossing 4.25 Deze congruentie (mod 72) is equivalent met het stelsel ( X 2 + 6X − 31 ≡ 0 (mod 8) X 2 + 6X − 31 ≡ 0 (mod 9) m (
m (
X 2 + 6X + 1 ≡ 0 (mod 8) X 2 + 6X + 5 ≡ 0 (mod 9)
X ≡ 1, 5 (mod 8) X ≡ 4, 8 (mod 9).
Er zijn dus 4 stelsels die opgelost moeten worden: ( ( X ≡ 1 (mod 8) X ≡ 1 (mod 8) ∨ ∨ X ≡ 4 (mod 9) X ≡ 8 (mod 9) Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
30
(
X ≡ 5 X ≡ 4
(mod 8) ∨ (mod 9)
(
X ≡ 5 (mod 8) X ≡ 8 (mod 9).
De oplossingen hiervoor zijn X ∈ {49, 17, 13, 53}
(mod 72).
Een alternatieve oplossing kan erin bestaan om eerst de term in X te elimineren. Dan vinden we, met Y = X + 3: X 2 + 6X − 31 ≡ 0
(mod 72)
2
(X + 3) − 9 − 31 ≡ 0
(mod 72)
Y 2 ≡ 40 Dit is equivalent met ( Y 2 ≡ 40 ≡ 0 Y
2
≡ 40 ≡ 4
(mod 72)
(mod 8)
⇔
(mod 9)
( Y Y
≡ 0 of 4 ≡ ±2
(mod 8)
(mod 9).
De oplossingen die we in elk van de vier gevallen vinden, zijn precies weer {49, 17, 13, 53} (mod 72). Oefening 4.26. Wanneer bezit de vergelijking 5X 2 + 8X + 1 ≡ 0
(mod p),
p priem, p ≥ 13, een oplossing? Oplossing 4.26 De vergelijking bezit een oplossing " #als de discriminant 44 een kwadraatrest (mod p) is, m.a.w. als 11 een 11 = 1. kwadraatrest (mod p) is, dus p Uit de kwadratische wederkerigheidswet volgt " # " # p 11 = 1 = (−1)5(p−1)/2 = (−1)(p−1)/2 =1· p 11 en dit impliceert, aangezien " # p = (−1)(p−1)/2 . 11
11 p
= 1, dat
"
# p Deel 1: = −1 = (−1)(p−1)/2 . 11 Dan is (p − 1)/2 oneven en dus p ≡ 3 (mod 4). Aangezien p geen kwadraatrest is (mod 11), is p ≡ 2, 6, 7, 8, 10 (mod 11), dus p, p ≥ 13, is een priemgetal dat voldoet aan de vergelijkingen ( p ≡ 2, 6, 7, 8, 10 (mod 11) p ≡3
(mod 4)
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
31
en dit impliceert p ≡ 35, 39, 7, 19, 43 (mod 44). " # p = 1 = (−1)(p−1)/2 . Deel 2: 11 Dan is (p − 1)/2 even en dus p ≡ 1 (mod 4). Aangezien p een kwadraatrest is (mod 11), is p ≡ 1, 3, 4, 5, 9 (mod 11). Dus hier voldoet p aan de vergelijkingen ( p ≡ 1, 3, 4, 5, 9 (mod 11) p ≡1
(mod 4)
en dit betekent p ≡ 1, 25, 37, 5, 9 (mod 44). We concluderen dat deze vergelijking oplossingen heeft als p ≥ 13, p priem, congruent is met 1, 5, 7, 9, 19, 25, 35, 37, 39 of 43 modulo 44. Oefening 4.27. Hoeveel primitieve elementen bezit het veld Z16 ? Welke orde kan een niet-primitief element van Z16 hebben en hoeveel elementen van die orde zijn er? Oplossing 4.27 Om een primitief element te vinden, moeten we eerst alle elementen vinden die copriem zijn met 16. Er zijn juist Φ(16) = Φ(24 ) = 23 = 8 elementen van Z[1, 16] copriem aan 16, namelijk {1, 3, 5, 7, 9, 11, 13, 15}. Van deze elementen moeten we de orde bepalen. Dit is het kleinste natuurlijk getal t waarvoor geldt dat at ≡ 1 (mod 16). Om niet voor alle elementen een groot aantal berekeningen te moeten maken, zullen we de theorie moeten gebruiken. Aangezien aΦ(m) ≡ 1 (mod m) vinden we al dat elke t ≤ 8. We weten ook dat de mogelijke ordes van deze getallen een deler moet zijn van 8, we hebben dus enkel 1, 2, 4 en 8 als mogelijke ordes van deze elementen. Een element wordt primitief element genoemd als t = 8. Verder hebben we dat als de orde van een element a gelijk is aan t, ak eveneens orde t heeft als en slechts als ggd(k, t) = 1. Hieruit kunnen we reeds besluiten dat als we een primitief element a vinden, er minstens Φ(8) = 4 primitieve elementen zijn, namelijk a, a3 , a5 en a7 (die wegens primitiviteit van a allemaal verschillend zijn). Deze voorbeschouwingen zullen we kunnen gebruiken bij de berekeningen. De orde van 1 is gelijk aan 1. Beschouw nu a = 3. We vinden 32 ≡ 9 (mod 16) 33 ≡ 27 ≡ 11 4 3 ≡ 3 · 11 ≡ 33
(mod 16) ≡ 1
(mod 16)
De orde van 3 is gelijk aan 4, maar ook de orde van 33 ≡ 11 (mod 16) is gelijk aan 3. We vinden ook dat de orde van 32 ≡ 9 (mod 16) kleiner of gelijk is aan 2, maar aangezien enkel 1 als orde 1 heeft, vinden we dat de orde van 9 gelijk is aan 2. Beschouw nu a = 5. We vinden 52 ≡ 25 ≡ 9
(mod 16).
Aangezien we de orde van 9 al kennen, vinden we dat de orde van 5 gelijk is aan 4. Ook de orde van 53 ≡ 5 · 9 ≡ 13 (mod 16) is gelijk aan 4. Hieruit kunnen we ook meteen besluiten dat er geen primitieve elementen zijn, aangezien er geen 4 elementen meer over zijn. Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
32
We moeten nu nog de orde van 7 en 15 bepalen. We vinden dat 73 ≡ 49 ≡ 1 (mod 16), de orde van 7 is dus gelijk aan 2. Uit (−1)2 ≡ 1 (mod 16), volgt dat ook de orde van −1 ≡ 15 gelijk is aan 2. We vatten dit samen in volgende tabel: x 3 5 7 9 11 13 15 orde 4 4 2 2 4 4 2
Opgeloste oefeningen Relaties en Structuren, hoofdstuk 4
33
