Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

6Getaltheorie in de gehele getallen

Getaltheorie — de studie van deelbaarheid in $\Z$ — werd begonnen in het Middelbaar-onderwijsvolume. 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, priemontbinding, en de rekenkunde van congruenties tot en met de kleine stelling van Fermat. Naast haar eigen bekoring is dit materiaal het model dat Hoofdstuk 8 nabootst voor veeltermen.

6.1 Deelbaarheid en euclidische deling

Definitie 6.1 (Deelbaarheid)

Voor $a, b \in \Z$ deelt $b$ het getal $a$ (genoteerd $b \mid a$ ) wanneer $a = bq$ voor een zekere $q \in \Z$ . Basisgevolgen: 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 $a \mid b$ samen met $b \mid a$ dwingen $b = \pm a$ af.

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. Als $r \geq b$ , dan zou $r - b = a - b(q+1)$ een kleiner element van $A$ zijn: tegenspraak. Dus $0 \leq r < b$ .

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

Voorbeeld 6.3 (Positionele getalnotatie door herhaalde deling)

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 de resten van laatste naar eerste: $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 geheel getal in $\intint06$ congruent met de huidige waarde mod $7$ , dus de schrijfwijze in grondtal $7$ is uniek — het feit dat stilzwijgend gebruikt wordt telkens wanneer het weekendprobleem “de cijfers van $n$ in grondtal $p$ ” manipuleert.

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$ niet beide nul 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^*$ . Deze $d$ is de grootste gemene deler $\gcd(a, b)$ : ze 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 aftrekking; de formele definitie staat in Hoofdstuk 7, en enkel deze twee eigenschappen worden gebruikt). Als $H = \{0\}$ , neem $n = 0$ . Anders bevat $H$ een niet-nul element en zijn tegengestelde, dus een kleinste strikt positief element $n$ . Dan $n\Z \subseteq H$ . Voor $x \in H$ , schrijf $x = nq + r$ met $0 \leq r < n$ (Stelling 6.2); $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 aftrekking, dus het is $d\Z$ met $d \geq 1$ (het bevat $a$ of $b$ niet-nul). Aangezien $a, b \in d\Z$ , deelt $d$ beide. En als $c$ zowel $a$ als $b$ deelt, dan deelt $c$ elke $au + bv$ — in het bijzonder $c \mid d$ , aangezien $d \in a\Z + b\Z$ . Dit 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$ niet beide nul bestaan er $u, v \in \Z$ met

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

In het bijzonder ( $\gcd(a,b) = 1$ , het relatief priem geval): $a$ en $b$ zijn relatief priem als en slechts als $au + bv = 1$ een oplossing heeft.

Bewijs. $\gcd(a,b) = d \in d\Z = a\Z + b\Z$ . Voor de equivalentie: als $\gcd(a,b) = 1$ , levert Bézout de oplossing; omgekeerd dwingt $au + bv = 1$ elke gemene deler van $a, b$ af om $1$ te delen. ∎

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, aangezien $r = a - bq$ ); herhaal totdat de rest $0$ is; de laatste niet-nul rest is de ggd. Door de delingen achterwaarts te doorlopen (of de coëfficiënten bij te houden op de weg naar beneden) verkrijg je een Bézout-paar $(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$ . Achterwaarts:

\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$ , $9 \times 120 = 1080$ .

Stelling 6.8 (Lemma van Gauss en gevolgen)

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

(Lemma van Gauss) Als $a \mid bc$ en $\gcd(a, b) = 1$ , dan $a \mid c$ .
Als $a \mid c$ , $b \mid c$ en $\gcd(a,b) = 1$ , dan $ab \mid c$ .
Als $\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) $b \mid q$ , dus $ab \mid aq = c$ .

(3) $au + bv = 1$ en $au' + cv' = 1$ . Vermenigvuldig de twee betrekkingen:

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

een Bézout-betrekking tussen $a$ en $bc$ : volgens Gevolg 6.5 is $\gcd(a, bc) = 1$ . ∎

Voorbeeld 6.9 (Een lineaire diophantische vergelijking oplossen)

Vind alle $(x, y) \in \Z^2$ met $6x + 10y = 4$ . Eerst de bestaanstoets: $\gcd(6, 10) = 2$ deelt $4$ , dus er bestaan oplossingen (als de ggd het rechterlid niet zou delen, zou het linkerlid altijd een veelvoud ervan zijn en zouden er geen zijn). Deel door: $3x + 5y = 2$ . Een particuliere oplossing is zichtbaar: $(x_0, y_0) = (-1, 1)$ . Voor de algemene, trek 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$ , en dan $x = -1 + 5k$ . Omgekeerd werkt elk zulk paar:

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

Het patroon is algemeen: één particuliere oplossing plus de gehele veelvouden van $\bigl(\frac b{\gcd}, -\frac a{\gcd}\bigr)$ — dezelfde “particulier plus homogeen”-structuur 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^*$ ,

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

Voorbeeld 6.11 (Uitlijningsproblemen zijn kgv-problemen)

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

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

tanden — dat wil zeggen $3$ omwentelingen van het grote tandwiel en $7$ van het kleine ( $252/84$ en $252/36$ ). Merk de praktische weg op: bereken eerst de ggd (Euclides: $84 = 2\times36 + 12$ , $36 = 3\times12$ ), en deel dan — bouw het kgv nooit op door veelvouden op te sommen. Elke periodiek-samenvallingsvraag (tandwielen, planetaire uitlijningen, samenvallende repeterende decimalen) herleidt zich tot deze ene berekening.

6.3 Priemgetallen

Definitie 6.12

Een geheel getal $p \geq 2$ is priem wanneer zijn enige positieve delers $1$ en $p$ zijn. Voor $p$ priem en $a \in \Z$ : ofwel $p \mid a$ , ofwel $\gcd(p, a) = 1$ . Bijgevolg (Stelling 6.8) geldt Euclides’ lemma: als $p \mid ab$ dan $p \mid a$ of $p \mid b$ .

Opmerking 6.13 (Priemtoets door proefdeling)

Als $n = ab$ met $2 \leq a \leq b$ , dan $a^2 \leq ab = n$ , dus $a \leq \sqrt n$ : een samengesteld getal $n$ heeft altijd een priemdeler $\leq \sqrt n$ . Om te toetsen 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$ , $271 = 7\cdot38 + 5 = 11\cdot24 + 7 = 13\cdot20 + 11$ ): priem, na zes delingen in plaats van tweehonderd. De $\sqrt n$ -barrière is een echte drempel: die efficiënt overschrijden voor honderdcijferige getallen vereist de moderne priemtoetsen die zijn voortgekomen uit Stelling 6.23.

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 ervan zou een kleinere deler van $n$ opleveren). Veronderstel nu dat $p_1, \dots, p_k$ alle priemgetallen waren, en zij $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$ — absurd. ∎

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 door sterke inductie (Stelling 1.12): $n = 2$ is priem; voor $n > 2$ is ofwel $n$ priem, ofwel $n = ab$ met $2 \leq a, b < n$ , en de inductiehypothese ontbindt $a$ en $b$ .

Uniciteit. Veronderstel $p_1 \cdots p_r = q_1 \cdots q_s$ (priemgetallen opgesomd met herhaling, zeg $r \leq s$ ), en pas inductie toe op $r$ . Als $r = 0$ 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 Euclides’ lemma ofwel $p_1 \mid q_1$ ofwel $p_1 \mid q_2\cdots q_s$ ; door herhaling deelt $p_1$ een zekere $q_j$ . Maar $q_j$ is priem en $p_1 \geq 2$ : noodzakelijk $p_1 = q_j$ . Schrap deze gemene factor (geoorloofd: $\Z$ is een integriteitsdomein) om

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

te verkrijgen (de hoed markeert weglating), een gelijkheid van kortere producten; de inductiehypothese zegt dat de twee lijsten $p_2, \dots, p_r$ en $q_1, \dots, \widehat{q_j}, \dots, q_s$ op volgorde na samenvallen, en dus deden de oorspronkelijke dat ook. De exponentvorm groepeert gelijke priemgetallen. ∎

Propositie 6.16 (Valuaties)

Voor $p$ priem en $n \in \N^*$ , schrijf $v_p(n)$ voor de exponent van $p$ in de ontbinding van $n$ (met $v_p(n) = 0$ als $p \nmid n$ ). Dan

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. Als $m \mid n$ , schrijf $n = mq$ en pas ze toe. Omgekeerd, als alle $v_p(m) \leq v_p(n)$ , voldoet het geheel getal $q = \prod_p p^{\,v_p(n) - v_p(m)}$ aan $mq = n$ . De ggd-formule: het geheel 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 derdemachten via valuaties)

Een geheel getal $n \geq 1$ is een volkomen kwadraat als en slechts als elke $v_p(n)$ even is (als $n = m^2$ , dan $v_p(n) = 2v_p(m)$ ; omgekeerd halveer elke exponent). Evenzo voor derdemachten met veelvouden van $3$ . Zo is $21168 = 2^4 \times 3^3 \times 7^2$ geen kwadraat ( $v_3 = 3$ is oneven) en geen derdemacht ( $v_2 = 4$ ); het kleinste positieve geheel getal $m$ zodanig dat $21168\,m$ wel een derdemacht is, wordt gevonden door elke exponent aan te vullen tot het volgende veelvoud van $3$ :

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, derdemachten, delers, ggd, kgv) worden coördinaatsgewijze vragen over de exponentvectoren $(v_2, v_3, v_5, \dots)$ — unieke ontbinding is de uitspraak dat deze coördinaten bestaan en goed gedefinieerd zijn.

6.4 Congruenties

Definitie 6.18

Voor $n \in \N^*$ : $a \equiv b \pmod n$ wanneer $n \mid a - b$ . Dit is een equivalentierelatie verenigbaar met optelling en vermenigvuldiging: als $a \equiv b$ en $a' \equiv b'$ (mod $n$ ), dan $a + a' \equiv b + b'$ , $aa' \equiv bb'$ , en $a^k \equiv b^k$ voor $k \in \N$ .

Voorbeeld 6.19 (De negenproef)

