---
title: "Getaltheorie in ℤ"
book: "Universitaire wiskunde — Bachelor jaar 1"
subject: math
language: nl
chapter: 6
exercises: 12
source: https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z
---

# Hoofdstuk 6 — Getaltheorie in ℤ

De getaltheorie — de studie van de [deelbaarheid](#def-b1-arith-divides) in $\Z$ — werd in het bovenbouwvolume aangevat. Dit hoofdstuk bouwt haar volledig opnieuw op vanaf de euclidische deling, met volledige bewijzen: [grootste gemene deler](#thm-b1-arith-gcd) en het [algoritme van Euclides](#met-b1-arith-euclid), de identiteit van Bézout en het lemma van Gauss, de [priemontbinding](#thm-b1-arith-fta), en het rekenen met [congruenties](#def-b1-arith-congruence) tot en met de kleine stelling van Fermat. Naast haar eigen bekoring is deze stof het model dat [Hoofdstuk 8](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly) voor veeltermen nabootst.

## 6.1 Deelbaarheid en euclidische deling

**Definitie 6.1 (Deelbaarheid).**

Voor $a, b \in \Z$ zeggen we dat $b$ het getal $a$ *deelt* (genoteerd $b \mid a$) wanneer $a = bq$ voor een zekere $q \in \Z$. Eenvoudige gevolgen: als $b \mid a$ en $b \mid a'$, dan $b \mid (ua + va')$ voor alle $u, v \in \Z$; als $b \mid a$ en $a
\neq 0$, dan $\abs b \leq \abs a$; en uit $a \mid b$ samen met $b \mid a$ volgt $b = \pm a$.

**Stelling 6.2 (Euclidische deling).**

Voor alle $a \in \Z$ en $b \in \N^*$ bestaat er precies één paar $(q, r)
\in \Z \times \N$ met

$$
a = bq + r, \qquad 0 \leq r < b .
$$

**Bewijs.** *Bestaan.* De [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $A = \{a - bk : k \in \Z\} \cap \N$ is een niet-lege deelverzameling van $\N$ (neem $k = -\abs a$: $a + b\abs a \geq
a + \abs a \geq 0$). Zij $r = a - bq$ haar kleinste element. Was $r \geq
b$, dan zou $r - b = a - b(q+1)$ een kleiner element van $A$ zijn: tegenspraak. Dus $0 \leq r < b$.

*Uniciteit.* Is $bq + r = bq' + r'$ met $0 \leq r, r' < b$, dan is $b(q - q') = r' - r$ met $\abs{r' - r} < b$: het veelvoud van $b$ in het linkerlid moet $0$ zijn, dus $q = q'$ en $r = r'$. ∎

**Voorbeeld 6.3 (Positiestelsels door herhaald delen).**

Schrijf $2026$ in grondtal $7$. Deel herhaaldelijk door $7$ en houd de resten bij:

$$
2026 = 7 \times 289 + 3, \quad
289 = 7 \times 41 + 2, \quad
41 = 7 \times 5 + 6, \quad
5 = 7 \times 0 + 5 .
$$

Lees je de resten van laatst naar eerst, dan is $2026 = (5\,6\,2\,3)_7$. Controle: $5 \times 343 + 6 \times 49 + 2 \times 7 + 3 = 1715 + 294 + 14
+ 3 = 2026$. De uniciteit van de euclidische deling is precies wat elk cijfer *afdwingt*: bij elke stap is de rest het enige gehele getal in $\intint06$ dat congruent is met de huidige waarde modulo $7$, zodat de schrijfwijze in grondtal $7$ uniek is — het feit dat stilzwijgend gebruikt wordt telkens als de weekendopgave met “de cijfers van $n$ in grondtal $p$” werkt.

## 6.2 Grootste gemene deler

**Stelling 6.4 (Deelgroepen van Z\ZZ; bestaan van de ggd).**

1. Elke deelgroep van $(\Z, +)$ is van de vorm $n\Z = \{nk : k \in  \Z\}$ voor een unieke $n \in \N$ .
2. Voor $a, b \in \Z$ die niet beide nul zijn, is de [verzameling](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-sets) $a\Z + b\Z = \{au + bv : u, v \in \Z\}$ een deelgroep van $\Z$ en dus gelijk aan $d\,\Z$ voor een unieke $d \in \N^*$ . Die $d$ is de *grootste gemene deler* $\gcd(a, b)$ : hij [deelt](#def-b1-arith-divides) $a$ en $b$ , en elke gemene deler van $a$ en $b$ [deelt](#def-b1-arith-divides) $d$ .

**Bewijs.** (1) Zij $H \subseteq \Z$ een deelgroep (niet-leeg, stabiel onder aftrekken; de formele definitie staat in [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures), en alleen die twee eigenschappen worden gebruikt). Is $H = \{0\}$, neem dan $n = 0$. Anders bevat $H$ een element ongelijk aan nul en zijn tegengestelde, en dus een kleinste strikt positief element $n$. Dan is $n\Z \subseteq H$. Voor $x \in H$ schrijf je $x = nq + r$ met $0 \leq r <
n$ ([Stelling 6.2](#thm-b1-arith-division)); dan is $r = x - nq \in H$, en de minimaliteit van $n$ dwingt $r = 0$ af: $x \in n\Z$. Uniciteit: $n$ is het kleinste positieve element van $n\Z$.

(2) $a\Z + b\Z$ bevat $0$ en is stabiel onder aftrekken, dus is het $d\Z$ met $d \geq 1$ (het bevat $a$ of $b$, en een van beide is niet nul). Omdat $a, b \in d\Z$, [deelt](#def-b1-arith-divides) $d$ ze beide. En [deelt](#def-b1-arith-divides) $c$ zowel $a$ als $b$, dan [deelt](#def-b1-arith-divides) $c$ elke $au + bv$ — in het bijzonder $c \mid d$, want $d \in a\Z
+ b\Z$. Dat is de aangekondigde eigenschap (en ze impliceert $\abs c \leq
d$, zodat $d$ de naam *grootste* gemene deler verdient). ∎

**Gevolg 6.5 (Identiteit van Bézout).**

Voor $a, b$ die niet beide nul zijn bestaan er $u, v \in \Z$ met

$$
au + bv = \gcd(a, b) .
$$

In het bijzonder ($\gcd(a,b) = 1$, het *relatief prieme* geval): $a$ en $b$ zijn [relatief priem](#cor-b1-arith-bezout) dan en slechts dan als $au + bv = 1$ een oplossing heeft.

**Bewijs.** Er is $\gcd(a,b) = d \in d\Z = a\Z + b\Z$. Voor de equivalentie: is $\gcd(a,b) = 1$, dan levert Bézout de oplossing; omgekeerd dwingt $au +
bv = 1$ af dat elke gemene deler van $a$ en $b$ het getal $1$ [deelt](#def-b1-arith-divides). ∎

**Methode 6.6 (Algoritme van Euclides, uitgebreid).**

Om $\gcd(a, b)$ te berekenen ($a > b > 0$): deel $a = bq + r$; dan is $\gcd(a, b) = \gcd(b, r)$ (de gemene delers van $(a,b)$ en van $(b,r)$ vallen samen, want $r = a - bq$); herhaal tot de rest $0$ is; de laatste rest ongelijk aan nul is de ggd. De delingen achterstevoren doorlopen (of de coëfficiënten onderweg bijhouden) levert een paar van Bézout $(u, v)$.

**Voorbeeld 6.7.**

$\gcd(120, 23)$: $120 = 5 \times 23 + 5$; $23 = 4 \times 5 + 3$; $5 =
1\times 3 + 2$; $3 = 1 \times 2 + 1$; $2 = 2 \times 1 + 0$. Dus $\gcd =
1$. Achterstevoren:

$$
\begin{align*}
1 &= 3 - 2 = 3 - (5 - 3) = 2\times 3 - 5 = 2(23 - 4\times 5) - 5 \\
&= 2 \times 23 - 9 \times 5 = 2\times 23 - 9(120 - 5\times 23)
= 47 \times 23 - 9 \times 120 .
\end{align*}
$$

Controle: $47 \times 23 = 1081$ en $9 \times 120 = 1080$.

**Stelling 6.8 (Lemma van Gauss en gevolgen).**

Zij $a, b, c \in \Z$.

1. (Lemma van Gauss) Is $a \mid bc$ en $\gcd(a, b) = 1$ , dan $a \mid c$ .
2. Is $a \mid c$ , $b \mid c$ en $\gcd(a,b) = 1$ , dan $ab \mid c$ .
3. Is $\gcd(a, b) = \gcd(a, c) = 1$ , dan $\gcd(a, bc) = 1$ .

**Bewijs.** (1) Bézout: $au + bv = 1$. Vermenigvuldig met $c$: $acu + bcv = c$. Beide termen zijn [deelbaar](#def-b1-arith-divides) door $a$ (de tweede omdat $a \mid bc$), dus $a \mid
c$.

(2) Schrijf $c = aq$; uit $b \mid aq$ en $\gcd(a, b) = 1$ geeft punt (1) dat $b \mid q$, dus $ab \mid aq = c$.

(3) Er is $au + bv = 1$ en $au' + cv' = 1$. Vermenigvuldig beide betrekkingen:

$$
1 = (au + bv)(au' + cv')
= a\,\bigl(auu' + ucv' + u'bv\bigr) + bc\,(vv') ,
$$

een betrekking van Bézout tussen $a$ en $bc$: volgens [Gevolg 6.5](#cor-b1-arith-bezout) is $\gcd(a, bc) = 1$. ∎

**Voorbeeld 6.9 (Een lineaire diofantische vergelijking oplossen).**

Bepaal alle $(x, y) \in \Z^2$ met $6x + 10y = 4$. Eerst de *bestaanstoets*: $\gcd(6, 10) = 2$ [deelt](#def-b1-arith-divides) $4$, dus zijn er oplossingen (deelde de ggd het rechterlid niet, dan zou het linkerlid altijd een veelvoud ervan zijn en zou er geen enkele zijn). Deel door: $3x + 5y = 2$. Een particuliere oplossing springt in het oog: $(x_0, y_0)
= (-1, 1)$. Voor de algemene trek je af: $3(x + 1) = -5(y - 1)$, dus $3
\mid 5(y-1)$, en het lemma van Gauss ($\gcd(3,5) = 1$) geeft $3 \mid y -
1$: $y = 1 - 3k$, waarna $x = -1 + 5k$. Omgekeerd voldoet elk zo’n paar:

$$
(x, y) = (-1 + 5k,\ 1 - 3k), \qquad k \in \Z .
$$

Het patroon is algemeen: één particuliere oplossing plus de geheeltallige veelvouden van $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — dezelfde structuur “particulier plus homogeen” als in [Hoofdstuk 5](https://one-course.com/books/math/3/nl/chapter/5-lineaire-differentiaalvergelijkingen#ch-b1-diffeq), met het lemma van Gauss in de rol van de uniciteit.

**Definitie 6.10 (Kleinste gemene veelvoud).**

$\operatorname{lcm}(a, b)$ is de voortbrenger in $\N$ van de deelgroep $a\Z \cap b\Z$: het is een gemeen veelvoud van $a$ en $b$ dat elk gemeen veelvoud [deelt](#def-b1-arith-divides), en voor $a, b \in
\N^*$ geldt

$$
\gcd(a,b) \times \operatorname{lcm}(a,b) = ab
\qquad (\text{bewijs in } \text{Oefening 6.5}).
$$

**Voorbeeld 6.11 (Samenloopvragen zijn kgv-vragen).**

Twee in elkaar grijpende tandwielen hebben $84$ en $36$ tanden. Na hoeveel tanden gemeenschappelijke beweging keren ze samen naar hun beginstand terug? De configuratie herhaalt zich wanneer het aantal verstreken tanden een gemeen veelvoud van $84$ en $36$ is; de eerste keer is dat na

$$
\operatorname{lcm}(84, 36) = \frac{84 \times 36}{\gcd(84, 36)}
= \frac{3024}{12} = 252
$$

tanden — dat wil zeggen $3$ omwentelingen van het grote en $7$ van het kleine tandwiel ($252/84$ en $252/36$). Let op de praktische weg: *bereken eerst de ggd* (Euclides: $84 = 2\times36 + 12$, $36 =
3\times12$) en deel dan — bouw het kgv nooit door veelvouden op te sommen. Elke vraag over periodieke samenloop (tandwielen, standen van planeten, samenvallende repeterende breuken) herleidt zich tot deze ene berekening.

## 6.3 Priemgetallen

**Definitie 6.12.**

Een geheel getal $p \geq 2$ heet *priem* wanneer zijn enige positieve delers $1$ en $p$ zijn. Voor $p$ priem en $a \in \Z$ geldt: ofwel $p \mid a$, ofwel $\gcd(p, a) = 1$. Bijgevolg ([Stelling 6.8](#thm-b1-arith-gauss)) geldt het *lemma van Euclides*: is $p
\mid ab$, dan $p \mid a$ of $p \mid b$.

**Opmerking 6.13 (Primaliteit toetsen met proefdelingen).**

Is $n = ab$ met $2 \leq a \leq b$, dan is $a^2 \leq ab = n$, dus $a
\leq \sqrt n$: een samengesteld getal $n$ heeft altijd een [priemdeler](#def-b1-arith-prime) $\leq \sqrt n$. Om na te gaan of $n$ [priem](#def-b1-arith-prime) is volstaat het dus de [priemgetallen](#def-b1-arith-prime) tot $\sqrt n$ te proberen. Voor $n = 271$: $\sqrt{271} <
17$, en $271$ is door geen van $2, 3, 5, 7, 11, 13$ [deelbaar](#def-b1-arith-divides) (oneven, cijfersom $10$, eindigt niet op $0$ of $5$, en $271 = 7\cdot38 + 5 =
11\cdot24 + 7 = 13\cdot20 + 11$): [priem](#def-b1-arith-prime), na zes delingen in plaats van tweehonderd. De grens $\sqrt n$ is een echte drempel: haar efficiënt overschrijden voor getallen van honderd cijfers vergt de moderne primaliteitstests die uit [Stelling 6.23](#thm-b1-arith-fermat) gegroeid zijn.

**Stelling 6.14 (Euclides).**

Er zijn oneindig veel [priemgetallen](#def-b1-arith-prime).

**Bewijs.** Elk geheel getal $n \geq 2$ heeft een [priemdeler](#def-b1-arith-prime): zijn kleinste deler $\geq 2$ is [priem](#def-b1-arith-prime) (een echte ontbinding daarvan zou een kleinere deler van $n$ opleveren). Stel nu dat $p_1, \dots, p_k$ alle [priemgetallen](#def-b1-arith-prime) waren, en zet $N = p_1 p_2 \cdots p_k + 1 \geq 2$. Een zeker [priemgetal](#def-b1-arith-prime) $p_i$ [deelt](#def-b1-arith-divides) $N$; maar $p_i$ [deelt](#def-b1-arith-divides) ook $N - 1 = p_1\cdots p_k$, dus $p_i
\mid 1$ — ongerijmd. ∎

**Stelling 6.15 (Hoofdstelling van de getaltheorie).**

Elk geheel getal $n \geq 2$ is een product van [priemgetallen](#def-b1-arith-prime), en de ontbinding

$$
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\qquad (p_1 < p_2 < \dots < p_k \text{ priem},\ \alpha_i \in \N^*)
$$

is uniek.

**Bewijs.** *Bestaan* met sterke inductie ([Stelling 1.12](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#thm-b1-logic-induction)): $n =
2$ is [priem](#def-b1-arith-prime); voor $n > 2$ is $n$ ofwel [priem](#def-b1-arith-prime), ofwel $n = ab$ met $2 \leq
a, b < n$, en de inductiehypothese ontbindt $a$ en $b$.

*Uniciteit.* Stel $p_1 \cdots p_r = q_1 \cdots q_s$ ([priemgetallen](#def-b1-arith-prime) met herhaling opgesomd, zeg $r \leq s$) en voer inductie naar $r$. Is $r
= 0$, dan is het linkerlid $1$, wat $s = 0$ afdwingt (een niet-leeg product van [priemgetallen](#def-b1-arith-prime) is groter dan $1$). Voor $r \geq 1$: het [priemgetal](#def-b1-arith-prime) $p_1$ [deelt](#def-b1-arith-divides) $q_1(q_2\cdots q_s)$, dus volgens het lemma van Euclides geldt $p_1 \mid q_1$ of $p_1 \mid q_2\cdots q_s$; herhalen geeft dat $p_1$ een zekere $q_j$ [deelt](#def-b1-arith-divides). Maar $q_j$ is [priem](#def-b1-arith-prime) en $p_1 \geq 2$: noodzakelijk is $p_1 = q_j$. Streep die gemeenschappelijke factor weg (geoorloofd: $\Z$ is een integriteitsdomein) en verkrijg

$$
p_2 \cdots p_r = q_1 \cdots \widehat{q_j} \cdots q_s
$$

(het dakje duidt de weglating aan), een gelijkheid van kortere producten; volgens de inductiehypothese vallen de twee lijsten $p_2, \dots, p_r$ en $q_1, \dots, \widehat{q_j}, \dots, q_s$ op de volgorde na samen, en dus ook de oorspronkelijke. De exponentvorm groepeert gelijke [priemgetallen](#def-b1-arith-prime). ∎

**Propositie 6.16 (Waarderingen).**

Schrijf voor $p$ [priem](#def-b1-arith-prime) en $n \in \N^*$ het symbool $v_p(n)$ voor de exponent van $p$ in de ontbinding van $n$ (met $v_p(n) = 0$ als $p \nmid
n$). Dan is

$$
v_p(mn) = v_p(m) + v_p(n),
\qquad
m \mid n \iff \forall p,\ v_p(m) \leq v_p(n),
$$

$$
v_p\bigl(\gcd(m,n)\bigr) = \min\bigl(v_p(m), v_p(n)\bigr),
\qquad
v_p\bigl(\operatorname{lcm}(m,n)\bigr) = \max\bigl(v_p(m),
v_p(n)\bigr).
$$

**Bewijs.** De eerste identiteit geldt omdat de ontbindingen vermenigvuldigen en de ontbinding van $mn$ uniek is. Is $m \mid n$, schrijf dan $n = mq$ en pas haar toe. Omgekeerd, geldt $v_p(m) \leq v_p(n)$ voor alle $p$, dan voldoet het gehele getal $q = \prod_p p^{\,v_p(n) - v_p(m)}$ aan $mq =
n$. De formule voor de ggd: het getal $d = \prod p^{\min}$ [deelt](#def-b1-arith-divides) beide volgens het criterium, en elke gemene deler $c$ heeft $v_p(c) \leq \min$ voor alle $p$, dus $c \mid d$; dezelfde redenering voor het kgv met $\max$. ∎

**Voorbeeld 6.17 (Kwadraten en derde machten via waarderingen).**

Een geheel getal $n \geq 1$ is een volkomen kwadraat dan en slechts dan als elke $v_p(n)$ even is (is $n = m^2$, dan is $v_p(n) = 2v_p(m)$; omgekeerd halveer je elke exponent). Analoog voor derde machten met veelvouden van $3$. Zo is $21168 = 2^4 \times 3^3 \times 7^2$ geen kwadraat ($v_3 = 3$ is oneven) en geen derde macht ($v_2 = 4$); het kleinste positieve gehele getal $m$ waarvoor $21168\,m$ *wel* een derde macht is, vind je door elke exponent tot het volgende veelvoud van $3$ aan te vullen:

$$
m = 2^{6-4} \times 3^{3-3} \times 7^{3-2} = 2^2 \times 7 = 28,
\qquad
21168 \times 28 = 2^6\,3^3\,7^3 = (2^2 \times 3 \times 7)^3
= 84^3 .
$$

Het inzicht: multiplicatieve vragen (kwadraten, derde machten, delers, ggd, kgv) worden *coördinaatsgewijze* vragen over de exponentvectoren $(v_2, v_3, v_5, \dots)$ — en de uniciteit van de [priemontbinding](#thm-b1-arith-fta) is precies de [uitspraak](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-statement) dat die coördinaten bestaan en welbepaald zijn.

## 6.4 Congruenties

**Definitie 6.18.**

Voor $n \in \N^*$ schrijven we $a \equiv b \pmod n$ wanneer $n \mid a - b$. Dat is een [equivalentierelatie](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-equiv) die verenigbaar is met optellen en vermenigvuldigen: is $a \equiv b$ en $a' \equiv b'$ (mod $n$), dan is $a + a' \equiv b + b'$, $aa' \equiv bb'$ en $a^k \equiv
b^k$ voor $k \in \N$.

**Voorbeeld 6.19 (De negenproef).**

De verenigbaarheid met $+$ en $\times$ is een controlemiddel dat zo oud is als de handel. Omdat $10 \equiv 1 \pmod 9$, is elk geheel getal modulo $9$ congruent met zijn cijfersom (bewezen als [Oefening 6.2](#exo-b1-arith-2)). Om de bewering $1234 \times 567 = 699\,678$ te toetsen: de cijfersommen geven $1234 \equiv 1$ en $567 \equiv 18 \equiv 0 \pmod 9$, dus moet het product $\equiv 1 \times 0 = 0$ zijn; en inderdaad is $6 + 9 + 9 + 6 + 7
+ 8 = 45 \equiv 0$. De proef slaagt (en het product klopt ook echt). Had iemand $699\,478$ gemeld, dan zou de cijfersom $43 \equiv 7 \not\equiv 0$ hem meteen ontmaskeren. De toets is eenzijdig — ze betrapt een fout tenzij de fout zelf een veelvoud van $9$ is — en dat is in het klein precies de les over pseudopriemgetallen uit [Voorbeeld 6.24](#ex-b1-arith-pseudoprime): controles met [congruenties](#def-b1-arith-congruence) weerleggen, ze bewijzen niet.

**Propositie 6.20 (Inverteerbaarheid modulo nnn).**

$a$ is *inverteerbaar modulo $n$* (dat wil zeggen $ab \equiv 1 \pmod
n$ voor een zekere $b$) dan en slechts dan als $\gcd(a, n) = 1$. De inverse is dan uniek modulo $n$ en wordt berekend met het uitgebreide [algoritme van Euclides](#met-b1-arith-euclid).

**Bewijs.** $ab \equiv 1 \pmod n$ betekent $ab + nk = 1$ voor een zekere $k$: een betrekking van Bézout, die bestaat precies wanneer $\gcd(a,n) = 1$ ([Gevolg 6.5](#cor-b1-arith-bezout)). Uniciteit: is $ab \equiv ab' \equiv 1$, dan is $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$. ∎

**Voorbeeld 6.21 (777 inverteren modulo 262626).**

Omdat $\gcd(7, 26) = 1$, is de klasse van $7$ inverteerbaar modulo $26$. Uitgebreid Euclides:

$$
26 = 3 \times 7 + 5, \qquad
7 = 1 \times 5 + 2, \qquad
5 = 2 \times 2 + 1 ,
$$

en dan achterstevoren:

$$
1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7
= 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .
$$

Bijgevolg is $7 \times (-11) \equiv 1 \pmod{26}$, oftewel $7^{-1} \equiv
-11 \equiv 15 \pmod{26}$; controle: $7 \times 15 = 105 = 4 \times 26 +
1$. Met de inverse in handen los je elke [congruentie](#def-b1-arith-congruence) $7x \equiv c
\pmod{26}$ in één vermenigvuldiging op: $x \equiv 15c$. Dit mechanische inverteren is het werkpaard van het modulaire rekenen — en van de protocollen met publieke sleutel die in [Opmerking 6.27](#rem-b1-arith-whereused) genoemd worden, waar de moduli honderden cijfers tellen maar het algoritme exact dit is.

**Voorbeeld 6.22 (Wanneer de coëfficiënt niet inverteerbaar is).**

Los $12x \equiv 8 \pmod{20}$ op. Hier is $\gcd(12, 20) = 4$, dus $12$ is niet inverteerbaar modulo $20$ — maar de vergelijking blijft hanteerbaar. De [congruentie](#def-b1-arith-congruence) zegt $20 \mid 12x - 8$; deling van de hele betrekking door $4$ (een deler van alle drie de ingrediënten) maakt haar equivalent met $5 \mid 3x - 2$, oftewel

$$
3x \equiv 2 \pmod 5 .
$$

Nu is $\gcd(3, 5) = 1$ en $3^{-1} \equiv 2 \pmod 5$ (want $3 \times 2 = 6
\equiv 1$), dus $x \equiv 4 \pmod 5$: de oplossingen zijn $x \equiv 4, 9,
14, 19 \pmod{20}$ — *vier* klassen modulo $20$, overeenkomend met de ggd. (Was het rechterlid niet [deelbaar](#def-b1-arith-divides) door $4$ geweest, zeg $12x
\equiv 6 \pmod{20}$, dan was er helemaal geen oplossing: het linkerlid is altijd $\equiv 0 \pmod 4$.) Algemene vorm: $ax \equiv b \pmod n$ is oplosbaar precies wanneer $\gcd(a, n) \mid b$, en heeft dan precies $\gcd(a, n)$ oplossingsklassen — deel alles door de ggd en inverteer.

**Stelling 6.23 (Kleine stelling van Fermat).**

Zij $p$ [priem](#def-b1-arith-prime). Voor elke $a \in \Z$ geldt

$$
a^p \equiv a \pmod p,
$$

en is $p \nmid a$, dan $a^{p-1} \equiv 1 \pmod p$.

**Bewijs.** Merk eerst op dat voor $1 \leq k \leq p - 1$ de [binomiaalcoëfficiënt](https://one-course.com/books/math/3/nl/chapter/2-telkunde#def-b1-counting-objects) $\binom pk = \frac{p!}{k!(p-k)!}$ [deelbaar](#def-b1-arith-divides) is door $p$: immers $k!\,(p-k)!\, \binom pk = p!$, en $p$ [deelt](#def-b1-arith-divides) $p!$ maar is [relatief priem](#cor-b1-arith-bezout) met $k!(p-k)!$ (alle factoren zijn $< p$), zodat het lemma van Gauss $p
\mid \binom pk$ geeft.

Bewijs nu $a^p \equiv a$ voor $a \in \N$ met inductie. Waar voor $a = 0$. Is $a^p \equiv a$, dan geeft het binomium

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

waarbij alle middelste termen modulo $p$ verdwijnen. Voor $a < 0$ pas je het resultaat toe op $-a$ en onderscheid je $p = 2$ (waar $x \equiv -x$) van oneven $p$ (waar $(-a)^p = -a^p$). Is ten slotte $p \nmid a$, dan vermenigvuldig je $a^p \equiv a$ met een inverse van $a$ modulo $p$ ([Propositie 6.20](#prop-b1-arith-invmod)). ∎

**Voorbeeld 6.24 (De omkering van Fermat faalt: 341341341).**

De kleine stelling van Fermat levert een goedkope toets op *samengesteldheid*: is $a^{n-1} \not\equiv 1 \pmod n$ voor een zekere $a$ die [relatief priem](#cor-b1-arith-bezout) is met $n$, dan is $n$ niet [priem](#def-b1-arith-prime). Zou de toets ook primaliteit kunnen waarborgen? Nee: neem $n = 341 = 11 \times
31$, samengesteld, en $a = 2$. Omdat $2^{10} = 1024 = 3 \times 341 + 1$, is

$$
2^{10} \equiv 1 \pmod{341}
\qquad\Longrightarrow\qquad
2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :
$$

het samengestelde getal $341$ doorstaat de toets van Fermat voor het grondtal $2$ (het is het kleinste zulke *pseudopriemgetal*). Het grondtal $3$ ontmaskert het ($3^{340} \not\equiv 1$), en in de praktijk draait een primaliteitstoets daarom op verscheidene grondtallen, plus verfijningen — de industriële versies van dit idee zijn wat de grote [priemgetallen](#def-b1-arith-prime) uit [Opmerking 6.27](#rem-b1-arith-whereused) waarborgt. Moraal: een implicatie en haar omkering leiden gescheiden levens ([Opmerking 1.10](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#rem-b1-logic-pitfalls)), zelfs bij stellingen.

**Voorbeeld 6.25 (Praktisch rekenen met congruenties).**

Wat is de rest van $7^{2026}$ modulo $11$? Volgens Fermat is $7^{10}
\equiv 1 \pmod{11}$. Omdat $2026 = 10 \times 202 + 6$, is

$$
7^{2026} \equiv 7^6 = (7^2)^3 = 49^3 \equiv 5^3 = 125 \equiv 4
\pmod{11}.
$$

De rest is $4$. De strategie: reduceer de exponent modulo de orde die Fermat levert, en reduceer daarna bij elke stap de tussenmachten.

**Opmerking 6.26 (Veelgemaakte fouten in de getaltheorie).**

1. *Een [congruentie](#def-b1-arith-congruence) delen.* Uit $ac \equiv bc \pmod n$ mag je *niet* $a \equiv b$ besluiten tenzij $\gcd(c, n) = 1$ : er is $6 \equiv 2 \pmod 4$ maar $3 \not\equiv 1 \pmod 4$ . De juiste algemene regel [deelt](#def-b1-arith-divides) ook de [modulus](https://one-course.com/books/math/3/nl/chapter/3-complexe-getallen#def-b1-complex-field) : $ac \equiv bc \pmod n \iff  a \equiv b \pmod{n/\gcd(c,n)}$ .
2. *Het lemma van Euclides misbruiken.* Uit $a \mid bc$ volgt $a \mid b$ of $a \mid c$ alleen voor *prieme* $a$ (of voor $a$ [relatief priem](#cor-b1-arith-bezout) met een van beide factoren): $6 \mid 4 \times  9$ , en toch [deelt](#def-b1-arith-divides) $6$ geen van beide factoren.
3. *[Relatief priem](#cor-b1-arith-bezout) is een relatie, geen eigenschap.* “ $8$ en $9$ zijn [relatief priem](#cor-b1-arith-bezout) ” is waar hoewel geen van beide [priem](#def-b1-arith-prime) is; “twee aan twee [relatief priem](#cor-b1-arith-bezout) ” is sterker dan “in hun geheel [relatief priem](#cor-b1-arith-bezout) ” ( $\gcd(6, 10, 15) = 1$ , terwijl geen enkel paar [relatief priem](#cor-b1-arith-bezout) is).
4. *Exponenten leven niet modulo $n$.* In $a^k \bmod n$ mag de exponent alleen modulo de *orde* van $a$ gereduceerd worden (bijvoorbeeld $p - 1$ wanneer Fermat van toepassing is), nooit modulo $n$ : $2^{10} \bmod 11$ is $1$ , niet $2^{10 \bmod 11} =  2^{10}$ — de reductie die wel werkt is die van [Voorbeeld 6.25](#ex-b1-arith-congruences) .

**Opmerking 6.27 (Waar dit hoofdstuk gebruikt wordt).**

Dit hoofdstuk is evenzeer een sjabloon als een gereedschapskist. De hele keten — euclidische deling, ggd, Bézout, Gauss, unieke ontbinding — wordt letterlijk overgespeeld voor veeltermen in [Hoofdstuk 8](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly), waar “graad” de rol van de absolute waarde speelt; beide hoofdstukken naast elkaar leggen is de beste manier om ze allebei te begrijpen. Het rekenen met [congruenties](#def-b1-arith-congruence) wordt de ring $\Z/n\Z$ in [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures), waarvan de inverteerbare elementen ([Propositie 6.20](#prop-b1-arith-invmod)) het eerste niet-triviale voorbeeld van een eenhedengroep vormen. Waarderingen keren terug in de weekendopgave hieronder (de formule van Legendre) en dragen de irrationaliteitsbewijzen van [Hoofdstuk 10](https://one-course.com/books/math/3/nl/chapter/10-reele-getallen#ch-b1-reals). Buiten dit volume is inverteren met Bézout modulo $n$ de motor van de cryptografie met publieke sleutel, en is de kleine stelling van Fermat de grootvader van de primaliteitstests die de grote [priemgetallen](#def-b1-arith-prime) daar waarborgen.

**Opmerking 6.28 (Tussenspel: Z\ZZ als sjabloon).**

Doe een stap terug van de afzonderlijke stellingen en bekijk de architectuur van het hoofdstuk: één gereedschap (de euclidische deling) bracht een classificatie voort (de deelgroepen $n\Z$), die een bestaansstelling voortbracht (ggd, Bézout), die een rekenkunde van de [deelbaarheid](#def-b1-arith-divides) voortbracht (Gauss), die de unieke ontbinding voortbracht — en elke verdieping rust alleen op de verdieping eronder. Datzelfde gebouw wordt in dit volume nog tweemaal opgetrokken met een andere benedenverdieping: in [Hoofdstuk 8](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly), waar delen naar graad het delen naar grootte vervangt en al het bovenstaande zich *letterlijk* herhaalt; en, in het klein, binnen elke $\Z/n\Z$ van [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures), waar vragen over inverteerbaarheid (de [Propositie 6.20](#prop-b1-arith-invmod) van dit hoofdstuk) structurele [uitspraken](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-statement) over ringen en lichamen worden. Een argument herkennen als “het $\Z$-argument, overgeplant” is de snelste manier om die hoofdstukken te leren — en de eerste smaak van de kerngewoonte van de algebra: stellingen bewijzen over *axioma’s* in plaats van over objecten.

![De rijen 0 tot en met 7 van de driehoek van Pascal, met de oneven getallen ingevuld: rij n bevat er 2s_2(n), waarbij s_2(n) het aantal enen in de binaire schrijfwijze van n is (rijen 1, 2, 4: twee oneven getallen; rij 7 = (111)_2: alle acht). Het zelfgelijkvormige patroon — elke “driehoek van oneven getallen” brengt twee kopieën van zichzelf voort — is de stelling van Kummer in beeld, bewezen in de weekendopgave hieronder.](https://one-course.com/images/onecourse/chapters/math-3/b1-arith/fig-8546c89fa14c.svg)

*De rijen $0$ tot en met $7$ van de driehoek van Pascal, met de *oneven* getallen ingevuld: rij $n$ bevat er $2^{s_2(n)}$, waarbij $s_2(n)$ het aantal enen in de binaire schrijfwijze van $n$ is (rijen $1, 2, 4$: twee oneven getallen; rij $7 = (111)_2$: alle acht). Het zelfgelijkvormige patroon — elke “driehoek van oneven getallen” brengt twee kopieën van zichzelf voort — is de stelling van Kummer in beeld, bewezen in de weekendopgave hieronder.*

## 6.5 Oefeningen

**Oefening 6.1 ★.**

Bereken $\gcd(1\,001, 777)$ met het [algoritme van Euclides](#met-b1-arith-euclid), en geef er een paar van Bézout bij.

**Oplossing van Oefening 6.1.**

$1001 = 1 \times 777 + 224$; $777 = 3 \times 224 + 105$; $224 = 2 \times
105 + 14$; $105 = 7 \times 14 + 7$; $14 = 2 \times 7 + 0$. Dus $\gcd(1001, 777) = 7$. Achterstevoren:

$$
7 = 105 - 7 \times 14
= 105 - 7(224 - 2\times 105) = 15 \times 105 - 7 \times 224
$$

$$
= 15(777 - 3\times 224) - 7\times 224 = 15 \times 777 - 52 \times 224
= 15 \times 777 - 52(1001 - 777) = 67 \times 777 - 52 \times 1001 .
$$

Controle: $67 \times 777 = 52\,059$ en $52 \times 1001 = 52\,052$; verschil $7$. Paar van Bézout: $(u, v) = (-52, 67)$ voor $1001u + 777v =
7$.

**Oefening 6.2 ★.**

Bewijs de deelbaarheidsregels in grondtal $10$: een geheel getal is modulo $9$ congruent met de som van zijn cijfers, en modulo $11$ met de alternerende som van zijn cijfers. Wat is $123\,456\,789$ modulo $9$ en modulo $11$?

**Oplossing van Oefening 6.2.**

Omdat $10 \equiv 1 \pmod 9$, is $10^k \equiv 1$, zodat $\sum_k d_k 10^k
\equiv \sum_k d_k \pmod 9$. Omdat $10 \equiv -1 \pmod{11}$, is $10^k
\equiv (-1)^k$, zodat het getal modulo $11$ congruent is met de alternerende som $\sum_k (-1)^k d_k$ (te beginnen bij het cijfer van de *eenheden*, met teken $+$).

$123\,456\,789$: cijfersom $45 \equiv 0 \pmod 9$. Alternerende som vanaf de eenheden: $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$, dus het getal is $\equiv 5 \pmod{11}$.

**Oefening 6.3 ★.**

Los op in $\Z$: $91x \equiv 1 \pmod{237}$ *(uitgebreid Euclides)*.

**Oplossing van Oefening 6.3.**

Euclides: $237 = 2 \times 91 + 55$; $91 = 1 \times 55 + 36$; $55 = 1
\times 36 + 19$; $36 = 1 \times 19 + 17$; $19 = 1 \times 17 + 2$; $17 = 8
\times 2 + 1$. Achterstevoren:

$$
1 = 17 - 8\times 2 = 17 - 8(19 - 17) = 9\times 17 - 8\times 19
= 9(36 - 19) - 8\times 19 = 9\times 36 - 17\times 19
$$

$$
= 9\times 36 - 17(55 - 36) = 26\times 36 - 17\times 55
= 26(91 - 55) - 17\times 55 = 26\times 91 - 43\times 55
$$

$$
= 26\times 91 - 43(237 - 2\times 91) = 112 \times 91 - 43 \times 237.
$$

Dus $91 \times 112 \equiv 1 \pmod{237}$: de oplossingen zijn $x \equiv
112 \pmod{237}$. (Controle: $91 \times 112 = 10\,192 = 43 \times 237 +
1$.)

**Oefening 6.4 ★.**

Bepaal alle paren $(x, y) \in \Z^2$ met $17x + 39y = 1$; en vervolgens alle paren met $17 x + 39 y = 5$.

**Oplossing van Oefening 6.4.**

$\gcd(17, 39) = 1$: Euclides geeft $39 = 2\times 17 + 5$, $17 = 3\times 5
+ 2$, $5 = 2\times 2 + 1$, en achterstevoren

$$
1 = 5 - 2\times 2 = 5 - 2(17 - 3\times 5) = 7\times 5 - 2\times 17
= 7(39 - 2\times 17) - 2\times 17 = 7\times 39 - 16\times 17 .
$$

Particuliere oplossing $(x_0, y_0) = (-16, 7)$. Algemene oplossing van de homogene vergelijking $17x + 39y = 0$: $x = 39k$, $y = -17k$ (want $17
\mid 39y$ en $\gcd(17,39) = 1$ dwingen $17 \mid y$ af — het lemma van Gauss). Bijgevolg is

$$
(x, y) = (-16 + 39k,\; 7 - 17k), \qquad k \in \Z .
$$

Voor het rechterlid $5$ vermenigvuldig je de particuliere oplossing met $5$: $(x, y) = (-80 + 39k,\; 35 - 17k)$ met $k \in \Z$.

**Oefening 6.5 ★★.**

Bewijs dat voor $a, b \in \N^*$ geldt: $\gcd(a,b) \times
\operatorname{lcm}(a,b) = ab$. *(Gebruik de formules voor waarderingen uit [Propositie 6.16](#prop-b1-arith-valuation) en $\min(\alpha,\beta) +
\max(\alpha,\beta) = \alpha + \beta$.)*

**Oplossing van Oefening 6.5.**

Voor elk [priemgetal](#def-b1-arith-prime) $p$ geldt, met $\alpha = v_p(a)$ en $\beta = v_p(b)$,

$$
v_p\bigl(\gcd(a,b)\bigr) + v_p\bigl(\operatorname{lcm}(a,b)\bigr)
= \min(\alpha, \beta) + \max(\alpha, \beta)
= \alpha + \beta = v_p(ab) .
$$

Twee positieve gehele getallen met dezelfde waardering in elk [priemgetal](#def-b1-arith-prime) zijn gelijk ([Propositie 6.16](#prop-b1-arith-valuation)), dus is $\gcd(a,b)\operatorname{lcm}(a,b) = ab$.

**Oefening 6.6 ★★.**

Zij $a = 2^{10} \times 3^4 \times 5^2$ en $b = 2^6 \times 3^7 \times 7$. Bereken $\gcd(a, b)$, $\operatorname{lcm}(a,b)$ en het aantal positieve delers van $a$. *(Bewijs de formule $\prod_i (\alpha_i + 1)$ voor het aantal delers.)*

**Oplossing van Oefening 6.6.**

Waarderingen: $\gcd(a, b) = 2^{\min(10,6)} 3^{\min(4,7)} 5^{\min(2,0)}
7^{\min(0,1)} = 2^6\, 3^4 = 5184$ en $\operatorname{lcm}(a,b) = 2^{10}\,
3^7\, 5^2\, 7$.

Aantal delers: een positieve deler van $n = \prod p_i^{\alpha_i}$ is precies een keuze $\prod p_i^{\beta_i}$ met $0 \leq \beta_i \leq
\alpha_i$ ([Propositie 6.16](#prop-b1-arith-valuation)); de keuzes zijn onafhankelijk, dus zijn er $\prod_i (\alpha_i + 1)$ delers. Voor $a$: $(10+1)(4+1)(2+1)
= 165$.

**Oefening 6.7 ★★.**

Bewijs dat $\sqrt p$ irrationaal is voor elk [priemgetal](#def-b1-arith-prime) $p$, met waarderingen: vergelijk $v_p$ van beide leden van $p q^2 = r^2$.

**Oplossing van Oefening 6.7.**

Stel $\sqrt p = \frac rq$ met $r, q \in \N^*$, oftewel $p q^2 = r^2$. Pas $v_p$ toe: $v_p(pq^2) = 1 + 2v_p(q)$ is oneven, terwijl $v_p(r^2) = 2
v_p(r)$ even is. Eén geheel getal kan niet tegelijk een oneven en een even $p$-waardering hebben: tegenspraak. Dus $\sqrt p \notin \Q$.

**Oefening 6.8 ★★.**

(Chinees restprobleem) Bepaal alle gehele getallen $x$ met

$$
x \equiv 2 \pmod 7, \qquad x \equiv 5 \pmod{11}.
$$

Bewijs onderweg dat voor [relatief prieme](#cor-b1-arith-bezout) $m, n$ het paar [congruenties](#def-b1-arith-congruence) $x
\equiv a \ (m)$, $x \equiv b\ (n)$ altijd een oplossing heeft, uniek modulo $mn$.

**Oplossing van Oefening 6.8.**

*Algemeen feit.* Met $\gcd(m,n) = 1$ geeft Bézout $mu + nv = 1$. Zet $x_0 = b\,mu + a\,nv$. Dan is $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a
\pmod m$ en analoog $x_0 \equiv b \pmod n$: het bestaan. Zijn $x$ en $x'$ twee oplossingen, dan delen $m$ en $n$ het getal $x - x'$, dus $mn \mid x
- x'$ ([Stelling 6.8](#thm-b1-arith-gauss) (2)): de uniciteit modulo $mn$.

*Numeriek:* $m = 7$, $n = 11$: $7 \times (-3) + 11 \times 2 = 1$. Dus $x_0 = 5 \times 7 \times (-3) + 2 \times 11 \times 2 = -105 + 44 =
-61 \equiv 16 \pmod{77}$. Controle: $16 = 2\times 7 + 2 \equiv 2 \pmod 7$ en $16 = 11 + 5 \equiv 5 \pmod{11}$. Oplossingen: $x \equiv 16 \pmod{77}$.

**Oefening 6.9 ★★.**

Bereken $3^{1000}$ modulo $7$, en de laatste twee decimale cijfers van $7^{100}$ *(modulo $100 = 4 \times 25$: gebruik [Oefening 6.8](#exo-b1-arith-8))*.

**Oplossing van Oefening 6.9.**

Modulo $7$: Fermat geeft $3^6 \equiv 1$, en $1000 = 6 \times 166 + 4$, dus $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

Laatste twee cijfers van $7^{100}$: werk modulo $4$ en modulo $25$. Modulo $4$ is $7 \equiv -1$, dus $7^{100} \equiv 1$. Modulo $25$ is $7^2
= 49 \equiv -1$, dus $7^4 \equiv 1$ en $7^{100} = (7^4)^{25} \equiv 1$. Volgens de Chinese reststelling ([Oefening 6.8](#exo-b1-arith-8)) is $7^{100}
\equiv 1 \pmod{100}$: de laatste twee cijfers zijn $01$.

**Oefening 6.10 ★★★.**

Bewijs voor $m, n \in \N^*$ dat $\gcd(2^m - 1,\, 2^n - 1) =
2^{\gcd(m,n)} - 1$. *Aanwijzing: toon eerst aan dat de rest van $2^m
- 1$ modulo $2^n - 1$ gelijk is aan $2^r - 1$, waarbij $r$ de rest van $m$ modulo $n$ is; volg dan het [algoritme van Euclides](#met-b1-arith-euclid).*

**Oplossing van Oefening 6.10.**

Schrijf $m = nq + r$ met $0 \leq r < n$. Dan is

$$
2^m - 1 = 2^r\bigl(2^{nq} - 1\bigr) + 2^r - 1,
$$

en $2^n - 1$ [deelt](#def-b1-arith-divides) $2^{nq} - 1 = (2^n - 1)(2^{n(q-1)} + \dots + 1)$. Dus is modulo $2^n - 1$ het getal $2^m - 1 \equiv 2^r - 1$, en omdat $0 \leq
2^r - 1 < 2^n - 1$ *is* dat de euclidische rest.

Bijgevolg spiegelt het [algoritme van Euclides](#met-b1-arith-euclid) op het paar $(2^m - 1, 2^n
- 1)$ exponent voor exponent het algoritme op $(m, n)$: elke delingsstap vervangt boven $(m, n)$ door $(n, r)$ en beneden $(2^m - 1, 2^n - 1)$ door $(2^n - 1, 2^r - 1)$. Boven eindigt het algoritme in $\gcd(m,n)$, dus beneden in $2^{\gcd(m,n)} - 1$.

**Oefening 6.11 ★★★.**

(Stelling van Wilson) Zij $p$ [priem](#def-b1-arith-prime). Bewijs dat

$$
(p-1)! \equiv -1 \pmod p ,
$$

door elke factor van $(p-1)!$ met haar inverse modulo $p$ te koppelen en de factoren aan te wijzen die met zichzelf gekoppeld worden (los eerst $x^2 \equiv 1 \pmod p$ op). Ga de omkering na: is $n \geq 2$ niet [priem](#def-b1-arith-prime), dan is $(n-1)! \not\equiv -1 \pmod n$.

**Oplossing van Oefening 6.11.**

Los eerst $x^2 \equiv 1 \pmod p$ op: $p \mid (x-1)(x+1)$, dus volgens het lemma van Euclides is $x \equiv 1$ of $x \equiv -1 \pmod p$.

In het product $(p-1)! = 1 \times 2 \times \dots \times (p-1)$ is elke factor $a$ inverteerbaar modulo $p$, en haar inverse $a^{-1}$ is opnieuw een van de factoren ([Propositie 6.20](#prop-b1-arith-invmod)). Koppel elke $a$ aan $a^{-1}$: de paren hebben product $1$, behalve de factoren die met zichzelf gekoppeld worden ($a = a^{-1}$, oftewel $a^2 \equiv 1$) — en dat zijn precies $1$ en $p - 1$. Bijgevolg is

$$
(p-1)! \equiv 1 \times (p - 1) \equiv -1 \pmod p .
$$

(Voor $p = 2$: $1! = 1 \equiv -1 \pmod 2$; het koppelargument ontaardt, maar het resultaat blijft gelden.)

*Omkering.* Zij $n \geq 2$ samengesteld, $n = ab$ met $1 < a \leq b
< n$. Is $a < b$, dan komen beide als verschillende factoren van $(n-1)!$ voor, dus $n \mid (n-1)!$ en $(n-1)! \equiv 0 \not\equiv -1$. Is $a = b$ (dus $n = a^2$): voor $a \geq 3$ zijn zowel $a$ als $2a$ kleiner dan $n$, zodat $n = a^2 \mid a \times 2a \mid (n-1)!$, met dezelfde conclusie; voor $n = 4$ is $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$.

**Oefening 6.12 ★★★.**

(Getallen van Fermat) Zet voor $n \in \N$ het getal $F_n = 2^{2^n} + 1$.

1. Bewijs dat $F_0 F_1 \cdots F_{n-1} = F_n - 2$ voor $n \geq 1$ (inductie).
2. Leid af dat de getallen van Fermat twee aan twee [relatief priem](#cor-b1-arith-bezout) zijn.
3. Leid daaruit een tweede bewijs af, onafhankelijk van [Stelling 6.14](#thm-b1-arith-euclidprimes) , dat er oneindig veel [priemgetallen](#def-b1-arith-prime) zijn.

**Oplossing van Oefening 6.12.**

1. Inductie. Voor $n = 1$: $F_0 = 3 = F_1 - 2 = 5 - 2$. Neem $F_0\cdots F_{n-1} = F_n - 2$ aan, dan is $$F_0 \cdots F_n = (F_n - 2)F_n  = \bigl(2^{2^n} - 1\bigr)\bigl(2^{2^n} + 1\bigr)  = 2^{2^{n+1}} - 1 = F_{n+1} - 2 .$$
2. Zij $m < n$ en $d = \gcd(F_m, F_n)$ . Volgens (1) [deelt](#def-b1-arith-divides) $F_m$ het getal $F_n - 2$ , dus [deelt](#def-b1-arith-divides) $d$ zowel $F_n$ als $F_n - 2$ en dus ook $2$ . Maar elk getal van Fermat is oneven, dus $d = 1$ .
3. Elke $F_n \geq 3$ heeft een [priemdeler](#def-b1-arith-prime) $p_n$ (de eerste stap van [Stelling 6.14](#thm-b1-arith-euclidprimes) ). Is $m \neq n$ , dan is $p_m \neq p_n$ , want een gemeenschappelijk [priemgetal](#def-b1-arith-prime) zou $\gcd(F_m, F_n) = 1$ delen. De [afbeelding](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-map) $n \mapsto p_n$ is dus [injectief](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-inj) van $\N$ in de [priemgetallen](#def-b1-arith-prime) : er zijn oneindig veel [priemgetallen](#def-b1-arith-prime) .

## 6.6 Opgave: de formule van Legendre en de overdrachten van Kummer

**Probleem 6.1.**

Op hoeveel nullen eindigt de decimale schrijfwijze van $1000!$ — en, dieper, wat is de exacte macht van een [priemgetal](#def-b1-arith-prime) $p$ die $1000!$ [deelt](#def-b1-arith-divides), of die een [binomiaalcoëfficiënt](https://one-course.com/books/math/3/nl/chapter/2-telkunde#def-b1-counting-objects) [deelt](#def-b1-arith-divides)? De volledige antwoorden zijn twee juwelen van de elementaire getaltheorie: de *formule van Legendre* $v_p(n!) = \sum_{k\geq1} \lfloor
n/p^k \rfloor$, met haar digitale tegenhanger $v_p(n!) = \frac{n -
s_p(n)}{p-1}$, en de *stelling van Kummer*: $v_p\binom{m+n}m$ telt de *overdrachten* bij het optellen van $m$ en $n$ in grondtal $p$. Deze opgave bewijst beide, toetst ze numeriek aan elkaar, en oogst de klassieke gevolgen — nullen aan het einde, de pariteit van de driehoek van Pascal, en een eerste afschatting in de richting van de priemgetalstelling. Overal is $p$ [priem](#def-b1-arith-prime), is $\floor{x}$ het geheel deel, en noteert $s_p(n)$ de som van de cijfers van $n$ geschreven in grondtal $p$.

**Deel I — Gehele delen, waarderingen en de formule van Legendre.**

1. Opwarmer: bereken $10!$ en lees af op hoeveel nullen het eindigt; bereken $v_2(10!)$ en $v_5(10!)$ rechtstreeks uit de ontbinding van elke factor $1, 2, \dots, 10$ .
2. Bewijs dat voor $x \in \R$ en $n \in \N^*$ geldt $\bigl\lfloor  \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
3. Bewijs dat $v_p(a + b) \geq \min\bigl(v_p(a), v_p(b)\bigr)$ voor alle $a, b \in \N^*$ , met gelijkheid zodra $v_p(a) \neq  v_p(b)$ .
4. Toon aan dat het aantal veelvouden van $m$ in $\intint1n$ gelijk is aan $\lfloor n/m \rfloor$ .
5. Bewijs de *formule van Legendre*: voor elke $n \in \N^*$ geldt $$v_p(n!) = \sum_{k=1}^{\infty}  \Bigl\lfloor \frac{n}{p^k} \Bigr\rfloor$$ (een eindige som: de termen verdwijnen zodra $p^k > n$). *Tel voor elke $k$ de factoren van $\intint1n$ die door $p^k$ [deelbaar](#def-b1-arith-divides) zijn: elke draagt precies één eenheid bij per niveau dat ze haalt.*

**Deel II — De digitale vorm en de nullen aan het einde.**

6. Bereken $v_5(1000!)$ en $v_2(1000!)$ en besluit: op hoeveel nullen eindigt $1000!$ ?
7. Bewijs de digitale vorm van de formule van Legendre: schrijf je $n = \sum_i a_i p^i$ in grondtal $p$, dan is $$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$$
8. Twee gevolgen voor $p = 2$ : toon aan dat $2^n$ het getal $n!$ nooit [deelt](#def-b1-arith-divides) , en dat $2^{n-1}$ het getal $n!$ precies dan [deelt](#def-b1-arith-divides) wanneer $n$ een macht van $2$ is.
9. Schat het tekort af: toon aan dat $\frac n{p-1} - \log_p(n) - 1  \leq v_p(n!) < \frac n{p-1}$ , zodat $\frac{v_p(n!)}{n} \to  \frac1{p-1}$ : op de lange duur groeit er per eenheid een aandeel $\frac1{p-1}$ van een factor $p$ aan.
10. Zij $Z(n) = v_5(n!)$ het aantal nullen waarop $n!$ eindigt. Toon aan dat $Z(n) - Z(n-1) = v_5(n)$ , leid af dat $Z$ de waarde $5$ volledig overslaat (bereken $Z(24)$ en $Z(25)$ ), en bewijs dat geen enkele faculteit op precies vijf nullen eindigt.

**Deel III — De stelling van Kummer.**

11. Bewijs dat $\lfloor x + y \rfloor - \lfloor x \rfloor - \lfloor y  \rfloor \in \{0, 1\}$ voor alle $x, y \in \R$, en leid uit de formule van Legendre af dat $$v_p\binom{m+n}m  = \sum_{k\geq1}\Bigl(  \Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor  - \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),$$ een som waarvan elke term $0$ of $1$ is.
12. Bewijs de *stelling van Kummer* : de $k$ -de term van die som is gelijk aan $1$ precies wanneer het optellen van $m$ en $n$ in grondtal $p$ een overdracht naar positie $k$ voortbrengt; dus telt $v_p\binom{m+n}m$ het totale aantal overdrachten. *(Schrijf $m = p^km_1 + m_0$ en $n = p^kn_1 + n_0$ met $0  \leq m_0, n_0 < p^k$ en bekijk $\lfloor (m_0 + n_0)/p^k  \rfloor$.)*
13. Leid af dat voor $0 < j < p^k$ geldt $$v_p\binom{p^k}{j} = k - v_p(j) ,$$ door de overdrachten in de optelling $j + (p^k - j)$ te tellen. (In het bijzonder $p \mid \binom p j$ voor $0 < j < p$: de sleutelstap van [Stelling 6.23](#thm-b1-arith-fermat), teruggevonden.)
14. Bewijs dat $v_2\binom{2n}n = s_2(n)$ . Leid af dat de centrale [binomiaalcoëfficiënt](https://one-course.com/books/math/3/nl/chapter/2-telkunde#def-b1-counting-objects) altijd even is, en dat $\binom{2n}n \equiv 2  \pmod 4$ precies wanneer $n$ een macht van $2$ is.
15. Toon met de identiteit van Vandermonde ( [Oefening 2.7](https://one-course.com/books/math/3/nl/chapter/2-telkunde#exo-b1-counting-7) ) en vraag 13 aan dat $\binom{2p}p  \equiv 2 \pmod p$ voor elk [priemgetal](#def-b1-arith-prime) $p$ .
16. Bereken $v_3\binom{1000}{500}$ tweemaal: één keer met Kummer (schrijf $500$ in grondtal $3$ en tel de overdrachten in $500 +  500$ ), één keer met de digitale vorm van Legendre (bereken $s_3(500)$ en $s_3(1000)$ ); ga na dat beide dezelfde waarde geven.

**Deel IV — De pariteit van de driehoek van Pascal, en een afschatting van de priemdichtheid.**

17. Bewijs het cijfercriterium: $\binom nk$ is *oneven* dan en slechts dan als elk binair cijfer van $k$ hoogstens gelijk is aan het overeenkomstige cijfer van $n$ . Formuleer en bewijs het analoge criterium voor $p \nmid \binom nk$ in grondtal $p$ .
18. Leid af dat rij $n$ van de driehoek van Pascal precies $2^{s_2(n)}$ oneven getallen bevat; ga dat na op de rijen $4$ en $5$ .
19. Leid af dat alle inwendige getallen $\binom nk$ ( $0 < k < n$ ) even zijn dan en slechts dan als $n$ een macht van $2$ is.
20. Bewijs dat elke priemmacht die $\binom{m+n}m$ [deelt](#def-b1-arith-divides) hoogstens $m  + n$ is: uit $p^a \mid \binom{m+n}m$ volgt $p^a \leq m + n$ . *(Hoeveel termen van de som uit vraag 11 kunnen ongelijk aan nul zijn?)*
21. Leid af dat $\binom{2n}n$ het getal $\operatorname{lcm}(1, 2,  \dots, 2n)$ [deelt](#def-b1-arith-divides), en combineer dat met de ondergrens $\binom{2n}n \geq \frac{4^n}{2n+1}$ (die je bewijst: het centrale getal is het grootste van de $2n + 1$ getallen van rij $2n$) om $$\operatorname{lcm}(1, \dots, 2n) \geq \frac{4^n}{2n+1}$$ te verkrijgen: de gemene veelvouden van de eerste gehele getallen groeien *exponentieel* — een eerste kwantitatieve blik op de overvloed aan [priemgetallen](#def-b1-arith-prime).

**Deel V — Synthese.**

22. Bepaal de kleinste $n$ waarvoor $n!$ op minstens $2026$ nullen eindigt. *(Schat $Z(n) \approx n/4$ en corrigeer met de exacte formule.)*
23. Nog een laatste kruiscontrole: toon aan dat $7$ het getal $\binom{100}{50}$ *niet* [deelt](#def-b1-arith-divides) , eerst door $50$ in grondtal $7$ te schrijven en na te gaan dat de optelling $50 + 50$ geen overdrachten kent, en daarna door $v_7(100!)$ en $v_7(50!)$ met de formule van Legendre te berekenen.
24. Waar precies gebruikte de opgave: (i) de unieke [priemontbinding](#thm-b1-arith-fta) ; (ii) de ontbinding $n = p^k n_1 + n_0$ uit de euclidische deling; (iii) een telargument uit [Hoofdstuk 2](https://one-course.com/books/math/3/nl/chapter/2-telkunde#ch-b1-counting) ? Eén zin per onderdeel.
25. Synthese, in een korte alinea: de formule van Legendre zet een vraag over [deelbaarheid](#def-b1-arith-divides) om in rekenen met cijfers, en de stelling van Kummer leest het antwoord af aan de overdrachten van één optelling — becommentarieer die vertaling, de controles van vraag 16, en wat de afschatting van vraag 21 over [priemgetallen](#def-b1-arith-prime) suggereert (de volledige [uitspraak](https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen#def-b1-logic-statement) , de priemgetalstelling, ligt ver buiten dit volume; de tegenhanger van de gereedschapskist van dit hoofdstuk voor veeltermen is [Hoofdstuk 8](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly) ).

**Oplossing van Probleem 6.1.**

**1.** $10! = 3\,628\,800$: twee nullen aan het einde. Waarderingen factor voor factor: machten van $2$ komen van $2, 4 = 2^2, 6, 8 = 2^3,
10$, samen $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$; machten van $5$ van $5$ en $10$: $v_5(10!) = 2$. Aantal nullen $= \min(v_2, v_5) = 2$, in overeenstemming.

**2.** Schrijf de euclidische deling $\lfloor x\rfloor = nq + r$ met $0 \leq r \leq n - 1$. Dan is $x = nq + r + \{x\}$ met $0 \leq r + \{x\}
< n$, dus $\lfloor x/n \rfloor = q = \bigl\lfloor \lfloor x \rfloor / n
\bigr\rfloor$.

**3.** Zij $\alpha = v_p(a) \leq \beta = v_p(b)$ (verwissel zo nodig) en schrijf $a = p^\alpha a'$ en $b = p^\beta b'$ met $p \nmid a',
b'$. Dan is $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$, dus $v_p(a + b) \geq \alpha = \min$. Is $\alpha < \beta$, dan is het haakje $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$: de waardering is precies $\alpha$.

**4.** De veelvouden van $m$ in $\intint1n$ zijn $m, 2m, \dots, qm$, waarbij $q$ het grootste gehele getal met $qm \leq n$ is, oftewel $q =
\lfloor n/m \rfloor$.

**5.** Wegens de unieke ontbinding is $v_p(n!) = \sum_{j=1}^{n}
v_p(j)$. Tel het anders: elke $j$ draagt $v_p(j) = \#\{k \geq 1 : p^k
\mid j\}$ bij, dus

$$
v_p(n!) = \sum_{j=1}^n \#\{k : p^k \mid j\}
= \sum_{k\geq1} \#\{j \leq n : p^k \mid j\}
= \sum_{k\geq1} \Bigl\lfloor \frac n{p^k} \Bigr\rfloor
$$

wegens vraag 4 — de formule van Legendre. De som is eindig: termen met $p^k > n$ verdwijnen.

**6.** $v_5(1000!) = 200 + 40 + 8 + 1 = 249$ (delingen door $5, 25,
125, 625$); $v_2(1000!) = 500 + 250 + 125 + 62 + 31 + 15 + 7 + 3 + 1 =
994$. Nullen aan het einde van $1000!$: elke nul verbruikt één $2$ en één $5$, dus zijn er $\min(994, 249) = 249$.

**7.** Met $n = \sum_i a_ip^i$ geeft vraag 2 dat $\lfloor n/p^k
\rfloor = \sum_{i \geq k} a_ip^{i-k}$ (knot de ontwikkeling in grondtal $p$ af). Sommeren over $k \geq 1$ en de twee eindige sommen verwisselen geeft

$$
v_p(n!) = \sum_{i\geq1} a_i \sum_{k=1}^{i} p^{i-k}
= \sum_{i\geq0} a_i\,\frac{p^i - 1}{p - 1}
= \frac{n - s_p(n)}{p - 1} .
$$

**8.** Voor $p = 2$ is $v_2(n!) = n - s_2(n)$. Omdat $n \geq 1$ voldoet aan $s_2(n) \geq 1$, is altijd $v_2(n!) \leq n - 1 < n$: $2^n
\nmid n!$. En $v_2(n!) = n - 1$ precies wanneer $s_2(n) = 1$, dat wil zeggen wanneer $n$ een macht van $2$ is.

**9.** $n$ heeft $\lfloor \log_p n \rfloor + 1$ cijfers in grondtal $p$, elk hoogstens $p - 1$, dus $1 \leq s_p(n) \leq
(p-1)\bigl(\log_p(n) + 1\bigr)$. Substitutie in vraag 7 geeft

$$
\frac n{p-1} - \log_p(n) - 1 \;\leq\; v_p(n!) \;<\; \frac n{p-1},
$$

en na deling door $n$: $\frac{v_p(n!)}n \to \frac1{p-1}$.

**10.** $Z(n) - Z(n-1) = v_5(n!/(n-1)!) = v_5(n)$: het aantal nullen springt met $v_5(n)$ bij elk veelvoud van $5$ en is daartussen constant. Er is $Z(24) = \lfloor24/5\rfloor = 4$ en $Z(25) = 5 + 1 = 6$: in $n =
25$ springt het aantal van $4$ meteen naar $6$ ($v_5(25) = 2$), en omdat $Z$ niet-dalend is met $Z \leq 4$ ervoor en $Z \geq 6$ erna, wordt de waarde $5$ nooit bereikt: geen enkele faculteit eindigt op precies vijf nullen.

**11.** Schrijf $x = \lfloor x\rfloor + \{x\}$: dan is $\lfloor x +
y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} +
\{y\}\rfloor$, en $0 \leq \{x\} + \{y\} < 2$ maakt dat laatste geheel deel $0$ of $1$. Vervolgens geeft Legendre, driemaal toegepast,

$$
v_p\binom{m+n}m = v_p\bigl((m{+}n)!\bigr) - v_p(m!) - v_p(n!)
= \sum_{k\geq1}\Bigl(
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{m}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac{n}{p^k}\Bigr\rfloor\Bigr),
$$

een eindige som van nullen en enen (pas de eerste bewering toe op $x =
m/p^k$ en $y = n/p^k$).

**12.** Leg $k \geq 1$ vast en schrijf $m = p^km_1 + m_0$ en $n =
p^kn_1 + n_0$ met $0 \leq m_0, n_0 < p^k$ (euclidische deling: $m_0$ is het getal gevormd door de $k$ laagste cijfers van $m$). Dan is

$$
\Bigl\lfloor\frac{m+n}{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac m{p^k}\Bigr\rfloor
- \Bigl\lfloor\frac n{p^k}\Bigr\rfloor
= \Bigl\lfloor\frac{m_0 + n_0}{p^k}\Bigr\rfloor ,
$$

wat $1$ is als $m_0 + n_0 \geq p^k$ en anders $0$. Maar $m_0 + n_0 \geq
p^k$ zegt precies dat het optellen van de $k$ laagste cijfers van $m$ en $n$ overloopt naar positie $k$ — een overdracht naar positie $k$ in het gewone optelalgoritme. Sommeren over $k$ geeft: $v_p\binom{m+n}m$ is het aantal overdrachten in de optelling $m + n$ in grondtal $p$. (Kummer, 1852.)

**13.** Pas Kummer toe met $m = j$ en $n = p^k - j$, met som $p^k =
(1\underbrace{0\cdots0}_{k})_p$. Zij $a = v_p(j)$, zodat de cijfers van $j$ in grondtal $p$ op de posities $0, \dots, a-1$ nul zijn en het cijfer op positie $a$ niet nul is. De cijfers van $p^k - j$ onder positie $a$ zijn eveneens nul ($p^k - j = p^a(p^{k-a} - j/p^a)$). Op positie $a$ moeten de twee cijfers ongelijk aan nul samen $p$ opleveren (resultaatcijfer $0$): één overdracht; op elke positie $a+1, \dots, k-1$ leveren de cijfers plus de binnenkomende overdracht samen $p$ (opnieuw resultaatcijfer $0$): de overdracht plant zich voort. In totaal $k - a$ overdrachten, dus $v_p\binom{p^k}j = k - v_p(j)$. Voor $k = 1$: $v_p\binom pj = 1$ voor $0 < j < p$, de [deelbaarheid](#def-b1-arith-divides) die in [Stelling 6.23](#thm-b1-arith-fermat) gebruikt werd.

**14.** Met de digitale vorm (vraag 7) en $s_2(2n) = s_2(n)$ (er komt alleen een cijfer nul bij):

$$
v_2\binom{2n}n = \bigl(2n - s_2(2n)\bigr) - 2\bigl(n -
s_2(n)\bigr) = 2s_2(n) - s_2(2n) = s_2(n) \geq 1 :
$$

$\binom{2n}n$ is altijd even, en $v_2 = 1$ (dat wil zeggen $\binom{2n}n
\equiv 2 \pmod 4$) precies wanneer $s_2(n) = 1$, dus wanneer $n$ een macht van $2$ is.

**15.** Vandermonde met $m = n = k = p$: $\binom{2p}p =
\sum_{j=0}^p \binom pj\binom p{p-j} = \sum_{j=0}^p \binom pj^2$. Voor $0
< j < p$ is $p \mid \binom pj$ (vraag 13), dus $\binom pj^2 \equiv 0
\pmod p$; de randtermen geven $1 + 1$: $\binom{2p}p \equiv 2 \pmod p$.

**16.** In grondtal $3$: $500 = 486 + 9 + 3 + 2$, met cijfers (laag naar hoog) $(2, 1, 1, 0, 0, 2)$, dus $s_3(500) = 6$; en $1000 = 729 + 243
+ 27 + 1$, met cijfers $(1, 0, 0, 1, 0, 1, 1)$, dus $s_3(1000) = 4$. *Kummer:* tel $500 + 500$ op in grondtal $3$: positie $0$: $2 + 2 =
4$, cijfer $1$ met overdracht $1$; positie $1$: $1 + 1 + 1 = 3$, cijfer $0$ met overdracht $1$; positie $2$: $1 + 1 + 1 = 3$, cijfer $0$ met overdracht $1$; positie $3$: $0 + 0 + 1 = 1$, geen overdracht; positie $4$: $0$; positie $5$: $2 + 2 = 4$, cijfer $1$ met overdracht $1$; positie $6$: de overdracht landt, cijfer $1$. Vier overdrachten: $v_3\binom{1000}{500} = 4$. *Legendre:* $v_3(1000!) = \frac{1000 -
4}2 = 498$ en $v_3(500!) = \frac{500 - 6}2 = 247$, dus $v_3\binom{1000}{500} = 498 - 2\times247 = 4$. Beide berekeningen komen overeen — en de cijfers $(1, 0, 0, 1, 0, 1, 1)$ van de optelling geven $1000$ terug, zoals het hoort.

**17.** Volgens Kummer ($p = 2$, $m = k$, $n' = n - k$) is $\binom
nk$ oneven precies wanneer de optelling $k + (n - k)$ in grondtal $2$ geen overdracht kent, dat wil zeggen wanneer op elke positie $k_i + (n -
k)_i = n_i$; in dat geval is $k_i \leq n_i$ voor alle $i$. Omgekeerd, is $k_i \leq n_i$ voor alle $i$, dan is het getal met cijfers $n_i - k_i$ gelijk aan $n - k$ en verloopt de optelling zonder overdracht. Hetzelfde bewijs in grondtal $p$: $p \nmid \binom nk$ precies wanneer elk cijfer van $k$ in grondtal $p$ hoogstens gelijk is aan het overeenkomstige cijfer van $n$.

**18.** Tellen we de $k \in \intint0n$ waarvan de cijfers voldoen aan $k_i \leq n_i$: elk cijfer van $k$ wordt onafhankelijk uit $n_i + 1$ waarden gekozen, wat $\prod_i (n_i + 1)$ keuzes geeft; in grondtal $2$ is dat $2^{\#\{i : n_i = 1\}} = 2^{s_2(n)}$. Rij $4 = (100)_2$: $2^1 = 2$ oneven getallen — inderdaad heeft $1, 4, 6, 4, 1$ alleen aan de randen oneven getallen. Rij $5 = (101)_2$: $2^2 = 4$ — inderdaad $1, 5, 10,
10, 5, 1$.

**19.** Alle inwendige getallen even $\iff$ de rij bevat precies $2$ oneven getallen (de twee randen zijn altijd oneven) $\iff 2^{s_2(n)} = 2
\iff s_2(n) = 1 \iff n$ is een macht van $2$.

**20.** In de som van vraag 11 verdwijnt de $k$-de term zodra $p^k >
m + n$ (alle drie de gehele delen zijn dan gelijk; eenvoudiger nog: elke term is dan $0$). Hoogstens $\lfloor \log_p(m+n)\rfloor$ termen zijn dus ongelijk aan nul, elk ter waarde $1$: $a = v_p\binom{m+n}m \leq
\log_p(m+n)$, oftewel $p^a \leq m + n$.

**21.** Voor elk [priemgetal](#def-b1-arith-prime) $p$ is $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) =
\lfloor\log_p(2n)\rfloor$ (de grootste macht van $p$ die $2n$ niet overtreft komt onder $1, \dots, 2n$ voor). Vraag 20 met $m = n$ geeft $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ voor elke $p$: volgens [Propositie 6.16](#prop-b1-arith-valuation) is dus $\binom{2n}n \mid
\operatorname{lcm}(1, \dots, 2n)$. Voor de grootte: de verhouding $\binom{2n}{k+1}/\binom{2n}k = \frac{2n-k}{k+1} \geq 1$ precies voor $k <
n$, zodat het centrale getal het grootste van de $2n + 1$ getallen van rij $2n$ is, waaruit $4^n = \sum_k \binom{2n}k \leq (2n+1)\binom{2n}n$. Samen:

$$
\operatorname{lcm}(1, \dots, 2n) \geq \binom{2n}n \geq
\frac{4^n}{2n + 1} .
$$

Waren er weinig [priemgetallen](#def-b1-arith-prime) onder $2n$, dan kon het kgv niet zo groot zijn: de exponentiële groei van het kgv is een kwantitatief spoor van de overvloed aan [priemgetallen](#def-b1-arith-prime).

**22.** $Z(n) = \sum_k\lfloor n/5^k\rfloor \approx \frac n4$, dus mik je rond $n = 4 \times 2026 = 8104$: $Z(8104) = 1620 + 324 + 64 + 12 +
2 = 2022$. Stap op met veelvouden van $5$: $Z(8110) = 2024$, $Z(8115) =
2025$, en

$$
Z(8120) = 1624 + 324 + 64 + 12 + 2 = 2026 .
$$

Omdat $Z$ tussen veelvouden van $5$ constant is en $Z(8119) = Z(8115) =
2025$, is de kleinste $n$ met minstens $2026$ nullen aan het einde $n =
8120$.

**23.** In grondtal $7$: $50 = 49 + 1$, met cijfers (laag naar hoog) $(1, 0, 1)$. Optellen van $50 + 50$: positie $0$: $1 + 1 = 2 < 7$, geen overdracht; positie $1$: $0 + 0 = 0$; positie $2$: $1 + 1 = 2 < 7$, geen overdracht. Zonder overdrachten, dus volgens Kummer is $v_7\binom{100}{50} = 0$: $7 \nmid \binom{100}{50}$. Legendre bevestigt dat: $v_7(100!) = \lfloor 100/7 \rfloor + \lfloor 100/49 \rfloor = 14 + 2
= 16$ en $v_7(50!) = 7 + 1 = 8$, dus $v_7\binom{100}{50} = 16 - 2\times8
= 0$.

**24.** (i) De unieke [priemontbinding](#thm-b1-arith-fta) ligt onder de definitie van $v_p$ en haar additiviteit, en dus onder de formule van Legendre en elke conclusie over [deelbaarheid](#def-b1-arith-divides) ([Propositie 6.16](#prop-b1-arith-valuation)). (ii) De euclidische deling leverde de afknottingsidentiteit van vraag 2 en de splitsing $m = p^km_1 + m_0$ die de overdracht isoleert (vraag 12). (iii) Tellen: het aantal veelvouden van $m$ (vraag 4), het product van cijferkeuzes (vraag 18) en de afschatting $4^n \leq (2n+1)\binom{2n}n$ voor de rijsom (vraag 21) zijn alle argumenten in de stijl van [Hoofdstuk 2](https://one-course.com/books/math/3/nl/chapter/2-telkunde#ch-b1-counting).

**25.** Legendre zet “welke macht van $p$ [deelt](#def-b1-arith-divides) $n!$” om in rekenen met cijfers in grondtal $p$; Kummer perst het antwoord voor [binomiaalcoëfficiënten](https://one-course.com/books/math/3/nl/chapter/2-telkunde#def-b1-counting-objects) samen tot de overdrachten van één enkele optelling — [deelbaarheid](#def-b1-arith-divides), ogenschijnlijk een globale eigenschap van reusachtige getallen, wordt lokaal afgelezen, cijfer voor cijfer. Vraag 16 is het paradigma: vier overdrachten, met de hand berekend, leggen de exacte macht van $3$ vast in een getal met honderden cijfers. En vraag 21 laat zien hoe dezelfde ideeënkring diep water raakt: een exponentiële ondergrens voor $\operatorname{lcm}(1, \dots, 2n)$ is een eerste, volledig elementaire stap in de richting van de priemgetalstelling, waarvan het bewijs ver buiten dit volume ligt. De hele gereedschapskist — deling, ggd, waarderingen — wordt voor veeltermen overgespeeld in [Hoofdstuk 8](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly), waar de tegenhanger van een cijferontwikkeling de ontwikkeling naar machten van $(X - a)$ is.