Wiskunde bovenbouw · Grades 10–12

29Rekenkunde

Rekenkunde bestudeert de gehele getallen: deelbaarheid, priemgetallen, resten. Lang beschouwd als de puurste der pure wiskunde, beschermt zij nu elke online betaling: het RSA-cryptosysteem rust op de stellingen van Bézout, Gauss en Fermat bewezen in dit hoofdstuk.

29.1 Deelbaarheid en euclidische deling

Definitie 29.1 (Deelbaarheid)

Laat $a, b \in \Z$ . We zeggen dat $b$ deelt $a$ , geschreven $b \mid a$ , als er een $k \in \Z$ bestaat met $a = kb$ . We zeggen ook dat $a$ een veelvoud van $b$ is.

Propositie 29.2

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

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

Stelling 29.3 (Euclidische deling)

Laat $a \in \Z$ en $b \in \N^*$ . Er bestaat een uniek paar $(q, r) \in \Z \times \N$ zodat

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

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

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

29.2 Congruenties

Definitie 29.4 (Congruentie)

Laat $n \in \N^*$ . Twee gehele getallen $a, b$ zijn congruent modulo $n$ , geschreven $a \equiv b \pmod n$ , als $n \mid (a - b)$ — equivalent, als $a$ en $b$ dezelfde rest hebben bij euclidische deling door $n$ .

Propositie 29.5 (Verenigbaarheid met bewerkingen)

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

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 $ac - bd = a(c - d) + d(a - b)$ is eveneens een veelvoud van $n$ . De machtenregel volgt door inductie uit de productregel. ∎

Methode 29.6 (Machten modulo $n$ berekenen)

Om $a^k \bmod n$ te berekenen, reduceer de basis modulo $n$ , zoek daarna een kleine macht van $a$ congruent met $\pm1$ , en gebruik die om de exponent in te klappen. 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)

Laat $a, b$ gehele getallen zijn, niet beide nul. De grootste gemene deler $\gcd(a, b)$ is het grootste gehele getal dat zowel $a$ als $b$ deelt. Wanneer $\gcd(a,b) = 1$ , heten $a$ en $b$ relatief priem.

Propositie 29.8 (Algoritme van Euclides)

Als $a = bq + r$ ( $b \neq 0$ ), dan $\gcd(a, b) = \gcd(b, r)$ . Itereren van de euclidische deling berekent dus $\gcd(a,b)$ : de ggd is de laatste niet-nul rest.

Bewijs. Elke gemeenschappelijke deler van $a$ en $b$ deelt $r = a - bq$ (Propositie 29.2), dus is een gemeenschappelijke deler van $b$ en $r$ ; en omgekeerd, omdat $a = bq + r$ . De twee paren hebben dezelfde gemeenschappelijke delers, dus dezelfde ggd. Het algoritme eindigt 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)

Laat $a, b$ gehele getallen zijn, niet beide nul, en $d = \gcd(a,b)$ . Er bestaan $u, v \in \Z$ zodat

au + bv = d .

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

Bewijs. Voer het algoritme van Euclides achterwaarts uit: elke rest is een gehele combinatie van de vorige twee, en de beginwaarden $a, b$ zijn combinaties van zichzelf; door dalende substitutie is de laatste niet-nul rest $d$ 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 equivalentie: als $\gcd(a,b) = 1$ , levert Bézout $u, v$ ; omgekeerd deelt elke gemeenschappelijke deler van $a$ en $b$ $au + bv = 1$ , wat $\gcd(a,b) = 1$ dwingt. ∎

Stelling 29.11 (Lemma van Gauss)

Laat $a, b, c \in \Z$ . Als $a \mid bc$ en $\gcd(a, b) = 1$ , dan $a \mid c$ .

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

Gevolg 29.12

Als $a \mid c$ , $b \mid c$ en $\gcd(a,b) = 1$ , dan $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 $c = abl$ . ∎

29.4 Priemgetallen

Definitie 29.13 (Priem)

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

Propositie 29.14

Elk geheel getal $n \geq 2$ heeft een priemdeler; als $n$ niet priem is, heeft het een priemdeler $\leq \sqrt n$ . Als een priemgetal $p$ een product $ab$ deelt, dan $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). Als $n = de$ samengesteld is met $2 \leq d \leq e$ , dan $d^2 \leq de = n$ , dus $d \leq \sqrt n$ . Voor het lemma van Euclides: als $p \nmid a$ , dan $\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. Gegeven een willekeurige eindige lijst $p_1, \dots, p_k$ van priemgetallen, beschouw $N = p_1 p_2 \cdots p_k + 1$ . Enig priemgetal $p$ deelt $N$ ; maar geen $p_i$ deelt $N$ (de rest is $1$ ), dus $p$ is een priemgetal niet in de lijst. Geen 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 deze factorisatie 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, door sterke inductie: $n$ priem is zijn eigen factorisatie; anders $n = de$ met $2 \leq d, e < n$ , en beide factoren volgens de inductiehypothese. Uniciteit: stel $p_1\cdots p_s = q_1 \cdots q_t$ (priemgetallen, herhalingen toegestaan). Volgens het lemma van Euclides deelt $p_1$ enig $q_j$ , en als priem is $p_1 = q_j$ ; schrap en herhaal. De twee factorisaties komen term voor term overeen. ∎

Stelling 29.17 (Kleine stelling van Fermat)

Laat $p$ priem zijn en $a \in \Z$ met $p \nmid a$ . Dan

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

Voor elk $a \in \Z$ (zonder relatieve-priemheid), $a^p \equiv a \pmod p$ .

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

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