Verenigbaarheid met $+$ en $\times$ is een controlemiddel zo oud als de handel. Aangezien $10 \equiv 1 \pmod 9$ , is elk geheel getal congruent mod $9$ met zijn cijfersom (bewezen als Oefening 6.2). Om de bewering $1234 \times 567 = 699\,678$ te controleren: cijfersommen geven $1234 \equiv 1$ en $567 \equiv 18 \equiv 0 \pmod 9$ , dus het product moet $\equiv 1 \times 0 = 0$ zijn; en inderdaad $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ . De controle slaagt (en het product is in feite correct). Had iemand $699\,478$ gerapporteerd, dan zou de cijfersom $43 \equiv 7 \not\equiv 0$ hem onmiddellijk ontmaskeren. De toets is eenzijdig — hij vangt een fout op tenzij de fout zelf een veelvoud van $9$ is — wat precies de pseudopriemles is van Voorbeeld 6.24 in het klein: congruentiecontroles weerleggen, ze certificeren niet.

Propositie 6.20 (Inverteerbaarheid mod $n$ )

$a$ is inverteerbaar mod $n$ (d.w.z. $ab \equiv 1 \pmod n$ voor een zekere $b$ ) als en slechts als $\gcd(a, n) = 1$ . De inverse is dan uniek mod $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 Bézout- betrekking, die bestaat asa $\gcd(a,n) = 1$ (Gevolg 6.5). Uniciteit: als $ab \equiv ab' \equiv 1$ , dan $b \equiv b(ab') = (ab)b' \equiv b' \pmod n$ . ∎

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

Aangezien $\gcd(7, 26) = 1$ is de klasse van $7$ inverteerbaar mod $26$ . Uitgebreide Euclides:

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

en dan achterwaarts:

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 .

Dus $7 \times (-11) \equiv 1 \pmod{26}$ , d.w.z. $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; controle: $7 \times 15 = 105 = 4 \times 26 + 1$ . Met de inverse in de hand wordt elke congruentie $7x \equiv c \pmod{26}$ opgelost in één vermenigvuldiging: $x \equiv 15c$ . Deze mechanische inversie is het werkpaard van de modulaire rekenkunde — en van de publieke-sleutelprotocollen vermeld in Opmerking 6.27, waar de moduli honderden cijfers hebben maar het algoritme precies 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 mod $20$ — maar de vergelijking is nog steeds oplosbaar. De congruentie zegt $20 \mid 12x - 8$ ; door de hele betrekking door $4$ te delen (deler van alle drie de ingrediënten), is ze equivalent met $5 \mid 3x - 2$ , d.w.z.

3x \equiv 2 \pmod 5 .

