- Priemgetallen, op de lijn φ(p) = p − 1
- Andere getallen
- Jouw n
Rekenmachine voor de phi-functie van Euler
Van de getallen 1 tot en met 12 hebben alleen 1, 5, 7 en 11 geen gemeenschappelijke deler met 12, dus φ(12) = 4. De phi-functie van Euler telt deze relatief priemen voor elke n. Voer een getal tot 10^18 in en krijg φ(n) met de priemfactoren en de uitgeschreven productformule, zie de getallen 1 tot en met n met de relatief priemen gemarkeerd, controleer de stelling van Euler, teken φ(k) voor tot 100.000 getallen tegelijk of vind elke n met een gegeven φ(n). Voer een geheel getal n tot 10^18 in, of kies een uitgewerkt voorbeeld. De tegels tonen φ(n), de priemfactoren van n, het aandeel van de getallen 1 tot en met n dat relatief priem is met n en het aantal delers, en de stappen schrijven de productformule uit met jouw getallen. Tot n = 500 worden de getallen 1 tot en met n getekend: de relatief priemen zijn ingekleurd, de andere hebben de kleur van het kleinste priemgetal dat ze met n gemeen hebben. Wijs een getal aan om zijn ggd met n te zien, en klik erop om het als a in de stelling van Euler te gebruiken. Grafiek toont φ(k) voor elke k tot een grens; klik op een punt om dat getal te openen. Inverse geeft elke n met φ(n) = m; klik op een ervan om het te openen.
Hoe het werkt
- Voer een geheel getal n tot 10^18 in, of kies een uitgewerkt voorbeeld zoals φ(60), een RSA-modulus of het Carmichaelgetal 561.
- Lees φ(n), de priemfactoren en de productformule met jouw getallen af. Wijs tot 500 de getallen 1 tot en met n aan om hun ggd met n te zien, en klik er een aan om er de stelling van Euler mee te controleren.
- Ga naar Grafiek om φ(k) voor elke k tot 100.000 te zien, of naar Inverse om elke n met φ(n) = m op te sommen.
Hoe φ(n) berekend wordt
Ontbind n in priemfactoren en vermenigvuldig n met (1 − 1/p) voor elk priemgetal p dat n deelt. Voor 60 = 2² × 3 × 5 geeft dat 60 × 1/2 × 2/3 × 4/5 = 16. Wegstrepen geeft hetzelfde aantal: van de 60 getallen zijn er 30 even; van de 30 oneven zijn er 10 veelvouden van 3; van de 20 die overblijven zijn er 4 veelvouden van 5, en er blijven er 16 over. Per priemmacht luidt de formule φ(p^k) = p^(k−1)(p − 1), en de waarden worden vermenigvuldigd: φ(60) = 2 × 2 × 4. Het moeilijke deel is het ontbinden. De rekenmachine gebruikt proefdelingen, een Miller-Rabin-priemtest en de rho-methode van Pollard, zodat zelfs een product van 18 cijfers van twee priemgetallen van 9 cijfers maar een fractie van een seconde kost.
Waar de phi-functie gebruikt wordt
φ(n) telt de breuken k/n tussen 0 en 1 die al onvereenvoudigbaar zijn, de stapgroottes waarmee een wijzer op een klok met n uren elk uur aandoet (1, 5, 7 en 11 op een klok van 12 uur), en de getallen die een inverse modulo n hebben. Euler bewees dat a^φ(n) ≡ 1 (mod n) voor elke a die relatief priem is met n, en RSA-versleuteling berust daarop: met n = 3233 = 61 × 53 is φ(n) = 60 × 52 = 3.120, en de publieke exponent 17 heeft de privépartner 2.753, omdat 17 × 2.753 = 15 × 3.120 + 1.
Veelgestelde vragen
Wat is de phi-functie van Euler?
φ(n) is het aantal gehele getallen van 1 tot en met n dat geen gemeenschappelijke deler met n heeft behalve 1. φ(9) = 6, omdat 1, 2, 4, 5, 7 en 8 relatief priem zijn met 9, terwijl 3, 6 en 9 de factor 3 delen. Volgens afspraak is φ(1) = 1. Euler bestudeerde de functie in de jaren 1760; Gauss gaf haar in 1801 het symbool φ, en James Joseph Sylvester in 1879 de Engelse naam totient.
Wat is φ van een priemgetal?
p − 1, omdat elk getal van 1 tot en met p − 1 relatief priem is met een priemgetal p, dus φ(97) = 96. Voor een priemmacht geldt φ(p^k) = p^k − p^(k−1), omdat alleen de veelvouden van p een deler met haar gemeen hebben: φ(81) = 81 − 27 = 54.
Wat zegt de stelling van Euler?
Als a en n relatief priem zijn, dan laat a^φ(n) bij deling door n rest 1. Voor n = 60 en a = 7: φ(60) = 16, en 7^16 ≡ 1 (mod 60). De kleine stelling van Fermat is het geval van een priemgetal n. Vaak werkt een kleinere exponent al: 7^4 = 2.401 = 40 × 60 + 1. De kleinste exponent die werkt voor elke a die relatief priem is met n, is de Carmichael-functie λ(n), die voor 60 gelijk is aan 4.
Kunnen twee getallen dezelfde phi-waarde hebben?
Ja, en meestal zijn het er meerdere: φ(n) = 24 voor n = 35, 39, 45, 52, 56, 70, 72, 78, 84 en 90. Sommige even getallen zijn nooit een waarde van φ, 14 is de kleinste, en geen enkel oneven getal boven 1 is er een, omdat φ(n) even is vanaf n = 3. Robert Carmichael beweerde in 1907 dat geen enkele waarde precies één keer voorkomt. Dat is nog altijd niet bewezen, en Kevin Ford liet in 1998 zien dat een uitzondering groter dan 10^(10^10) zou moeten zijn.
Hoe groot mag het getal zijn?
Elk geheel getal tot 10^18. De rekenmachine ontbindt het met exacte gehele rekenkunde in je browser, zodat φ(10^18) = 4 × 10^17 en φ(999.999.866.000.004.473) = 999.999.864.000.004.608 tot op het laatste cijfer kloppen. De getallen 1 tot en met n worden getekend tot 500, de grafiek gaat tot 100.000 en de inverse werkt voor waarden tot 10^10.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor