Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

6Getaltheorie in ℤ

De getaltheorie — de studie van de deelbaarheid in $\Z$ — werd in het bovenbouwvolume aangevat. Dit hoofdstuk bouwt haar volledig opnieuw op vanaf de euclidische deling, met volledige bewijzen: grootste gemene deler en het algoritme van Euclides, de identiteit van Bézout en het lemma van Gauss, de priemontbinding, en het rekenen met congruenties tot en met de kleine stelling van Fermat. Naast haar eigen bekoring is deze stof het model dat Hoofdstuk 8 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 $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$ ; bestaan van de ggd)

Elke deelgroep van $(\Z, +)$ is van de vorm $n\Z = \{nk : k \in \Z\}$ voor een unieke $n \in \N$ .
Voor $a, b \in \Z$ die niet beide nul zijn, is de verzameling $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 $a$ en $b$ , en elke gemene deler van $a$ en $b$ deelt $d$ .

Bewijs. (1) Zij $H \subseteq \Z$ een deelgroep (niet-leeg, stabiel onder aftrekken; de formele definitie staat in Hoofdstuk 7, 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); 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 $d$ ze beide. En deelt $c$ zowel $a$ als $b$ , dan deelt $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 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. ∎

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$ .

(Lemma van Gauss) Is $a \mid bc$ en $\gcd(a, b) = 1$ , dan $a \mid c$ .
Is $a \mid c$ , $b \mid c$ en $\gcd(a,b) = 1$ , dan $ab \mid c$ .
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 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 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 $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, 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, 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) 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 $\leq \sqrt n$ . Om na te gaan of $n$ priem is volstaat het dus de priemgetallen tot $\sqrt n$ te proberen. Voor $n = 271$ : $\sqrt{271} < 17$ , en $271$ is door geen van $2, 3, 5, 7, 11, 13$ deelbaar (oneven, cijfersom $10$ , eindigt niet op $0$ of $5$ , en $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$ ): priem, 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 gegroeid zijn.

Stelling 6.14 (Euclides)

Er zijn oneindig veel priemgetallen.

Bewijs. Elk geheel getal $n \geq 2$ heeft een priemdeler: zijn kleinste deler $\geq 2$ is priem (een echte ontbinding daarvan zou een kleinere deler van $n$ opleveren). Stel nu dat $p_1, \dots, p_k$ alle priemgetallen waren, en zet $N = p_1 p_2 \cdots p_k + 1 \geq 2$ . Een zeker priemgetal $p_i$ deelt $N$ ; maar $p_i$ deelt 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, 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): $n = 2$ is priem; voor $n > 2$ is $n$ ofwel priem, 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 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 is groter dan $1$ ). Voor $r \geq 1$ : het priemgetal $p_1$ deelt $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. Maar $q_j$ is priem 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. ∎

Propositie 6.16 (Waarderingen)

Schrijf voor $p$ priem 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 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 is precies de uitspraak 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 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). 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: controles met congruenties weerleggen, ze bewijzen niet.

Propositie 6.20 (Inverteerbaarheid modulo $n$ )

$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.

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). Uniciteit: is $ab \equiv ab' \equiv 1$ , dan is $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

Voorbeeld 6.21 ( $7$ inverteren modulo $26$ )

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 $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 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 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 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. 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 $\binom pk = \frac{p!}{k!(p-k)!}$ deelbaar is door $p$ : immers $k!\,(p-k)!\, \binom pk = p!$ , en $p$ deelt $p!$ maar is relatief priem 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). ∎

Voorbeeld 6.24 (De omkering van Fermat faalt: $341$ )

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 is met $n$ , dan is $n$ niet priem. 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 uit Opmerking 6.27 waarborgt. Moraal: een implicatie en haar omkering leiden gescheiden levens (Opmerking 1.10), 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)

Een congruentie 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 ook de modulus: $ac \equiv bc \pmod n \iff a \equiv b \pmod{n/\gcd(c,n)}$ .
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 met een van beide factoren): $6 \mid 4 \times 9$ , en toch deelt $6$ geen van beide factoren.
Relatief priem is een relatie, geen eigenschap. “ $8$ en $9$ zijn relatief priem” is waar hoewel geen van beide priem is; “twee aan twee relatief priem” is sterker dan “in hun geheel relatief priem” ( $\gcd(6, 10, 15) = 1$ , terwijl geen enkel paar relatief priem is).
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.

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, 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 wordt de ring $\Z/n\Z$ in Hoofdstuk 7, waarvan de inverteerbare elementen (Propositie 6.20) 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. 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 daar waarborgen.

Opmerking 6.28 (Tussenspel: $\Z$ 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 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, 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, waar vragen over inverteerbaarheid (de Propositie 6.20 van dit hoofdstuk) structurele uitspraken 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. — 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, en geef er een paar van Bézout bij.

Oplossing

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

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

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

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 en $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Oplossing

Oplossing van Oefening 6.5.

Voor elk priemgetal $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 zijn gelijk (Propositie 6.16), 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

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); 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 $p$ , met waarderingen: vergelijk $v_p$ van beide leden van $p q^2 = r^2$ .

