- Primtal, på linjen φ(p) = p − 1
- Övriga tal
- Ditt n
Räknare för Eulers fi-funktion
Av talen 1 till 12 har bara 1, 5, 7 och 11 ingen gemensam delare med 12, så φ(12) = 4. Eulers fi-funktion räknar dessa relativt prima tal för varje n. Ange ett tal upp till 10^18 för att få φ(n) med primfaktorerna och produktformeln utskriven, se talen 1 till n med de relativt prima markerade, kontrollera Eulers sats, rita φ(k) för upp till 100 000 tal på en gång eller hitta varje n med ett givet φ(n). Ange ett heltal n upp till 10^18 eller välj ett genomräknat exempel. Rutorna visar φ(n), primfaktorerna i n, andelen av talen 1 till n som är relativt prima med n och antalet delare, och stegen skriver ut produktformeln med dina tal. Upp till n = 500 ritas talen 1 till n: de relativt prima är ifyllda, de övriga har färgen för det minsta primtal de har gemensamt med n. Peka på ett tal för att se dess sgd med n, och klicka på det för att använda det som a i Eulers sats. Diagram visar φ(k) för varje k upp till en gräns; klicka på en punkt för att öppna det talet. Invers listar varje n med φ(n) = m; klicka på ett för att öppna det.
Hur det fungerar
- Ange ett heltal n upp till 10^18, eller välj ett genomräknat exempel som φ(60), en RSA-modul eller Carmichaeltalet 561.
- Läs av φ(n), primfaktorerna och produktformeln med dina tal. Upp till 500 kan du peka på talen 1 till n för att se deras sgd med n och klicka på ett av dem för att kontrollera Eulers sats med det.
- Byt till Diagram för att se φ(k) för varje k upp till 100 000, eller till Invers för att lista varje n med φ(n) = m.
Så beräknas φ(n)
Faktorisera n i primtal och multiplicera n med (1 − 1/p) för varje primtal p som delar n. För 60 = 2² × 3 × 5 ger det 60 × 1/2 × 2/3 × 4/5 = 16. Att stryka ger samma antal: av de 60 talen är 30 jämna; av de 30 udda är 10 multipler av 3; av de 20 som är kvar är 4 multipler av 5, och då återstår 16. För en primtalspotens är formeln φ(p^k) = p^(k−1)(p − 1), och värdena multipliceras: φ(60) = 2 × 2 × 4. Det svåra är faktoriseringen. Räknaren använder provdivision, ett Miller–Rabin-primtalstest och Pollards rho-metod, så även en 18-siffrig produkt av två 9-siffriga primtal tar en bråkdel av en sekund.
Var fi-funktionen används
φ(n) räknar de bråk k/n mellan 0 och 1 som redan är förkortade, de steglängder som för en visare förbi varje timme på en klocka med n timmar (1, 5, 7 och 11 på en 12-timmarsklocka), och de tal som har en invers modulo n. Euler bevisade att a^φ(n) ≡ 1 (mod n) för varje a som är relativt prima med n, och RSA-kryptering bygger på det: med n = 3233 = 61 × 53 är φ(n) = 60 × 52 = 3 120, och den publika exponenten 17 har den privata partnern 2 753, eftersom 17 × 2 753 = 15 × 3 120 + 1.
Ofta ställda frågor
Vad är Eulers fi-funktion?
φ(n) är antalet heltal från 1 till n som inte har någon gemensam delare med n utom 1. φ(9) = 6, eftersom 1, 2, 4, 5, 7 och 8 är relativt prima med 9, medan 3, 6 och 9 delar faktorn 3. Enligt konvention är φ(1) = 1. Euler studerade funktionen på 1760-talet; Gauss gav den symbolen φ 1801 och James Joseph Sylvester det engelska namnet totient 1879.
Vad är φ av ett primtal?
p − 1, eftersom varje tal från 1 till p − 1 är relativt prima med ett primtal p, så φ(97) = 96. För en primtalspotens gäller φ(p^k) = p^k − p^(k−1), eftersom bara multiplerna av p har en gemensam delare med den: φ(81) = 81 − 27 = 54.
Vad säger Eulers sats?
Om a och n är relativt prima ger a^φ(n) resten 1 vid division med n. För n = 60 och a = 7: φ(60) = 16, och 7^16 ≡ 1 (mod 60). Fermats lilla sats är fallet med ett primtal n. Ofta räcker redan en mindre exponent: 7^4 = 2 401 = 40 × 60 + 1. Den minsta exponent som fungerar för varje a som är relativt prima med n är Carmichaels funktion λ(n), som för 60 är 4.
Kan två tal ha samma värde på φ?
Ja, och oftast har flera det: φ(n) = 24 för n = 35, 39, 45, 52, 56, 70, 72, 78, 84 och 90. Vissa jämna tal är aldrig ett värde på φ, det minsta är 14, och inget udda tal över 1 är det, eftersom φ(n) är jämnt från n = 3. Robert Carmichael påstod 1907 att inget värde antas exakt en gång. Det är fortfarande obevisat, och Kevin Ford visade 1998 att ett undantag måste vara större än 10^(10^10).
Hur stora tal kan jag ange?
Vilket heltal som helst upp till 10^18. Räknaren faktoriserar det med exakt heltalsaritmetik i din webbläsare, så φ(10^18) = 4 × 10^17 och φ(999 999 866 000 004 473) = 999 999 864 000 004 608 stämmer till sista siffran. Talen 1 till n ritas upp till 500, diagrammet går upp till 100 000 och inversen fungerar för värden upp till 10^10.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor