aantal priemfactoren, aritmetische functie, totientfunctie

© h.hofstede (h.hofstede@hogeland.nl)

Een arithmetische functie is een functie die "iets" telt van een natuurlijk getal. Dat "iets" kan van alles zijn. Het domein is dus ℕ, het bereik kan alles zijn. Hier volgen een paar beroemde voorbeelden van arithmetische functies.

Het aantal priemfactoren n_p(n).

Voor het aantal priemfactoren van priemgetal p in de ontbinding van het getal n verzinnen we de notatie n_p(n).
Dus bijvoorbeeld n₃(45) = 2 want 45 = 3² • 5 en dat zijn twee factoren 3.

Dan geldt:
n_p(GGD(x, y)) = min(n_p(x), n_p(y))
n_p(KGV(x, y)) = max(n_p(x), n_p(y))

Dat kunnen we gebruiken om een aantal stellingen over GGD en KGV te bewijzen.

Stelling:
Er geldt: GGD(KGV(a, b) , KGV(a, c)) = KGV(a, GGD(b, c))

Bewijs.

Bekijk eerst één priemgetal p en stel dat n_p(a) = x en n_p(b) = y en n_p(c) = z. Dus dat dat priemgetal x keer in a voorkomt en y keer in b.
Dan is n_p(KGV(a, b)) = max(x, y) en n_p(KGV(a, c)) = max(x, z)
Dan is n_p(GGD(KGV(a, b) , KGV(a, c)) = min(max(x, y), max(x, z))
En aan de rechterkant staat dan max(x, min(y, z))
Dus moeten we aantonen dat: min(max(x, y), max(x, z)) = max(x, min(y, z))

Stel dat y ≤ z. Dat mag je rustig stellen want de stelling is symmetrisch in y en z dus je kiest gewoon voor y degene met het kleinst aantal priemfactoren p.
Dan is min(y, z) = y en dus staat aan de rechterkant max(x, y)

Bekijk nu de linkerkant.
Omdat y ≤ z kan max(x, y) nooit groter zijn dan max(x, z), dus de kleinste van de twee is max(x, y)

Dus priemgetal p komt even vaak voor aan beide kanten.
Dus elk priemgetal komt even vaak voor.

q.e.d.

N.B. Voor het totaal aantal priemfactoren van een getal wordt meestal de notatie Ω(n) gebruikt. Daarbij gaat het dus niet om verschillende priemfactoren, maar gewoon om hoeveel priemfactoren er zijn.
Dus bijvoorbeeld Ω(24) = 4 want 24 = 2 • 2 • 2 • 3 en dat zijn er vier.
Voor het aantal verschillende priemfactoren wordt dan meestal de kleine letter ω(n) gebruikt. Dus ω(24) = 2.

Postulaat van Bertrand.

Voor elk natuurlijk getal n > 1 bestaat er een priemgetal p met n < p < 2n

De wiskundige Paul Erdös gaf daarvan een mooi bewijs, ongeveer als volgt.

Hij bewees eerst voor de binomiaalcoëfficiënt (2n nCr n) de volgende ongelijkheid:

Erdös toonde vervolgens aan dat, als er GEEN priemgetal tussen n en 2n zou liggen, dat dan vanaf bepaalde n zou gelden dat :

En dat kan natuurlijk niet beiden gelden, dus moest er vanaf bepaalde n wel steeds een priemgetal tussen n en 2n liggen. Hij hoefde vervolgens alleen nog een aantal kleine waarden van n met de hand te controleren dat daar ook steeds zo'n priemgetal was.
Het precieze bewijs van Erdös is trouwens nog best ingewikkeld. Dat kun je hier vinden.

Het aantal delers t(n).

We definiëren de functie t(n) als het aantal positieve delers van n.
Die kunnen we makkelijk met de priemfactorontbinding berekenen.
Stelling:

t(n) = (n_p1(n) + 1) • (n_p2(n) + 1) • (n_p3(n) + 1) ......

Daarbij zijn p₁, p₂, p₃, ... alle priemgetallen uit de priemfactorontbinding van n.

Bewijs.

Als je een willekeurige deler van het getal p₁^a • p₂^b • p₃^c • .... wilt maken dan mag je van elke p_i een willekeurig aantal kiezen. Omdat je er ook nul kunt kiezen heb je voor p₁ de keuze uit (a + 1) mogelijkheden, voor p₂ de mogelijkheid van (b + 1) mogelijkheden, enz.
Samen geeft dat (a + 1)(b + 1) ....en dat is de gevraagde formule.

N.B. van elke p_i er nul kiezen is eigenlijk een mogelijkheid die niet mag, dus het aantal delers zou 1 minder moeten zijn, maar het getal 1 als deler zijn we vergeten (1 is geen priemgetal): die moet er nog weer bij, zodat de formule toch klopt.

q.e.d.

Voorbeeld: het getal 45000 = 2³ • 3² • 5⁴ heeft dus 4 • 3 • 5 = 60 delers.

De som van de delers s(n).

Als een getal n te schrijven is als n = p₁ⁿ¹ • p₂ⁿ² • p₃ⁿ³• .... dan geldt voor de som s(n) van de delers van n:

s(n) = (1 + p₁ + p₁² + ... + p₁ⁿ1) • (1 + p₂ + p₂² + ... + p₂ⁿ2) • (1 + p₃ + p₃² + ... + p₃ⁿ3) • ....

Dat is natuurlijk vrij snel in te zien.
Schrijf n als (p₁p₁p₁...) • (p₂p₂p₂...) • (p₃p₃p₃...) • ....
Om een willekeurige deler te maken neem je uit het eerste groepje 0 tm a getallen p₁, uit het tweede groepje 0 tm b getallen p₂, uit het derde groepje 0 tm c getallen p₃, enz.
En dan moet je al die mogelijke combinaties bij elkaar optellen.
Al die mogelijke combinaties krijg je ook als je de haakjes in de uitdrukking van s(n) zou wegwerken.

De totiëntfunctie j(n).

j(n) is het aantal getallen uit {1, 2, ..., n} dat relatief priem is met n

Oh ja, twee getallen heten relatief priem als ze geen priemfactor hetzelfde hebben.
Dit wordt ook wel copriem genoemd
Natuurlijk is er ook voor j(n) een directe formule. Stel dat n = p₁ⁿ¹ • p₂ⁿ² • p₃ⁿ³• ....., dan geldt:

j(n) = n • (1 - ¹/_p1)• (1 - ¹/_p2) • ...

Dat deze formule wel zo'n beetje moet kloppen kun je misschien als volgt begrijpen.
Neem priemfactor 5, dan heeft 1 van elke 5 getallen die als priemfactor (dat zijn namelijk alle getallen uit de tafel van 5). Dus 4 van de 5 hebben NIET 5 als priemfactor. Dus de kans dat een willekeurig getal 5 NIET als priemfactor heeft is ⁴/₅.
En op dezelfde manier is de kans dat een willekeurig getal 7 NIET als priemfactor heeft ⁶/₇, en voor 11 is dat ¹⁰/₁₁, enz.
Dus de kans dat een willekeurig getal 5 en 7 en 11 allemaal NIET als priemfactor heeft is ⁴/₅ • ⁶/₇ • ¹⁰/₁₁.
Dat rijtje staat precies in bovenstaande formule.

Voor het exactere bewijs daarvan heb je het principe van inclusie/exclusie nodig. Dat staat in deze les uitgelegd, en aan het eind van die les wordt de formule voor j(n) afgeleid.

Voorbeeld: 300 = 2² • 3 • 5² dus j(300) = 300 • (¹/₂) • (²/₃) • (⁴/₅) = 80
(klopt: het zijn 1 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 113 119 121 127 131 133 137 139 143 149 151 157 161 163 167 169 173 179 181 187 191 193 197 199 203 209 211 217 221 223 227 229 233 239 241 247 251 253 257 259 263 269 271 277 281 283 287 289 293 299 en dat zijn er precies 80).

Multiplicatief.

Een functie f heet multiplicatief als geldt
1. f(ab) = f(a) • f(b) voor alle coprieme a en b
2. f(1) ≠ 0

Dat betekent dat, zodra we f(n) kennen voor alle machten van priemgetallen, f volledig bekend is.
De eerder genoemde functies t, s en j zijn multiplicatief.
In de volgende lessen zullen we vaak gebruik maken van het multiplicatief zijn van functies. Vooral omdat daaruit volgt dat je het gelijk zijn van multiplicatieve functies dus kunt aantonen door te laten zien dat ze voor de machten van priemgetallen gelijk zijn.

Een functie heet trouwens volledig multiplicatief als de voorwaarde van het copriem zijn er niet bij hoeft, dus als de eigenschap voor alle a en b geldt.


OPGAVEN

1.	Er geldt: KGV(GGD(a, b), GGD(a, c)) = GGD(a, KGV(b, c)). Bewijs deze stelling.

2.	Vind alle natuurlijke getallen waarvoor n! een kwadraat is.

3.	Stelling van Greenfield en Greenfield: De verzameling {1, 2, ..., 2k - 1, 2k} kan altijd worden opgedeeld in k paren waarvan de som telkens een priemgetal is. Toon dat aan met behulp van het postulaat van Bertrand. Gebruik volledige inductie.

4.	Toon aan dat de som van de positieve delers van n alleen maar een even getal is als n een kwadraat is.

5.	Toon aan dat j(n) even is voor n > 2.