Omdat $p$ geen van $1, \dots, p-1$ deelt, staat herhaald gebruik van het lemma van Euclides toe $(p-1)!$ te schrappen, wat $a^{p-1} \equiv 1$ achterlaat. De tweede vorm volgt door met $a$ te vermenigvuldigen (en is triviaal wanneer $p \mid a$ ). ∎

Voorbeeld 29.18 (Toepassing op cryptografie)

De stelling van Fermat maakt machtsverheffen modulo $n$ omkeerbaar wanneer de exponenten geschikt gekozen zijn — het hart van het RSA-cryptosysteem. Met $p, q$ grote priemgetallen en $n = pq$ publiceert men $n$ en een exponent $e$ ; encryptie is $x \mapsto x^e \bmod n$ . Ontcijferen vereist een exponent $d$ met $ed \equiv 1 \pmod{(p-1)(q-1)}$ , die alleen iemand die $p$ en $q$ kent kan berekenen — en $p, q$ uit $n$ herstellen betekent een getal van honderden cijfers factoriseren, wat geen 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 $17 \times 120 = 2040$ en $2040 - 2026 = 14$ ): quotiënt $-120$ , rest $14$ (de rest moet in $\intco{0}{17}$ liggen, dus is zij 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 ★

Met het algoritme van Euclides, bereken $\gcd(1071, 462)$ , en vind gehele $u, 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$ .

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

Oefening 29.4 ★

Toon dat voor elk $n \in \Z$ , $n^2$ 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 kwadrateren: $0^2 \equiv 0$ , $1^2 \equiv 1$ , $2^2 = 4 \equiv 0$ , $3^2 = 9 \equiv 1$ . Dus $n^2 \equiv 0$ of $1 \pmod 4$ . Een som van twee kwadraten is dan congruent met $0 + 0$ , $0 + 1$ of $1 + 1$ , d.w.z. met $0$ , $1$ of $2 \pmod 4$ — nooit met $3$ .

Oefening 29.5 ★★

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

Oplossing

Oplossing van Oefening 29.5.

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

Oefening 29.6 ★★

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

Oplossing

Oplossing van Oefening 29.6.

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

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 Diophantische vergelijking

17x - 40y = 1,

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

Oplossing

Oplossing van Oefening 29.7.

$\gcd(17, 40) = 1$ , dus oplossingen bestaan. Euclides: $40 = 2\times17 + 6$ ; $17 = 2\times6 + 5$ ; $6 = 5 + 1$ . Terugsubstitueren: $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$ : de bijzondere relatie aftrekken, $17(x + 7) = 40(y + 3)$ ; omdat $\gcd(17, 40) = 1$ , geeft Gauss $40 \mid x + 7$ , dus $x = -7 + 40k$ en dan $y = -3 + 17k$ , $k \in \Z$ (alle controleren).

Voor $17x - 40y = 6$ , vermenigvuldig 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 .

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

Oefening 29.8 ★★

Toon dat $\sqrt2$ irrationaal is, met de uniciteit van de priemfactorisatie (vergelijk de exponent van $2$ aan beide zijden van $a^2 = 2b^2$ ).

Oplossing

Oplossing van Oefening 29.8.

Stel $\sqrt2 = \frac ab$ met $a, b \in \N^*$ ; dan $a^2 = 2b^2$ . In de priemfactorisatie van een kwadraat is elke exponent even; dus de exponent van $2$ in $a^2$ is even, terwijl in $2b^2$ hij oneven is (één meer dan een even getal). Twee factorisaties van hetzelfde gehele getal met verschillende exponenten van $2$ weerspreken de uniciteit in Stelling 29.16. Dus bestaat er geen zo’n breuk: $\sqrt2 \notin \Q$ .

Oefening 29.9 ★★★

Laat $p$ een priemgetal zijn.

Toon dat voor $1 \leq k \leq p - 1$ , $p$ deelt $\dbinom{p}{k}$ . (Hint: gebruik $k\binom pk = p\binom{p-1}{k-1}$ , Oefening 27.7, en het lemma van Gauss.)
Leid af, door inductie op $a \geq 0$ , een ander bewijs 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}$ deelt $p$ $k\binom pk$ . Voor $1 \leq k \leq p-1$ , $p \nmid k$ en $p$ priem geven $\gcd(p, k) = 1$ , dus het lemma van Gauss levert $p \mid \binom pk$ .

2. Inductie op $a$ . Voor $a = 0$ : $0^p \equiv 0$ . Neem $a^p \equiv a \pmod p$ aan. Met de binomiaalstelling,

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

alle middentermen verdwijnen modulo $p$ door punt 1. Door de inductiehypothese, $(a+1)^p \equiv a + 1 \pmod p$ . Dit bewijst $a^p \equiv a$ voor alle $a \in \N$ , en het geval $a < 0$ volgt door $a \equiv a + kp$ te schrijven voor een geschikte positieve representant.

Oefening 29.10 ★★★

(Chinees-restenprobleem.) Vind alle gehele $n$ zodat

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

(Hint: los de eerste twee voorwaarden op, neem daarna de derde mee; Bézout-coëfficiënten helpen.)

Oplossing

Oplossing van Oefening 29.10.

$n \equiv 2 \pmod 3$ en $n \equiv 3 \pmod 5$ : schrijf $n = 2 + 3s$ ; dan $2 + 3s \equiv 3 \pmod 5$ , d.w.z. $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 eerste twee voorwaarden betekenen $n \equiv 8 \pmod{15}$ .

$n \equiv 2 \pmod 7$ toevoegen: $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$ .)