Oplossing

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 $m, n$ het paar congruenties $x \equiv a \ (m)$ , $x \equiv b\ (n)$ altijd een oplossing heeft, uniek modulo $mn$ .

Oplossing

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 (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).

Oplossing

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) 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.

Oplossing

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 $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 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. 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, dan is $(n-1)! \not\equiv -1 \pmod n$ .

Oplossing

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). 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$ .

Bewijs dat $F_0 F_1 \cdots F_{n-1} = F_n - 2$ voor $n \geq 1$ (inductie).
Leid af dat de getallen van Fermat twee aan twee relatief priem zijn.
Leid daaruit een tweede bewijs af, onafhankelijk van Stelling 6.14, dat er oneindig veel priemgetallen zijn.

Oplossing

Oplossing van Oefening 6.12.

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 .$
Zij $m < n$ en $d = \gcd(F_m, F_n)$ . Volgens (1) deelt $F_m$ het getal $F_n - 2$ , dus deelt $d$ zowel $F_n$ als $F_n - 2$ en dus ook $2$ . Maar elk getal van Fermat is oneven, dus $d = 1$ .
Elke $F_n \geq 3$ heeft een priemdeler $p_n$ (de eerste stap van Stelling 6.14). Is $m \neq n$ , dan is $p_m \neq p_n$ , want een gemeenschappelijk priemgetal zou $\gcd(F_m, F_n) = 1$ delen. De afbeelding $n \mapsto p_n$ is dus injectief van $\N$ in de priemgetallen: er zijn oneindig veel priemgetallen.

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 $p$ die $1000!$ deelt, of die een binomiaalcoëfficiënt deelt? 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, 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.

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$ .
Bewijs dat voor $x \in \R$ en $n \in \N^*$ geldt $\bigl\lfloor \lfloor x \rfloor / n \bigr\rfloor = \lfloor x/n \rfloor$ .
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)$ .
Toon aan dat het aantal veelvouden van $m$ in $\intint1n$ gelijk is aan $\lfloor n/m \rfloor$ .
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 zijn: elke draagt precies één eenheid bij per niveau dat ze haalt.

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

Bereken $v_5(1000!)$ en $v_2(1000!)$ en besluit: op hoeveel nullen eindigt $1000!$ ?
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} .$
Twee gevolgen voor $p = 2$ : toon aan dat $2^n$ het getal $n!$ nooit deelt, en dat $2^{n-1}$ het getal $n!$ precies dan deelt wanneer $n$ een macht van $2$ is.
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.
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.

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.
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$ .)
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, teruggevonden.)
Bewijs dat $v_2\binom{2n}n = s_2(n)$ . Leid af dat de centrale binomiaalcoëfficiënt altijd even is, en dat $\binom{2n}n \equiv 2 \pmod 4$ precies wanneer $n$ een macht van $2$ is.
Toon met de identiteit van Vandermonde (Oefening 2.7) en vraag 13 aan dat $\binom{2p}p \equiv 2 \pmod p$ voor elk priemgetal $p$ .
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.

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$ .
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$ .
Leid af dat alle inwendige getallen $\binom nk$ ( $0 < k < n$ ) even zijn dan en slechts dan als $n$ een macht van $2$ is.
Bewijs dat elke priemmacht die $\binom{m+n}m$ deelt 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?)
Leid af dat $\binom{2n}n$ het getal $\operatorname{lcm}(1, 2, \dots, 2n)$ deelt, 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.

Deel V — Synthese.

Bepaal de kleinste $n$ waarvoor $n!$ op minstens $2026$ nullen eindigt. (Schat $Z(n) \approx n/4$ en corrigeer met de exacte formule.)
Nog een laatste kruiscontrole: toon aan dat $7$ het getal $\binom{100}{50}$ niet deelt, 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.
Waar precies gebruikte de opgave: (i) de unieke priemontbinding; (ii) de ontbinding $n = p^k n_1 + n_0$ uit de euclidische deling; (iii) een telargument uit Hoofdstuk 2? Eén zin per onderdeel.
Synthese, in een korte alinea: de formule van Legendre zet een vraag over deelbaarheid 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 suggereert (de volledige uitspraak, de priemgetalstelling, ligt ver buiten dit volume; de tegenhanger van de gereedschapskist van dit hoofdstuk voor veeltermen is Hoofdstuk 8).

Oplossing

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 die in Stelling 6.23 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 $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 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 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.

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 ligt onder de definitie van $v_p$ en haar additiviteit, en dus onder de formule van Legendre en elke conclusie over deelbaarheid (Propositie 6.16). (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.

25. Legendre zet “welke macht van $p$ deelt $n!$ ” om in rekenen met cijfers in grondtal $p$ ; Kummer perst het antwoord voor binomiaalcoëfficiënten samen tot de overdrachten van één enkele optelling — deelbaarheid, 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, waar de tegenhanger van een cijferontwikkeling de ontwikkeling naar machten van $(X - a)$ is.