Nu is $\gcd(3, 5) = 1$ en $3^{-1} \equiv 2 \pmod 5$ ( $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 mod $20$ , overeenstemmend met de ggd. (Was het rechterlid niet deelbaar door $4$ , zeg $12x \equiv 6 \pmod{20}$ , dan zou er helemaal geen oplossing zijn: het linkerlid is altijd $\equiv 0 \pmod 4$ .) Algemene vorm: $ax \equiv b \pmod n$ is oplosbaar asa $\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$ :

a^p \equiv a \pmod p,

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

Bewijs. Eerst, voor $1 \leq k \leq p - 1$ , is de binomiaalcoëfficiënt $\binom pk = \frac{p!}{k!(p-k)!}$ deelbaar door $p$ : inderdaad $k!\,(p-k)!\, \binom pk = p!$ en $p$ deelt $p!$ maar is relatief priem met $k!(p-k)!$ (alle factoren zijn $< p$ ), dus het lemma van Gauss geeft $p \mid \binom pk$ .

Bewijs nu $a^p \equiv a$ voor $a \in \N$ door inductie. Waar voor $a = 0$ . Als $a^p \equiv a$ , dan volgens het binomium van Newton

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

waarbij alle middelste termen verdwijnen mod $p$ . Voor $a < 0$ , pas het resultaat toe op $-a$ en scheid $p = 2$ (waar $x \equiv -x$ ) van oneven $p$ (waar $(-a)^p = -a^p$ ). Ten slotte, als $p \nmid a$ , vermenigvuldig $a^p \equiv a$ met een inverse van $a$ mod $p$ (Propositie 6.20). ∎

Voorbeeld 6.24 (Fermats omkering faalt: $341$ )

De kleine stelling van Fermat geeft een goedkope samengesteldheidstoets: als $a^{n-1} \not\equiv 1 \pmod n$ voor een zekere $a$ relatief priem met $n$ , dan is $n$ niet priem. Zou de toets ook priemheid kunnen certificeren? Nee: neem $n = 341 = 11 \times 31$ , samengesteld, en $a = 2$ . Aangezien $2^{10} = 1024 = 3 \times 341 + 1$ ,

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 Fermats toets voor het grondtal $2$ (het is het kleinste zulke pseudopriemgetal). Het grondtal $3$ ontmaskert het ( $3^{340} \not\equiv 1$ ), en praktische priemtoetsing draait de toets daarom op verscheidene grondtallen, plus verfijningen — de industriële versies van dit idee zijn wat de grote priemgetallen van Opmerking 6.27 certificeert. Moraal: een implicatie en haar omkering leiden een gescheiden leven (Opmerking 1.10), zelfs voor stellingen.

Voorbeeld 6.25 (Praktische congruentieberekeningen)

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

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

De rest is $4$ . De strategie: herleid de exponent modulo de orde geleverd door Fermat, en herleid dan tussentijdse machten bij elke stap.

Opmerking 6.26 (Veelvoorkomende valkuilen in de getaltheorie)

Een congruentie delen. Uit $ac \equiv bc \pmod n$ mag men niet besluiten $a \equiv b$ tenzij $\gcd(c, n) = 1$ : $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)}$ .
Euclides’ lemma verkeerd gebruiken. $a \mid bc$ impliceert $a \mid b$ of $a \mid c$ enkel voor $a$ priem (of relatief priem met één factor): $6 \mid 4 \times 9$ maar $6$ deelt 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; “paarsgewijs relatief priem” is sterker dan “globaal relatief priem” ( $\gcd(6, 10, 15) = 1$ maar geen enkel paar is relatief priem).
Exponenten leven niet mod $n$ . In $a^k \bmod n$ mag de exponent enkel herleid worden modulo de orde van $a$ (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 herleiding die werkt is die welke Voorbeeld 6.25 uitvoert.

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 herhaald voor veeltermen in Hoofdstuk 8, waar “graad” de rol van absolute waarde speelt; de twee hoofdstukken naast elkaar vergelijken is de beste manier om beide te begrijpen. De congruentierekening wordt de ring $\Z/n\Z$ in Hoofdstuk 7, wier inverteerbare elementen (Propositie 6.20) het eerste niet-triviale voorbeeld vormen van een groep van eenheden. Valuaties keren terug in het weekendprobleem hieronder (de formule van Legendre) en voeden de irrationaliteitsbewijzen van Hoofdstuk 10. Buiten dit volume is Bézout-inversie mod $n$ de motor van de publieke-sleutelcryptografie, en de kleine stelling van Fermat is de grootvader van de priemtoetsen die de grote priemgetallen certificeren die daar gebruikt worden.

Opmerking 6.28 (Intermezzo: $\Z$ als sjabloon)

Doe een stap terug van de individuele stellingen en observeer de architectuur van het hoofdstuk: één gereedschap (euclidische deling) bracht een classificatie voort (deelgroepen $n\Z$ ), die een bestaansstelling voortbracht (ggd, Bézout), die een deelbaarheidsrekening voortbracht (Gauss), die unieke ontbinding voortbracht — elke verdieping rust enkel op de verdieping eronder. Hetzelfde gebouw zal nog tweemaal opgetrokken worden in dit volume met verschillende benedenverdiepingen: in Hoofdstuk 8, waar deling door graad de deling door grootte vervangt en alles daarboven zich letterlijk herhaalt; en, in het klein, binnen elke $\Z/n\Z$ van Hoofdstuk 7, waar inverteerbaarheidsvragen (het 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 voorproef van de kerngewoonte van de algebra: stellingen bewijzen over axioma’s in plaats van over objecten.

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

6.5 Oefeningen

Oefening 6.1 ★

Bereken $\gcd(1\,001, 777)$ met het algoritme van Euclides, en een Bézout- paar ervoor.

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

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$ . Bézout-paar: $(u, v) = (-52, 67)$ voor $1001u + 777v = 7$ .

Oefening 6.2 ★

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

Oplossing

Oplossing van Oefening 6.2.

Aangezien $10 \equiv 1 \pmod 9$ : $10^k \equiv 1$ , dus $\sum_k d_k 10^k \equiv \sum_k d_k \pmod 9$ . Aangezien $10 \equiv -1 \pmod{11}$ : $10^k \equiv (-1)^k$ , dus het geheel getal is congruent met de alternerende som $\sum_k (-1)^k d_k$ mod $11$ (te beginnen bij het eenhedencijfer 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}$ (uitgebreide 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$ . Achterwaarts:

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 ★

Vind alle paren $(x, y) \in \Z^2$ met $17x + 39y = 1$ ; en dan 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 achterwaarts

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$ (aangezien $17 \mid 39y$ en $\gcd(17,39) = 1$ afdwingen $17 \mid y$ — lemma van Gauss). Bijgevolg

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

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

Oefening 6.5 ★★

Bewijs dat voor $a, b \in \N^*$ : $\gcd(a,b) \times \operatorname{lcm}(a,b) = ab$ . (Gebruik de valuatieformules van Propositie 6.16 en $\min(\alpha,\beta) + \max(\alpha,\beta) = \alpha + \beta$ .)

Oplossing

Oplossing van Oefening 6.5.

Voor elk priemgetal $p$ , 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 valuatie bij elk priemgetal zijn gelijk (Propositie 6.16), dus $\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 delertellingsformule $\prod_i (\alpha_i + 1)$ .)

Oplossing

Oplossing van Oefening 6.6.

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

Delertelling: 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 behulp van valuaties: vergelijk $v_p$ van beide leden van $p q^2 = r^2$ .

Oplossing

Oplossing van Oefening 6.7.

Veronderstel $\sqrt p = \frac rq$ met $r, q \in \N^*$ , d.w.z. $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. Een geheel getal kan niet tegelijk een oneven en een even $p$ -valuatie hebben: tegenspraak. Dus $\sqrt p \notin \Q$ .

Oefening 6.8 ★★

(Chinees restprobleem) Vind 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 mod $mn$ .

Oplossing

Oplossing van Oefening 6.8.

Algemeen feit. Met $\gcd(m,n) = 1$ geeft Bézout $mu + nv = 1$ . Stel $x_0 = b\,mu + a\,nv$ . Dan $x_0 \equiv a\,nv \equiv a(1 - mu) \equiv a \pmod m$ en analoog $x_0 \equiv b \pmod n$ : bestaan. Als $x$ en $x'$ twee oplossingen zijn, delen $m$ en $n$ het getal $x - x'$ , dus $mn \mid x - x'$ (Stelling 6.8 (2)): uniciteit mod $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$ ; $16 = 11 + 5 \equiv 5 \pmod{11}$ . Oplossingen: $x \equiv 16 \pmod{77}$ .

Oefening 6.9 ★★

Bereken $3^{1000}$ mod $7$ , en de laatste twee decimale cijfers van $7^{100}$ (mod $100 = 4 \times 25$ : gebruik Oefening 6.8).

Oplossing

Oplossing van Oefening 6.9.

Mod $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 mod $4$ en mod $25$ . Mod $4$ : $7 \equiv -1$ , dus $7^{100} \equiv 1$ . Mod $25$ : $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), $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$ . Hint: toon eerst dat de rest van $2^m - 1$ mod $2^n - 1$ gelijk is aan $2^r - 1$ waarbij $r$ de rest is van $m$ mod $n$ ; volg dan het algoritme van Euclides.

Oplossing

Oplossing van Oefening 6.10.

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

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 mod $2^n - 1$ , $\;2^m - 1 \equiv 2^r - 1$ , en aangezien $0 \leq 2^r - 1 < 2^n - 1$ , is dit de euclidische rest.

Bijgevolg weerspiegelt het algoritme van Euclides op het paar $(2^m - 1, 2^n - 1)$ , exponent na exponent, het algoritme op $(m, n)$ : elke delingsstap vervangt $(m, n)$ door $(n, r)$ boven en $(2^m - 1, 2^n - 1)$ door $(2^n - 1, 2^r - 1)$ beneden. Het algoritme boven eindigt bij $\gcd(m,n)$ , dus beneden eindigt het bij $2^{\gcd(m,n)} - 1$ .

Oefening 6.11 ★★★

(Stelling van Wilson) Zij $p$ een priemgetal. Bewijs dat

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

door elke factor van $(p-1)!$ te koppelen aan zijn inverse mod $p$ en de zelfgekoppelde factoren te identificeren (los eerst $x^2 \equiv 1 \pmod p$ op). Controleer de omkering: als $n \geq 2$ niet priem is, dan $(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 Euclides’ lemma $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 mod $p$ , en zijn inverse $a^{-1}$ is opnieuw een van de factoren (Propositie 6.20). Koppel elke $a$ aan $a^{-1}$ : de paren vermenigvuldigen tot $1$ , behalve dat de zelfgekoppelde factoren ( $a = a^{-1}$ , d.w.z. $a^2 \equiv 1$ ) alleen staan — en dit zijn precies $1$ en $p - 1$ . Bijgevolg

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

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

Omkering. Zij $n \geq 2$ samengesteld, $n = ab$ met $1 < a \leq b < n$ . Als $a < b$ , verschijnen beide als verschillende factoren van $(n-1)!$ , dus $n \mid (n-1)!$ en $(n-1)! \equiv 0 \not\equiv -1$ . Als $a = b$ (d.w.z. $n = a^2$ ): voor $a \geq 3$ zijn zowel $a$ als $2a$ $< n$ , dus $n = a^2 \mid a \times 2a \mid (n-1)!$ , dezelfde conclusie; voor $n = 4$ , $(n-1)! = 6 \equiv 2 \not\equiv -1 \pmod 4$ .

Oefening 6.12 ★★★

(Fermat-getallen) Voor $n \in \N$ , zij $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 Fermat-getallen paarsgewijs relatief priem zijn.
Leid 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$ . Aannemend $F_0\cdots F_{n-1} = F_n - 2$ :

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

6.6 Probleem: 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 $n!$ 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 gedaante $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$ . Dit probleem bewijst beide, controleert ze numeriek tegen elkaar, en oogst de klassieke gevolgen — eindnullen, de pariteit van de driehoek van Pascal, en een eerste afschatting in de richting van de priemgetalstelling. Overal is $p$ een priemgetal, $\floor{x}$ het gehele deel, en $s_p(n)$ duidt de som aan van de cijfers van $n$ geschreven in grondtal $p$ .

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

Opwarmer: bereken $10!$ en lees zijn aantal eindnullen af; 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^*$ , $\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 telkens wanneer $v_p(a) \neq v_p(b)$ .
Toon 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^*$ ,

$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 deelbaar zijn door $p^k$ : elke draagt precies één eenheid bij per niveau dat ze bereikt.

Deel II — De digitale vorm en de eindnullen.

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 $n = \sum_i a_i p^i$ in grondtal $p$ ,

$v_p(n!) = \frac{n - s_p(n)}{p - 1} .$
Twee gevolgen voor $p = 2$ : toon dat $2^n$ nooit $n!$ deelt, en dat $2^{n-1}$ $n!$ precies dan deelt wanneer $n$ een macht van $2$ is.
Schat het tekort af: toon $\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 komt een aandeel $\frac1{p-1}$ van één factor $p$ per eenheid bij.
Zij $Z(n) = v_5(n!)$ het aantal eindnullen van $n!$ . Toon $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 eindigt op precies vijf nullen.

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 van termen elk gelijk aan $0$ of $1$ .
Bewijs de stelling van Kummer: de $k$ -de term van die som is gelijk aan $1$ precies wanneer de optelling van $m$ en $n$ in grondtal $p$ een overdracht naar positie $k$ voortbrengt; dus is $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 inspecteer $\lfloor (m_0 + n_0)/p^k \rfloor$ .)
Leid af dat voor $0 < j < p^k$ :

$v_p\binom{p^k}{j} = k - v_p(j) ,$

door de overdrachten te tellen in de optelling $j + (p^k - j)$ . (In het bijzonder $p \mid \binom p j$ voor $0 < j < p$ : de sleutelstap van Stelling 6.23, herwonnen.)
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, dat $\binom{2p}p \equiv 2 \pmod p$ voor elk priemgetal $p$ .
Bereken $v_3\binom{1000}{500}$ tweemaal: eenmaal via Kummer (schrijf $500$ in grondtal $3$ en tel de overdrachten in $500 + 500$ ), eenmaal via de digitale vorm van Legendre (bereken $s_3(500)$ en $s_3(1000)$ ); controleer dat beide dezelfde waarde geven.

Deel IV — De pariteit van de driehoek van Pascal, en een priemdichtheidsafschatting.

Bewijs het cijfercriterium: $\binom nk$ is oneven als en slechts als elk binair cijfer van $k$ ten hoogste het overeenkomstige cijfer van $n$ is. 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 elementen bevat; verifieer op rijen $4$ en $5$ .
Leid af dat alle inwendige elementen $\binom nk$ ( $0 < k < n$ ) even zijn als en slechts als $n$ een macht van $2$ is.
Bewijs dat elke priemmacht die $\binom{m+n}m$ deelt ten hoogste $m + n$ is: als $p^a \mid \binom{m+n}m$ dan $p^a \leq m + n$ . (Hoeveel niet-nul termen kan de som van vraag 11 hebben?)
Leid af dat $\binom{2n}n$ het getal $\operatorname{lcm}(1, 2, \dots, 2n)$ deelt, en combineer met de ondergrens $\binom{2n}n \geq \frac{4^n}{2n+1}$ (die je zult bewijzen: het centrale element is het grootste van de $2n + 1$ elementen 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 glimp van de overvloed aan priemgetallen.

Deel V — Synthese.

Vind de kleinste $n$ zodanig dat $n!$ eindigt op ten minste $2026$ nullen. (Schat $Z(n) \approx n/4$ , en stel dan bij met behulp van de exacte formule.)
Een laatste kruiscontrole: toon dat $7$ het getal $\binom{100}{50}$ niet deelt, eerst door $50$ in grondtal $7$ te schrijven en te controleren dat de optelling $50 + 50$ overdrachtvrij is, en dan door $v_7(100!)$ en $v_7(50!)$ met de formule van Legendre te berekenen.
Waar precies gebruikte het probleem: (i) unieke ontbinding; (ii) de euclidische-delingsontbinding $n = p^k n_1 + n_0$ ; (iii) een telargument uit Hoofdstuk 2? Eén zin voor elk.
Synthese, in een korte paragraaf: de formule van Legendre zet een deelbaarheidsvraag om in cijferrekening, en de stelling van Kummer leest het antwoord af van de overdrachten van één optelling — becommentarieer deze vertaling, de controles van vraag 16, en wat de afschatting van vraag 21 suggereert over priemgetallen (de volledige uitspraak, de priemgetalstelling, ligt ver buiten dit volume; het polynomiale analogon van de gereedschapskist van dit hoofdstuk is Hoofdstuk 8).

Oplossing

Oplossing van Probleem 6.1.

1. $10! = 3\,628\,800$ : twee eindnullen. Valuaties factor na factor: machten van $2$ komen van $2, 4 = 2^2, 6, 8 = 2^3, 10$ , in totaal $v_2(10!) = 1 + 2 + 1 + 3 + 1 = 8$ ; machten van $5$ van $5$ en $10$ : $v_5(10!) = 2$ . Eindnullen $= \min(v_2, v_5) = 2$ , consistent.

2. Schrijf de euclidische deling $\lfloor x\rfloor = nq + r$ , $0 \leq r \leq n - 1$ . Dan $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 indien nodig) en schrijf $a = p^\alpha a'$ , $b = p^\beta b'$ met $p \nmid a', b'$ . Dan $a + b = p^\alpha\bigl(a' + p^{\beta - \alpha}b'\bigr)$ , dus $v_p(a + b) \geq \alpha = \min$ . Als $\alpha < \beta$ , is de haakjesuitdrukking $a' + p^{\beta-\alpha}b' \equiv a' \not\equiv 0 \pmod p$ : de valuatie is precies $\alpha$ .

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

5. Volgens de unieke ontbinding, $v_p(n!) = \sum_{j=1}^{n} v_p(j)$ . Tel 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

volgens 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$ . Eindnullen van $1000!$ : elke nul verbruikt één $2$ en één $5$ , dus zijn er $\min(994, 249) = 249$ ervan.

7. Met $n = \sum_i a_ip^i$ geeft vraag 2 $\lfloor n/p^k \rfloor = \sum_{i \geq k} a_ip^{i-k}$ (kap de $p$ -adische ontwikkeling af). Sommeer over $k \geq 1$ en verwissel de twee eindige sommen:

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$ : $v_2(n!) = n - s_2(n)$ . Aangezien $n \geq 1$ $s_2(n) \geq 1$ heeft, altijd $v_2(n!) \leq n - 1 < n$ : $2^n \nmid n!$ . En $v_2(n!) = n - 1$ asa $s_2(n) = 1$ asa $n$ een macht van $2$ is.

9. $n$ heeft $\lfloor \log_p n \rfloor + 1$ cijfers in grondtal $p$ , elk ten hoogste $p - 1$ , dus $1 \leq s_p(n) \leq (p-1)\bigl(\log_p(n) + 1\bigr)$ . Substitueer in vraag 7:

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

en deel 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)$ : de telling van eindnullen springt met $v_5(n)$ bij elk veelvoud van $5$ en is constant daartussen. $Z(24) = \lfloor24/5\rfloor = 4$ en $Z(25) = 5 + 1 = 6$ : bij $n = 25$ springt de telling van $4$ rechtstreeks naar $6$ ( $v_5(25) = 2$ ), en aangezien $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\}$ : $\lfloor x + y\rfloor = \lfloor x\rfloor + \lfloor y\rfloor + \lfloor \{x\} + \{y\}\rfloor$ , en $0 \leq \{x\} + \{y\} < 2$ maakt het laatste gehele deel $0$ of $1$ . Dan, door Legendre driemaal toe te passen,

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 $0$ ’en en $1$ ’en (pas de eerste bewering toe op $x = m/p^k$ , $y = n/p^k$ ).

