Wiskunde bovenbouw · Grades 10–12

29Getaltheorie

De getaltheorie bestudeert de gehele getallen: deelbaarheid, priemgetallen, resten. Lang gold ze als de zuiverste van de zuivere wiskunde; vandaag beschermt ze elke betaling op het internet: het RSA-systeem steunt op de stellingen van Bézout, Gauss en Fermat die in dit hoofdstuk bewezen worden.

29.1 Deelbaarheid en euclidische deling

Definitie 29.1 (Deelbaarheid)

Zij $a, b \in \Z$ . We zeggen dat $b$ het getal $a$ deelt, genoteerd $b \mid a$ , als er een $k \in \Z$ bestaat met $a = kb$ . We zeggen dan ook dat $a$ een veelvoud van $b$ is.

Propositie 29.2

Geldt $c \mid a$ en $c \mid b$ , dan deelt $c$ elke gehele combinatie $au + bv$ ( $u, v \in \Z$ ). Geldt $a \mid b$ en $b \mid a$ met $a,b \in \N$ , dan is $a = b$ . Geldt $a \mid b$ en $b \neq 0$ , dan is $\abs a \leq \abs b$ .

Bewijs. Schrijf $a = kc$ en $b = lc$ : dan is $au + bv = (ku + lv)c$ . De overige punten volgen uit $\abs{a} = \abs{k}\,\abs{b}$ met $\abs k \geq 1$ zodra $b = ka \neq 0$ . ∎

Stelling 29.3 (Euclidische deling)

Zij $a \in \Z$ en $b \in \N^*$ . Er bestaat precies één paar $(q, r) \in \Z \times \N$ met

a = bq + r \qquad\text{en}\qquad 0 \leq r < b .

Hierbij is $q$ het quotiënt en $r$ de rest.

Bewijs. Bestaan. De verzameling van de veelvouden van $b$ die $a$ niet overschrijden heeft een grootste element $bq$ (ze is niet leeg en naar boven begrensd); stel $r = a - bq$ . Wegens de maximaliteit is $b(q+1) > a$ , dus $0 \leq r < b$ . Uniciteit. Geldt $bq + r = bq' + r'$ met $0 \leq r, r' < b$ , dan is $b(q - q') = r' - r$ met $\abs{r' - r} < b$ : een veelvoud van $b$ met absolute waarde kleiner dan $b$ is noodzakelijk $0$ , dus $r = r'$ en $q = q'$ . ∎

29.2 Congruenties

Definitie 29.4 (Congruentie)

Zij $n \in \N^*$ . Twee gehele getallen $a$ en $b$ heten congruent modulo $n$ , genoteerd $a \equiv b \pmod n$ , als $n \mid (a - b)$ — gelijkwaardig: als $a$ en $b$ dezelfde rest hebben bij de euclidische deling door $n$ .

Propositie 29.5 (Verenigbaarheid met de bewerkingen)

Geldt $a \equiv b \pmod n$ en $c \equiv d \pmod n$ , dan is

a + c \equiv b + d, \qquad ac \equiv bd, \qquad a^k \equiv b^k \ (k \in \N) \pmod n .

Bewijs. $n$ deelt $(a-b) + (c-d) = (a+c) - (b+d)$ , en ook $ac - bd = a(c - d) + d(a - b)$ is een veelvoud van $n$ . De regel voor de machten volgt met inductie uit die voor het product. ∎

Methode 29.6 (Machten modulo $n$ berekenen)

Om $a^k \bmod n$ te berekenen, herleid je eerst het grondtal modulo $n$ , zoek je daarna een kleine macht van $a$ die congruent is met $\pm1$ , en gebruik je die om de exponent in te korten. Bijvoorbeeld $2^{100} \bmod 7$ : omdat $2^3 = 8 \equiv 1 \pmod 7$ en $100 = 3\times33 + 1$ ,

2^{100} = \left(2^{3}\right)^{33} \times 2 \equiv 1^{33}\times 2 = 2 \pmod 7 .

29.3 Ggd, Bézout en Gauss

Definitie 29.7 (Ggd)

Zij $a$ en $b$ gehele getallen die niet allebei nul zijn. De grootste gemene deler $\gcd(a, b)$ is het grootste gehele getal dat zowel $a$ als $b$ deelt. Is $\gcd(a,b) = 1$ , dan heten $a$ en $b$ relatief priem.

Propositie 29.8 (Algoritme van Euclides)

Geldt $a = bq + r$ ( $b \neq 0$ ), dan is $\gcd(a, b) = \gcd(b, r)$ . Door de euclidische deling te herhalen bereken je dus $\gcd(a,b)$ : de ggd is de laatste rest verschillend van nul.

Bewijs. Elke gemene deler van $a$ en $b$ deelt $r = a - bq$ (Propositie 29.2) en is dus een gemene deler van $b$ en $r$ ; en omgekeerd, want $a = bq + r$ . De twee paren hebben dezelfde gemene delers, dus dezelfde ggd. Het algoritme stopt omdat de resten een strikt dalende rij van niet-negatieve gehele getallen vormen. ∎

Voorbeeld 29.9

$\gcd(252, 198)$ : $252 = 198 + 54$ ; $198 = 3\times54 + 36$ ; $54 = 36 + 18$ ; $36 = 2 \times 18 + 0$ . Dus $\gcd(252,198) = 18$ .

Stelling 29.10 (Identiteit van Bézout)

Zij $a$ en $b$ gehele getallen die niet allebei nul zijn, en $d = \gcd(a,b)$ . Er bestaan $u, v \in \Z$ met

au + bv = d .

In het bijzonder zijn $a$ en $b$ relatief priem als en slechts als $au + bv = 1$ voor zekere gehele getallen $u$ en $v$ .

Bewijs. Doorloop het algoritme van Euclides achterwaarts: elke rest is een gehele combinatie van de twee voorgaande, en de begingegevens $a$ en $b$ zijn combinaties van zichzelf; door aflopend te substitueren is de laatste rest $d$ verschillend van nul een gehele combinatie van $a$ en $b$ . (In Voorbeeld 29.9: $18 = 54 - 36 = 54 - (198 - 3\times54) = 4\times54 - 198 = 4(252 - 198) - 198 = 4\times252 - 5\times198$ .)

Voor de gelijkwaardigheid: is $\gcd(a,b) = 1$ , dan levert Bézout $u$ en $v$ ; omgekeerd deelt elke gemene deler van $a$ en $b$ ook $au + bv = 1$ , zodat $\gcd(a,b) = 1$ . ∎

Stelling 29.11 (Lemma van Gauss)

Zij $a, b, c \in \Z$ . Geldt $a \mid bc$ en $\gcd(a, b) = 1$ , dan is $a \mid c$ .

Bewijs. Bézout geeft $au + bv = 1$ ; vermenigvuldig met $c$ : $acu + bcv = c$ . Beide termen van het linkerlid zijn veelvouden van $a$ (de tweede omdat $a \mid bc$ ), en dus is $c$ dat ook. ∎

Gevolg 29.12

Geldt $a \mid c$ , $b \mid c$ en $\gcd(a,b) = 1$ , dan is $ab \mid c$ .

Bewijs. Schrijf $c = ak$ . Uit $b \mid ak$ en $\gcd(a,b)=1$ geeft Gauss $b \mid k$ , zeg $k = bl$ ; dan is $c = abl$ . ∎

29.4 Priemgetallen

Definitie 29.13 (Priem)

Een geheel getal $p \geq 2$ heet priem als zijn enige positieve delers $1$ en $p$ zijn.

Propositie 29.14

Elk geheel getal $n \geq 2$ heeft een priemdeler; is $n$ niet priem, dan heeft het een priemdeler $\leq \sqrt n$ . Deelt een priemgetal $p$ een product $ab$ , dan is $p \mid a$ of $p \mid b$ (lemma van Euclides).

Bewijs. De kleinste deler $d \geq 2$ van $n$ is priem (elke echte deler van $d$ zou een kleinere deler van $n$ zijn). Is $n = de$ samengesteld met $2 \leq d \leq e$ , dan is $d^2 \leq de = n$ , dus $d \leq \sqrt n$ . Voor het lemma van Euclides: geldt $p \nmid a$ , dan is $\gcd(p, a) = 1$ (de enige delers van $p$ zijn $1$ en $p$ ), en het lemma van Gauss geeft $p \mid b$ . ∎

Stelling 29.15 (Euclides)

Er zijn oneindig veel priemgetallen.

Bewijs. Neem een willekeurige eindige lijst $p_1, \dots, p_k$ van priemgetallen en beschouw $N = p_1 p_2 \cdots p_k + 1$ . Een zeker priemgetal $p$ deelt $N$ ; maar geen enkele $p_i$ deelt $N$ (de rest is $1$ ), dus $p$ is een priemgetal dat niet in de lijst staat. Geen enkele eindige lijst put de priemgetallen uit. ∎

Stelling 29.16 (Hoofdstelling van de rekenkunde)

Elk geheel getal $n \geq 2$ is een product van priemgetallen, en die ontbinding is uniek op de volgorde van de factoren na:

n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r}, \qquad p_1 < p_2 < \dots < p_r \text{ priem},\ \alpha_i \geq 1 .

Bewijs. Bestaan, met sterke inductie: is $n$ priem, dan is het zijn eigen ontbinding; anders is $n = de$ met $2 \leq d, e < n$ , en beide ontbinden volgens de inductiehypothese. Uniciteit: onderstel $p_1\cdots p_s = q_1 \cdots q_t$ (priemgetallen, herhalingen toegestaan). Volgens het lemma van Euclides deelt $p_1$ een zekere $q_j$ , en omdat $p_1$ priem is, is $p_1 = q_j$ ; schrap en herhaal. De twee ontbindingen stemmen term voor term overeen. ∎

Stelling 29.17 (Kleine stelling van Fermat)

Zij $p$ priem en $a \in \Z$ met $p \nmid a$ . Dan is

a^{p-1} \equiv 1 \pmod p .

Voor elke $a \in \Z$ (zonder enige voorwaarde) geldt $a^p \equiv a \pmod p$ .

Bewijs. Beschouw de $p - 1$ gehele getallen $a, 2a, 3a, \dots, (p-1)a$ modulo $p$ . Geen ervan is $\equiv 0$ (geldt $p \mid ka$ met $1 \leq k \leq p-1$ , dan dwingt het lemma van Euclides $p \mid k$ af, wat onmogelijk is), en ze zijn paarsgewijs verschillend modulo $p$ (geldt $ka \equiv la$ , dan is $p \mid (k - l)a$ , dus $p \mid k - l$ , dus $k = l$ ). Modulo $p$ zijn het dus de getallen $1, 2, \dots, p-1$ in een zekere volgorde. Vermenigvuldig alle congruenties:

a^{p-1}\,(p-1)! \equiv (p-1)! \pmod p .

Omdat $p$ geen enkele van $1, \dots, p-1$ deelt, mag je met herhaald gebruik van het lemma van Euclides $(p-1)!$ wegdelen, en blijft $a^{p-1} \equiv 1$ over. De tweede vorm volgt door met $a$ te vermenigvuldigen (en is triviaal zodra $p \mid a$ ). ∎

Voorbeeld 29.18 (Toepassing in de cryptografie)

De stelling van Fermat maakt het machtsverheffen modulo $n$ omkeerbaar zodra de exponenten geschikt gekozen zijn — het hart van het RSA-cryptosysteem. Met grote priemgetallen $p$ en $q$ en $n = pq$ publiceer je $n$ en een exponent $e$ ; versleutelen is $x \mapsto x^e \bmod n$ . Ontsleutelen vraagt een exponent $d$ met $ed \equiv 1 \pmod{(p-1)(q-1)}$ , en die kan alleen berekend worden door wie $p$ en $q$ kent — en $p$ en $q$ uit $n$ terugvinden betekent een getal van honderden cijfers ontbinden, wat geen enkel bekend algoritme in redelijke tijd doet.

29.5 Oefeningen

Oefening 29.1 ★

Bereken het quotiënt en de rest van de euclidische deling van $2026$ door $17$ , en van $-2026$ door $17$ .

Oplossing

Oplossing van Oefening 29.1.

$17 \times 119 = 2023$ , dus $2026 = 17 \times 119 + 3$ : quotiënt $119$ , rest $3$ . Voor $-2026$ : $-2026 = 17\times(-120) + 14$ (inderdaad is $17 \times 120 = 2040$ en $2040 - 2026 = 14$ ): quotiënt $-120$ , rest $14$ (de rest moet in $\intco{0}{17}$ liggen, dus ze is niet $-3$ ).

Oefening 29.2 ★

Wat is de rest van $7^{100}$ modulo $10$ ? (Wat is het laatste cijfer van $7^{100}$ ?)

Oplossing

Oplossing van Oefening 29.2.

Modulo $10$ : $7^2 = 49 \equiv 9 \equiv -1$ . Dus $7^{100} = \left(7^2\right)^{50} \equiv (-1)^{50} = 1 \pmod{10}$ : het laatste cijfer van $7^{100}$ is $1$ .

Oefening 29.3 ★

Bereken met het algoritme van Euclides $\gcd(1071, 462)$ , en zoek gehele getallen $u$ en $v$ met $1071u + 462v = \gcd(1071, 462)$ .

Oplossing

Oplossing van Oefening 29.3.

Euclides: $1071 = 2\times462 + 147$ ; $462 = 3\times147 + 21$ ; $147 = 7\times21 + 0$ . Dus $\gcd = 21$ .

Achterwaartse substitutie: $21 = 462 - 3\times147 = 462 - 3(1071 - 2\times462) = 7\times462 - 3\times1071$ . Dus $u = -3$ en $v = 7$ : $1071\times(-3) + 462\times7 = 21$ .

Oefening 29.4 ★

Toon aan dat $n^2$ voor elke $n \in \Z$ congruent is met $0$ of $1$ modulo $4$ . Leid af dat een geheel getal $\equiv 3 \pmod 4$ nooit een som van twee kwadraten is.

Oplossing

Oplossing van Oefening 29.4.

Elk geheel getal is $\equiv 0, 1, 2$ of $3 \pmod 4$ , en na kwadrateren: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . Dus is $n^2 \equiv 0$ of $1 \pmod 4$ . Een som van twee kwadraten is dan congruent met $0 + 0$ , $0 + 1$ of $1 + 1$ , dat wil zeggen met $0$ , $1$ of $2 \pmod 4$ — nooit met $3$ .

Oefening 29.5 ★★

Toon aan dat $n(n+1)(2n+1)$ voor alle $n \in \N$ deelbaar is door $6$ .

Oplossing

Oplossing van Oefening 29.5.

Deelbaarheid door $2$ : van $n$ en $n + 1$ is er één even. Deelbaarheid door $3$ : is $n \equiv 0$ , dan geldt $3 \mid n$ ; is $n \equiv 1 \pmod 3$ , dan is $2n + 1 \equiv 3 \equiv 0$ ; is $n \equiv 2$ , dan is $n + 1 \equiv 0$ . In alle gevallen deelt $3$ het product. Omdat $\gcd(2,3) = 1$ , geeft Gevolg 29.12 dat $6 \mid n(n+1)(2n+1)$ . (Daarmee is opnieuw bewezen dat $\frac{n(n+1)(2n+1)}{6}$ , de som van de kwadraten uit Oefening 20.1, een geheel getal is.)

Oefening 29.6 ★★

Los in $\Z$ de congruentie $5x \equiv 3 \pmod{11}$ op. (Tip: zoek de inverse van $5$ modulo $11$ .)

Oplossing

Oplossing van Oefening 29.6.

We zoeken de inverse van $5$ modulo $11$ : proberen (of Bézout) geeft $5 \times 9 = 45 = 44 + 1 \equiv 1 \pmod{11}$ . Vermenigvuldig de congruentie met $9$ :

x \equiv 9 \times 3 = 27 \equiv 5 \pmod{11}.

De oplossingen zijn de gehele getallen $x = 5 + 11k$ , $k \in \Z$ . (Controle: $5\times5 = 25 \equiv 3 \pmod{11}$ .)

Oefening 29.7 ★★

Los in $\Z \times \Z$ de diofantische vergelijking

17x - 40y = 1

op, en beschrijf daarna alle oplossingen van $17x - 40y = 6$ .

Oplossing

Oplossing van Oefening 29.7.

$\gcd(17, 40) = 1$ , dus er zijn oplossingen. Euclides: $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ . Achterwaarts substitueren: $1 = 6 - 5 = 6 - (17 - 2\times6) = 3\times6 - 17 = 3(40 - 2\times17) - 17 = 3\times40 - 7\times17$ . Dus $17\times(-7) - 40\times(-3) = 1$ : de bijzondere oplossing $(x_0, y_0) = (-7, -3)$ .

Algemene oplossing van $17x - 40y = 1$ : trek de bijzondere betrekking af, dan is $17(x + 7) = 40(y + 3)$ ; omdat $\gcd(17, 40) = 1$ , geeft Gauss $40 \mid x + 7$ , dus $x = -7 + 40k$ en vervolgens $y = -3 + 17k$ , $k \in \Z$ (en die voldoen allemaal).

Voor $17x - 40y = 6$ vermenigvuldig je de bijzondere oplossing met $6$ : $(x_1, y_1) = (-42, -18)$ , en dezelfde redenering geeft

x = -42 + 40k, \qquad y = -18 + 17k, \qquad k \in \Z .

(Bijvoorbeeld $k = 2$ : $x = 38$ , $y = 16$ ; inderdaad is $17\times38 - 40\times16 = 646 - 640 = 6$ .)

Oefening 29.8 ★★

Toon aan dat $\sqrt2$ irrationaal is met behulp van de uniciteit van de priemontbinding (vergelijk de exponent van $2$ in beide leden van $a^2 = 2b^2$ ).

Oplossing

Oplossing van Oefening 29.8.

Onderstel $\sqrt2 = \frac ab$ met $a, b \in \N^*$ ; dan is $a^2 = 2b^2$ . In de priemontbinding van een kwadraat is elke exponent even; de exponent van $2$ in $a^2$ is dus even, terwijl hij in $2b^2$ oneven is (één meer dan een even getal). Twee ontbindingen van hetzelfde gehele getal met verschillende exponenten van $2$ zijn in tegenspraak met de uniciteit uit Stelling 29.16. Zo’n breuk bestaat dus niet: $\sqrt2 \notin \Q$ .

Oefening 29.9 ★★★

Zij $p$ een priemgetal.

Toon aan dat $p$ voor $1 \leq k \leq p - 1$ het getal $\dbinom{p}{k}$ deelt. (Tip: gebruik $k\binom pk = p\binom{p-1}{k-1}$ , Oefening 27.7, en het lemma van Gauss.)
Leid daaruit met inductie op $a \geq 0$ een tweede bewijs af van de kleine stelling van Fermat in de vorm $a^p \equiv a \pmod p$ .

Oplossing

Oplossing van Oefening 29.9.

1. Uit $k\binom pk = p \binom{p-1}{k-1}$ volgt dat $p$ het getal $k\binom pk$ deelt. Voor $1 \leq k \leq p-1$ geven $p \nmid k$ en $p$ priem dat $\gcd(p, k) = 1$ , dus levert het lemma van Gauss $p \mid \binom pk$ .

2. Inductie op $a$ . Voor $a = 0$ : $0^p \equiv 0$ . Onderstel $a^p \equiv a \pmod p$ . Volgens het binomium van Newton is

(a+1)^p = \sum_{k=0}^{p} \binom pk a^k \equiv a^p + 1 \pmod p,

want alle tussenliggende termen verdwijnen modulo $p$ volgens punt 1. Volgens de inductiehypothese is dus $(a+1)^p \equiv a + 1 \pmod p$ . Daarmee is $a^p \equiv a$ bewezen voor alle $a \in \N$ , en het geval $a < 0$ volgt door $a \equiv a + kp$ met een geschikte positieve vertegenwoordiger te schrijven.

Oefening 29.10 ★★★

(Chinees restprobleem.) Zoek alle gehele getallen $n$ waarvoor

n \equiv 2 \pmod 3, \qquad n \equiv 3 \pmod 5, \qquad n \equiv 2 \pmod 7 .

(Tip: los eerst de twee eerste voorwaarden op en voeg daarna de derde toe; coëfficiënten van Bézout helpen.)

Oplossing

Oplossing van Oefening 29.10.

$n \equiv 2 \pmod 3$ en $n \equiv 3 \pmod 5$ : schrijf $n = 2 + 3s$ ; dan is $2 + 3s \equiv 3 \pmod 5$ , dat wil zeggen $3s \equiv 1 \pmod 5$ . De inverse van $3$ modulo $5$ is $2$ ( $3\times2 = 6 \equiv 1$ ), dus $s \equiv 2 \pmod 5$ , zeg $s = 2 + 5t$ , en $n = 8 + 15t$ : de twee eerste voorwaarden betekenen $n \equiv 8 \pmod{15}$ .

Voeg $n \equiv 2 \pmod 7$ toe: $8 + 15t \equiv 2 \pmod 7$ , en $15 \equiv 1 \pmod 7$ , dus $t \equiv -6 \equiv 1 \pmod 7$ , zeg $t = 1 + 7u$ . Dus $n = 23 + 105u$ :

n \equiv 23 \pmod{105}.

(Controle: $23 = 3\times7 + 2 = 5\times4 + 3 = 7\times3 + 2$ .)

29.6 Opgave: geheime codes en controlecijfers

Probleem 29.1

Weekendopgave — congruenties bewaken elke streepjescode en elke bankkaart, en de kleine stelling van Fermat bedient het slot op de geheimen van de wereld

G. H. Hardy schepte er in 1940 over op dat de getaltheorie “onbezoedeld” door toepassingen was. Tachtig jaar later spreekt elke piep aan de kassa, elke kaartbetaling en elk versleuteld bericht hem tegen — en dat met precies het gereedschap van dit hoofdstuk: congruenties (Propositie 29.5), inversen van Bézout (Stelling 29.10) en de kleine stelling van Fermat (Oefening 29.9). Deze opgave controleert de codes, breekt een speelgoedversie van het slot open, en leert waarom het echte slot standhoudt.

Deel I — Vlot met congruenties.

Bereken $2026 \bmod 7$ ; en daarna het laatste cijfer van $7^{100}$ (zoek de cyclus van de machten van $7$ modulo $10$ ).
Snel machtsverheffen (Methode 29.6): bereken $5^{117} \bmod 13$ (vertrek van $5^2 \equiv -1$ ).
Los $3x \equiv 5 \pmod 7$ op.
Pas het algoritme van Euclides toe op $(97, 35)$ , substitueer achterwaarts om gehele getallen $u$ en $v$ met $97u + 35v = 1$ te vinden, en leid de inverse van $35$ modulo $97$ af.
Formuleer precies wanneer $a$ inverteerbaar is modulo $n$ , en welke stelling de inverse levert.

Deel II — Controlecijfers.

ISBN-10: de tien cijfers $d_1 \dots d_{10}$ van een boekcode moeten voldoen aan $10d_1 + 9d_2 + \dots + 2d_9 + 1d_{10} \equiv 0 \pmod{11}$ . Ga het echte ISBN $0\,306\,40615\,2$ na.
Bewijs dat het ISBN-schema elke fout in één cijfer opspoort: verandert één cijfer met $d \not\equiv 0$ , dan verandert de gewogen som met $w d$ met $1 \leq w \leq 10$ — waarom kan dat nooit $\equiv 0 \pmod{11}$ zijn (Stelling 29.11)?
Bewijs dat het ook elke verwisseling van twee naburige (verschillende) cijfers opspoort. Leg daarna het geheim van het ontwerp uit: welke eigenschap van $11$ deed beide bewijzen werken, en wat kan er misgaan met modulus $10$ ?
Streepjescodes EAN-13 wegen de cijfers met $1, 3, 1, 3, \dots$ modulo $10$ . Bereken het controlecijfer dat $978\,2940199\,05$ vervolledigt. Welke verwisselingen van naburige cijfers spoort EAN niet op? (Wanneer is $2(a - b) \equiv 0 \pmod{10}$ ?)
Bankkaarten gebruiken het schema van Luhn: verdubbel van rechts af elk tweede cijfer (en trek $9$ af zodra het dubbele boven $9$ uitkomt), tel alles op, en eis een veelvoud van $10$ . Ga het testnummer $4539\,1488\,0343\,6467$ na.
In één zin: wat leverde de priemmodulus het ISBN op dat EAN en Luhn, geketend aan $10$ , niet kunnen hebben?

Deel III — Het slot van Fermat.

Een valstrik vóór de schat: bereken $2^{10} \bmod 341$ , leid $2^{340} \bmod 341$ af — en ontbind daarna $341$ . Wat zegt dit voorbeeld (een pseudopriemgetal van Fermat) over het gebruik van de kleine stelling van Fermat als priemtest?
RSA in het klein: neem $p = 3$ en $q = 11$ , dus $n = 33$ en $(p-1)(q-1) = 20$ ; de publieke exponent is $e = 3$ . Zoek de private exponent $d$ met $3d \equiv 1 \pmod{20}$ (de methode van vraag 4).
Versleutel het bericht $m = 4$ : bereken $c = m^3 \bmod 33$ .
Ontsleutel: bereken $c^d \bmod 33$ (gebruik $c \equiv -2 \pmod{33}$ ) en haal het bericht terug.
Waarom het ontsleutelen altijd werkt: toon aan dat $m^{21} \equiv m$ zowel modulo $3$ als modulo $11$ (de kleine stelling van Fermat in elk van beide werelden), en besluit modulo $33$ (Stelling 29.11 lijmt de twee congruenties aan elkaar). Waar kwam de bijzondere vorm $1 + 20k$ van $21 = ed$ binnen?
De veiligheid van het slot: iedereen kent $n$ en $e$ ; om $d$ terug te vinden heb je $(p-1)(q-1)$ nodig, en dus de factoren van $n$ . Onze $33$ ontbindt in één oogopslag — waarom beschermt hetzelfde schema, met een $n$ van zeshonderd cijfers, de banken van de wereld? (Eén zin over de asymmetrie tussen vermenigvuldigen en ontbinden.)

