De phi-functie van Euler uitgelegd
Schrijf de getallen 1 tot en met 10 op en streep elk getal weg dat een deler met 10 gemeen heeft. Er blijven er vier over: 1, 3, 7 en 9. Dat aantal, φ(10) = 4, is de phi-functie van Euler, een van de meest gebruikte functies uit de getaltheorie, van breuken en klokken tot de versleuteling die online betalingen beschermt.
Relatief priemen tellen
Twee getallen zijn relatief priem als hun grootste gemene deler 1 is. φ(n) telt de k van 1 tot en met n met ggd(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 en φ(1) = 1. Hetzelfde aantal duikt op veel plaatsen op. Het is het aantal breuken k/n tussen 0 en 1 dat al onvereenvoudigbaar is, het aantal stapgroottes waarmee een wijzer op een klok met n uren elk uur aandoet, en het aantal k met een inverse modulo n, zodat k × x ≡ 1 (mod n) op te lossen is.
De productformule
Als de priemgetallen die n delen p₁, p₂ … zijn, dan is φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. De reden is een zeef. De helft van alle getallen is even, dus het wegstrepen van de veelvouden van 2 laat de fractie 1 − 1/2 over; van de overgebleven getallen is een op de drie een veelvoud van 3, enzovoort. Volgens de Chinese reststelling zijn de voorwaarden voor verschillende priemgetallen onafhankelijk, dus de fracties worden gewoon vermenigvuldigd. Voor 100 = 2² × 5² geeft dat 100 × 1/2 × 4/5 = 40. Twee eigenschappen geven hetzelfde resultaat in een andere vorm: φ(p^k) = p^(k−1)(p − 1), en φ(mn) = φ(m) φ(n) als m en n relatief priem zijn, dus φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
De stelling van Euler
Fermat merkte in 1640 op dat a^(p−1) ≡ 1 (mod p) voor een priemgetal p en elke a die niet deelbaar is door p. Euler bewees de algemene versie, gepubliceerd in 1763: a^φ(n) ≡ 1 (mod n) zodra ggd(a, n) = 1. Het bewijs is kort. Vermenigvuldig de φ(n) getallen die relatief priem zijn met n met a; de producten zijn weer relatief priem met n en allemaal verschillend modulo n, dus het zijn dezelfde getallen in een andere volgorde, en wie de twee producten vergelijkt, houdt a^φ(n) ≡ 1 over. De kleinste exponent die voor een gegeven a werkt, is zijn orde, die altijd een deler van φ(n) is; de kleinste die voor alle a tegelijk werkt, is de Carmichael-functie λ(n). Voor 561 = 3 × 11 × 17 deelt λ(561) = 80 het getal 560, dus a^560 ≡ 1 (mod 561) voor elke a die relatief priem is met 561, hoewel 561 geen priemgetal is. Het is het kleinste Carmichaelgetal, en de reden waarom de test van Fermat alleen niet kan bewijzen dat een getal priem is.
De delersom van Gauss en het gemiddelde
Tel φ(d) op over de delers d van n en je krijgt altijd n terug: voor 12 is φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss bewees dit in zijn Disquisitiones Arithmeticae van 1801; je ziet het door de breuken 1/12, 2/12 … 12/12 te vereenvoudigen en naar hun noemer te sorteren. Gemiddeld is φ(k) ongeveer 0,61 k: het gemiddelde van φ(k)/k nadert 6/π² ≈ 0,6079, wat ook de kans is dat twee willekeurige gehele getallen relatief priem zijn, en φ(1) + … + φ(N) ligt dicht bij 3N²/π². Voor N = 1.000 is de som 304.192, tegenover 3N²/π² ≈ 303.964.
Waarden die nooit voorkomen
φ(n) is even voor elke n vanaf 3, omdat de getallen die relatief priem zijn met n in paren k en n − k voorkomen. Ook is niet elk even getal een waarde: 14, 26, 34, 38 en 50 zijn de eerste die nooit voorkomen, terwijl 24 de waarde is van tien verschillende getallen, van 35 tot 90. Ze vinden is een eindige zoektocht, want voor elk priemgetal p dat n deelt, moet p − 1 een deler van φ(n) zijn. In 1907 beweerde Robert Carmichael dat geen enkele waarde precies één keer voorkomt. Zijn bewijs was fout, de bewering is nog open, en elke uitzondering zou groter dan 10^(10^10) moeten zijn. D. H. Lehmer vroeg in 1932 of φ(n) een deler van n − 1 kan zijn voor een samengesteld n; er is geen voorbeeld bekend.
De phi-functie in RSA
RSA kiest twee grote priemgetallen p en q en publiceert n = pq en een exponent e. Omdat φ(n) = (p − 1)(q − 1), kan wie n kan ontbinden φ(n) berekenen, en daaruit de privé-exponent d met e × d ≡ 1 (mod φ(n)); de stelling van Euler zorgt er dan voor dat (m^e)^d ≡ m (mod n). In het schoolvoorbeeld n = 3233 = 61 × 53 is φ(n) = 3.120, e = 17 en d = 2.753. Veel implementaties gebruiken in plaats daarvan λ(n) = kgv(p − 1, q − 1), hier 780, wat de kleinere d = 413 oplevert. φ(n) berekenen voor een RSA-modulus van 600 cijfers is net zo moeilijk als hem ontbinden: uit n en φ(n) volgen de twee priemgetallen met één vierkantswortel.
Zelf ontdekken
Open de rekenmachine en voer een willekeurige n tot 10^18 in om φ(n) met de priemfactoren en de formule te zien. Tot 500 worden de getallen 1 tot en met n getekend, de relatief priemen ingekleurd en de andere in de kleur van het kleinste priemgetal dat ze met n gemeen hebben, zodat de productformule een zeef wordt die je kunt natellen. Kies een getal a om de stelling van Euler te controleren, ga naar Grafiek om φ(k) tot 100.000 te zien met de priemgetallen op de lijn φ(p) = p − 1, of naar Inverse om elke n met φ(n) = m te vinden.
Veelgestelde vragen
Waarom is φ(1) = 1?
Omdat ggd(1, 1) = 1: het enige getal van 1 tot en met 1 is relatief priem met 1. De afspraak houdt ook de formules geldig, bijvoorbeeld de som van Gauss over de delers van n, die voor n = 1 gewoon φ(1) = 1 is.
Is φ hetzelfde als de priemgetal-telfunctie?
Nee. π(n) telt de priemgetallen tot en met n, φ(n) de getallen tot en met n die relatief priem zijn met n. φ(10) = 4 telt 1, 3, 7 en 9, terwijl π(10) = 4 de getallen 2, 3, 5 en 7 telt. Dat ze hier gelijk zijn, is toeval: φ(12) = 4, maar π(12) = 5.
Hoe snel kan φ(n) berekend worden?
Zo snel als n ontbonden kan worden. Met bekende priemfactoren zijn het een paar vermenigvuldigingen; zonder is er geen snelle methode bekend, en daar berust RSA op. Voor getallen tot 10^18 kost het ontbinden in een browser milliseconden, voor getallen met honderden cijfers kan het jaren duren.
Welke getallen hebben de kleinste φ(n) in verhouding tot n?
Getallen met veel kleine priemfactoren. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… hangt alleen af van welke priemgetallen n delen, niet van hun machten: voor elke macht van 2 is het precies 1/2, en voor 30 = 2 × 3 × 5 is het 8/30, ongeveer 27 %. Het product van de eerste 15 priemgetallen, 614.889.782.588.491.410, heeft φ(n)/n ≈ 14 %, de laagste waarde van alle getallen tot 10^18.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Open de rekenmachine