12. Fixeer $k \geq 1$ en schrijf $m = p^km_1 + m_0$ , $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$ lage cijfers van $m$ ). Dan

\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 $0$ anders. Maar $m_0 + n_0 \geq p^k$ zegt precies dat het optellen van de $k$ lage cijfers van $m$ en $n$ overloopt naar positie $k$ — een overdracht naar positie $k$ in het schoolboek-optelalgoritme. Sommeer over $k$ : $v_p\binom{m+n}m$ is het aantal overdrachten in de optelling $m + n$ in grondtal $p$ . (Kummer, 1852.)

13. Pas Kummer toe op $m = j$ , $n = p^k - j$ , som $p^k = (1\underbrace{0\cdots0}_{k})_p$ . Zij $a = v_p(j)$ , zodat de cijfers van $j$ in grondtal $p$ op posities $0, \dots, a-1$ gelijk zijn aan $0$ en het cijfer op positie $a$ niet-nul is. De cijfers van $p^k - j$ onder positie $a$ zijn ook $0$ ( $p^k - j = p^a(p^{k-a} - j/p^a)$ ). Op positie $a$ moeten de twee niet-nul cijfers optellen tot $p$ (resultaatcijfer $0$ ): één overdracht; op elke positie $a+1, \dots, k-1$ tellen cijfers plus de inkomende overdracht op tot $p$ (opnieuw resultaatcijfer $0$ ): de overdracht plant zich voort. 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 gebruikt in Stelling 6.23.

14. Volgens de digitale vorm (vraag 7), met $s_2(2n) = s_2(n)$ (een nulcijfer aanhangen):

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$ (d.w.z. $\binom{2n}n \equiv 2 \pmod 4$ ) precies wanneer $s_2(n) = 1$ , d.w.z. 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$ , $p \mid \binom pj$ (vraag 13), dus $\binom pj^2 \equiv 0 \pmod p$ ; de eindtermen geven $1 + 1$ : $\binom{2p}p \equiv 2 \pmod p$ .

16. Grondtal $3$ : $500 = 486 + 9 + 3 + 2$ , cijfers (laag naar hoog) $(2, 1, 1, 0, 0, 2)$ , dus $s_3(500) = 6$ ; en $1000 = 729 + 243 + 27 + 1$ , 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$ overdracht $1$ ; positie $1$ : $1 + 1 + 1 = 3$ , cijfer $0$ overdracht $1$ ; positie $2$ : $1 + 1 + 1 = 3$ , cijfer $0$ overdracht $1$ ; positie $3$ : $0 + 0 + 1 = 1$ , geen overdracht; positie $4$ : $0$ ; positie $5$ : $2 + 2 = 4$ , cijfer $1$ overdracht $1$ ; positie $6$ : 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$ . De twee berekeningen stemmen overeen — en de optelcijfers $(1, 0, 0, 1, 0, 1, 1)$ reproduceren $1000$ , zoals ze moeten.