Deel IV — Klassiekers.

De oude Chinese soldatentelling (vergelijk met Oefening 29.10): een aantal soldaten laat rest $2$ bij opstelling per $3$ en rest $3$ bij opstelling per $5$ . Zoek alle mogelijke aantallen, en leg uit waarom het antwoord uniek is modulo $15$ .
Eindelijk bewijzen van één regel: leid uit $10 \equiv 1 \pmod 9$ af dat elk getal congruent is met zijn cijfersom modulo $9$ ; leid uit $10 \equiv -1 \pmod{11}$ de regel van de alternerende som voor $11$ af. (Het onderbouwvolume bewees die met expliciete algebra — bewonder de beknoptheid.)
Slotstuk — Hardy tegen de streepjescode: vat het gereedschap van het hoofdstuk samen (rekenen met congruenties, inversen van Bézout, de kleine stelling van Fermat, het lijmen van relatief prieme moduli) en zeg waar elk stuk in deze opgave op zijn plaats klikte; geef daarna het moderne oordeel over “onbezoedeld”.

Oplossing

Oplossing van Probleem 29.1.

1. $2026 = 289 \times 7 + 3$ : $2026 \equiv 3 \pmod 7$ . Machten van $7$ mod $10$ : $7, 9, 3, 1$ , een cyclus van lengte $4$ ; en $100 \equiv 0 \pmod 4$ : het laatste cijfer van $7^{100}$ is $1$ .

2. $5^2 = 25 \equiv -1 \pmod{13}$ , dus $5^{116} = \left(5^2\right)^{58} \equiv (-1)^{58} = 1$ en $5^{117} \equiv 5 \pmod{13}$ .

3. De inverse van $3$ modulo $7$ is $5$ ( $15 \equiv 1$ ): $x \equiv 5 \times 5 = 25 \equiv 4 \pmod 7$ .

4. $97 = 2 \times 35 + 27$ ; $35 = 27 + 8$ ; $27 = 3 \times 8 + 3$ ; $8 = 2 \times 3 + 2$ ; $3 = 2 + 1$ . Achterwaarts substitueren: $1 = 97 \times 13 + 35 \times (-36)$ . Dus $35 \times (-36) \equiv 1 \pmod{97}$ : de inverse van $35$ is $-36 \equiv 61 \pmod{97}$ .

5. $a$ is inverteerbaar modulo $n$ precies wanneer $\gcd(a, n) = 1$ : Bézout levert $au + nv = 1$ , dat wil zeggen $au \equiv 1$ ; omgekeerd dwingt een inverse de ggd om $1$ te delen.

6. $0{\cdot}10 + 3{\cdot}9 + 0{\cdot}8 + 6{\cdot}7 + 4{\cdot}6 + 0{\cdot}5 + 6{\cdot}4 + 1{\cdot}3 + 5{\cdot}2 + 2{\cdot}1 = 132 = 12 \times 11 \equiv 0 \pmod{11}$ : geldig.

7. De som verandert met $wd$ met $1 \leq w \leq 10$ en $1 \leq \abs d \leq 9$ : omdat $11$ priem is en geen van beide factoren deelt, kan het het product niet delen (Stelling 29.11 / Propositie 29.14). De gewijzigde som is dus nooit opnieuw $\equiv 0$ : elke fout in één cijfer laat het alarm afgaan.

8. Het verwisselen van naburige cijfers $a$ en $b$ (gewichten $w + 1$ en $w$ ) verandert de som met $(w+1)b + wa - (w+1)a - wb = b - a \not\equiv 0$ zodra $a \neq b$ : opgespoord. Het geheim is dat $11$ priem is: modulo $10$ verdwijnen producten zoals $5 \times 2$ zonder dat een van beide factoren nul is, zodat een fout van $\pm 2$ op een gewicht $5$ (of een ongelukkige verwisseling) erdoor kan glippen.