17. Volgens Kummer ( $p = 2$ , $m = k$ , $n' = n - k$ ): $\binom nk$ is oneven asa de optelling $k + (n - k)$ in grondtal $2$ geen overdracht heeft, asa op elke positie de cijfers voldoen aan $k_i + (n - k)_i = n_i$ ; in dat geval $k_i \leq n_i$ voor alle $i$ . Omgekeerd, als $k_i \leq n_i$ voor alle $i$ , dan is het getal met cijfers $n_i - k_i$ gelijk aan $n - k$ en is de optelling overdrachtvrij. Hetzelfde bewijs in grondtal $p$ : $p \nmid \binom nk$ asa elk cijfer van $k$ in grondtal $p$ ten hoogste het overeenkomstige cijfer van $n$ is.

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

19. Alle inwendige elementen even $\iff$ de rij heeft precies $2$ oneven elementen (de twee uiteinden 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, en inderdaad is de eerste $0$ wanneer $p^k > m+n$ ; nog eenvoudiger, elke term is $0$ ). Bijgevolg zijn ten hoogste $\lfloor \log_p(m+n)\rfloor$ termen niet-nul, elk gelijk aan $1$ : $a = v_p\binom{m+n}m \leq \log_p(m+n)$ , d.w.z. $p^a \leq m + n$ .

21. Voor elk priemgetal $p$ , $v_p\bigl(\operatorname{lcm}(1, \dots, 2n)\bigr) = \lfloor\log_p(2n)\rfloor$ (de grootste macht van $p$ die $2n$ niet overschrijdt verschijnt onder $1, \dots, 2n$ ). Vraag 20 met $m = n$ geeft $v_p\binom{2n}n \leq \lfloor\log_p(2n)\rfloor$ voor elke $p$ : volgens Propositie 6.16, $\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$ , dus is het centrale element het grootste van de $2n + 1$ elementen van rij $2n$ , waaruit $4^n = \sum_k \binom{2n}k \leq (2n+1)\binom{2n}n$ . Combineren:

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

Waren er weinig priemgetallen onder $2n$ , dan zou het kgv niet zo groot kunnen zijn: 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 bij $n = 4 \times 2026 = 8104$ : $Z(8104) = 1620 + 324 + 64 + 12 + 2 = 2022$ . Ga omhoog met veelvouden van $5$ : $Z(8110) = 2024$ , $Z(8115) = 2025$ , en

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

Aangezien $Z$ constant is tussen veelvouden van $5$ en $Z(8119) = Z(8115) = 2025$ , is de kleinste $n$ met ten minste $2026$ eindnullen $n = 8120$ .

23. Grondtal $7$ : $50 = 49 + 1$ , cijfers (laag naar hoog) $(1, 0, 1)$ . Tel $50 + 50$ op: positie $0$ : $1 + 1 = 2 < 7$ , geen overdracht; positie $1$ : $0 + 0 = 0$ ; positie $2$ : $1 + 1 = 2 < 7$ , geen overdracht. Overdrachtvrij, dus volgens Kummer $v_7\binom{100}{50} = 0$ : $7 \nmid \binom{100}{50}$ . Legendre stemt overeen: $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) Unieke ontbinding ligt aan de basis van de definitie zelf van $v_p$ en zijn additiviteit, en dus van de formule van Legendre en elke deelbaarheidsconclusie (Propositie 6.16). (ii) Euclidische deling bracht de afkappingsidentiteit van vraag 2 voort en de splitsing $m = p^km_1 + m_0$ die de overdracht isoleert (vraag 12). (iii) Tellen: de telling van veelvouden van $m$ (vraag 4), het cijferkeuzeproduct (vraag 18), en de rijsomgrens $4^n \leq (2n+1)\binom{2n}n$ (vraag 21) zijn allemaal argumenten in de stijl van Hoofdstuk 2.

25. Legendre zet “welke macht van $p$ deelt $n!$ ” om in cijferrekening in grondtal $p$ ; Kummer comprimeert het antwoord voor binomiaalcoëfficiënten tot de overdrachten van één enkele optelling — deelbaarheid, ogenschijnlijk een globale eigenschap van enorme getallen, wordt lokaal afgelezen, cijfer na cijfer. Vraag 16 is het paradigma: vier overdrachten, met de hand berekend, bepalen de exacte macht van $3$ in een getal met honderden cijfers. En vraag 21 toont hoe dezelfde kring van ideeën diepe wateren beroert: een exponentiële ondergrens voor $\operatorname{lcm}(1, \dots, 2n)$ is een eerste, volledig elementaire stap naar de priemgetalstelling, wier bewijs ver buiten dit volume ligt. De hele gereedschapskist — deling, ggd, valuaties — wordt herhaald voor veeltermen in Hoofdstuk 8, waar het analogon van een cijferontwikkeling ontwikkeling in machten van $(X - a)$ is.