9. De gewogen som van de twaalf cijfers is $119$ ; het controlecijfer moet ze aanvullen tot een veelvoud van $10$ : dat is $1$ (volledige code $978\,2940199\,051$ ). EAN mist de verwisselingen van naburige cijfers met $2(a - b) \equiv 0 \pmod{10}$ , dat wil zeggen $\abs{a - b} = 5$ : een $2$ en een $7$ verwisselen glipt er ongezien door — de prijs van de vriendelijke modulus $10$ .

10. Verdubbel je van rechts af elk tweede cijfer en vouw je terug ( $16 \to 7$ , enzovoort), dan komt de som op $80 \equiv 0 \pmod{10}$ : de testkaart is geldig.

11. Met een priemmodulus is elk gewicht inverteerbaar, zodat alle fouten in één cijfer en alle verwisselingen van naburige cijfers gevat worden — de luxe van het ISBN; schema’s modulo $10$ houden mensvriendelijke cijfers en nemen een kleine blinde vlek erbij.

12. $2^{10} = 1024 = 3 \times 341 + 1 \equiv 1 \pmod{341}$ , dus $2^{340} = \left(2^{10}\right)^{34} \equiv 1$ . En toch is $341 = 11 \times 31$ samengesteld: het doorstaat de test van Fermat met grondtal $2$ zonder priem te zijn. Moraal: de congruentie van Fermat is noodzakelijk, niet voldoende — priemtesten vragen scherper gereedschap (en krijgt dat, in de universitaire volumes).

13. $3d \equiv 1 \pmod{20}$ : $d = 7$ ( $21 = 20 + 1$ ).

14. $c = 4^3 = 64 \equiv 31 \pmod{33}$ .

15. $31 \equiv -2$ : $(-2)^7 = -128$ , en $-128 + 4 \times 33 = 4$ : de versleutelde tekst ontsleutelt tot $m = 4$ . Het slot draait.

16. Modulo $3$ : geldt $3 \nmid m$ , dan is $m^2 \equiv 1$ (Fermat), dus $m^{21} = m \cdot \left(m^2\right)^{10} \equiv m$ ; geldt $3 \mid m$ , dan zijn beide leden $\equiv 0$ . Modulo $11$ : $m^{10} \equiv 1$ of $11 \mid m$ , en $m^{21} = m \cdot \left(m^{10}\right)^2 \equiv m$ . Zowel $3$ als $11$ deelt dus $m^{21} - m$ , en omdat ze relatief priem zijn, deelt hun product $33$ het ook (Gauss): $m^{21} \equiv m \pmod{33}$ . De exponent $ed = 21 = 1 + 20k$ was zo gebouwd dat beide exponenten van Fermat ( $2$ en $10$ , delers van $20$ ) verdwijnen.

17. Twee priemgetallen van $300$ cijfers vermenigvuldigen kost een microseconde; ze uit hun product terugvinden verslaat elk bekend algoritme en alle computers van de wereld — het slot is een eenrichtingsstraat. (Onze $n = 33$ is diezelfde straat op speelgoedschaal, in beide richtingen te belopen.)

18. Door de resten te toetsen (of met Bézout op te bouwen): $n \equiv 8 \pmod{15}$ , dus de aantallen $8, 23, 38, 53, \dots$ Uniciteit modulo $15$ : twee oplossingen verschillen een veelvoud van $3$ en van $5$ , dus van $15$ ( $3$ en $5$ zijn relatief priem, Gauss). De generaal met $1000$ soldaten kondigt met drie snelle opstellingen “ $8$ ” aan — de aloude truc om koppen te tellen.

19. $10 \equiv 1 \pmod 9$ geeft $10^k \equiv 1$ , dus $\sum d_k 10^k \equiv \sum d_k$ : een getal en zijn cijfersom zijn congruent modulo $9$ (en modulo $3$ ). En $10 \equiv -1 \pmod{11}$ geeft $\sum d_k 10^k \equiv \sum (-1)^k d_k$ : de alternerende regel. Twee regels uit de kindertijd, elk in één lijn.

20. Congruenties maakten van resten een rekenkunde (Deel I); Bézout sloeg de inversen die lineaire congruenties en de $d$ van RSA oplossen (vragen 4 en 13); de kleine stelling van Fermat opende en sloot het slot (vragen 15 en 16); het lijmen van relatief prieme moduli telde de soldaten en maakte het bewijs af (vragen 16 en 18). Het oordeel over Hardy: de zuiverste stelling die hij kende bewaakt nu elke aankoop — zuiverheid is, mits tijd, het meest toepasbare wat er is.