Eulers fi-funktion förklarad

Skriv ner talen från 1 till 10 och stryk varje tal som har en gemensam delare med 10. Fyra blir kvar: 1, 3, 7 och 9. Det antalet, φ(10) = 4, är Eulers fi-funktion, en av talteorins mest använda funktioner, från bråk och klockor till krypteringen som skyddar betalningar på nätet.

Talen 1 till 30 i ett rutnät med de åtta som är relativt prima med 30 ifyllda, formeln φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 och ett diagram över φ(k) med primtalen på en rät linje
Talen 1 till 30 i ett rutnät med de åtta som är relativt prima med 30 ifyllda, formeln φ(30) = 30 × 1/2 × 2/3 × 4/5 = 8 och ett diagram över φ(k) med primtalen på en rät linje

Att räkna relativt prima tal

Två tal är relativt prima när deras största gemensamma delare är 1. φ(n) räknar de k från 1 till n med sgd(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 och φ(1) = 1. Samma antal dyker upp på många ställen. Det är antalet bråk k/n mellan 0 och 1 som redan är förkortade, antalet steglängder som för en visare förbi varje timme på en klocka med n timmar, och antalet k som har en invers modulo n, så att k × x ≡ 1 (mod n) går att lösa.

Produktformeln

Om primtalen som delar n är p₁, p₂ … är φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Skälet är ett såll. Hälften av alla tal är jämna, så att ta bort multiplerna av 2 lämnar andelen 1 − 1/2; av de tal som är kvar är vart tredje en multipel av 3, och så vidare. Enligt kinesiska restsatsen är villkoren för olika primtal oberoende, så andelarna multipliceras helt enkelt. För 100 = 2² × 5² ger det 100 × 1/2 × 4/5 = 40. Två egenskaper ger samma resultat i en annan form: φ(p^k) = p^(k−1)(p − 1), och φ(mn) = φ(m) φ(n) när m och n är relativt prima, så φ(100) = φ(4) × φ(25) = 2 × 20 = 40.

Eulers sats

Fermat märkte 1640 att a^(p−1) ≡ 1 (mod p) för ett primtal p och varje a som inte är delbart med p. Euler bevisade den allmänna versionen, publicerad 1763: a^φ(n) ≡ 1 (mod n) så snart sgd(a, n) = 1. Beviset är kort. Multiplicera de φ(n) tal som är relativt prima med n med a; produkterna är åter relativt prima med n och alla olika modulo n, så de är samma tal i en annan ordning, och jämför man de två produkterna återstår a^φ(n) ≡ 1. Den minsta exponent som fungerar för ett givet a är dess ordning, som alltid delar φ(n); den minsta som fungerar för alla a på en gång är Carmichaels funktion λ(n). För 561 = 3 × 11 × 17 delar λ(561) = 80 talet 560, så a^560 ≡ 1 (mod 561) för varje a som är relativt prima med 561, trots att 561 inte är ett primtal. Det är det minsta Carmichaeltalet och skälet till att Fermats test ensamt inte kan bevisa att ett tal är ett primtal.

Leonhard Euler på ett porträtt av Jakob Emanuel Handmann. År 1763 publicerade han den allmänna formen av Fermats iakttagelse: a^φ(n) ≡ 1 (mod n) när a och n är relativt prima.
Leonhard Euler på ett porträtt av Jakob Emanuel Handmann. År 1763 publicerade han den allmänna formen av Fermats iakttagelse: a^φ(n) ≡ 1 (mod n) när a och n är relativt prima.

Gauss delarsumma och medelvärdet

Summera φ(d) över delarna d till n så får du alltid tillbaka n: för 12 är φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss bevisade det i sina Disquisitiones Arithmeticae från 1801; man ser det genom att förkorta bråken 1/12, 2/12 … 12/12 och sortera dem efter nämnare. I genomsnitt är φ(k) ungefär 0,61 k: medelvärdet av φ(k)/k går mot 6/π² ≈ 0,6079, vilket också är sannolikheten att två slumpmässiga heltal är relativt prima, och φ(1) + … + φ(N) ligger nära 3N²/π². För N = 1 000 är summan 304 192, mot 3N²/π² ≈ 303 964.

Carl Friedrich Gauss på ett porträtt av Christian Albrecht Jensen från 1840. Han införde kongruensbeteckningen a ≡ b (mod n) i Disquisitiones Arithmeticae från 1801.
Carl Friedrich Gauss på ett porträtt av Christian Albrecht Jensen från 1840. Han införde kongruensbeteckningen a ≡ b (mod n) i Disquisitiones Arithmeticae från 1801.

Värden som aldrig förekommer

φ(n) är jämnt för varje n från 3 och uppåt, eftersom talen som är relativt prima med n kommer i par k och n − k. Inte heller varje jämnt tal är ett värde: 14, 26, 34, 38 och 50 är de första som aldrig förekommer, medan 24 är värdet för tio olika tal, från 35 till 90. Att hitta dem är en ändlig sökning, eftersom p − 1 måste dela φ(n) för varje primtal p som delar n. År 1907 påstod Robert Carmichael att inget värde antas exakt en gång. Hans bevis var felaktigt, påståendet är fortfarande öppet, och varje undantag måste vara större än 10^(10^10). D. H. Lehmer frågade 1932 om φ(n) kan dela n − 1 för ett sammansatt n; inget exempel är känt.

Fi-funktionen i RSA

RSA väljer två stora primtal p och q och publicerar n = pq och en exponent e. Eftersom φ(n) = (p − 1)(q − 1) kan den som kan faktorisera n beräkna φ(n), och därifrån den privata exponenten d med e × d ≡ 1 (mod φ(n)); Eulers sats garanterar då att (m^e)^d ≡ m (mod n). I läroboksexemplet n = 3233 = 61 × 53 är φ(n) = 3 120, e = 17 och d = 2 753. Många implementationer använder i stället λ(n) = mgm(p − 1, q − 1), här 780, vilket ger det mindre d = 413. Att beräkna φ(n) för en RSA-modul med 600 siffror är lika svårt som att faktorisera den: ur n och φ(n) följer de två primtalen med en enda kvadratrot.

Ron Rivest, Adi Shamir och Len Adleman (från vänster till höger)
Ron Rivest, Adi Shamir och Len Adleman (från vänster till höger)

Utforska själv

Öppna räknaren och ange ett valfritt n upp till 10^18 för att se φ(n) med primfaktorerna och formeln. Upp till 500 ritas talen 1 till n, de relativt prima ifyllda och de övriga färgade efter det minsta primtal de har gemensamt med n, så att produktformeln blir ett såll man kan räkna. Välj ett tal a för att kontrollera Eulers sats, byt till Diagram för att se φ(k) upp till 100 000 med primtalen på linjen φ(p) = p − 1, eller till Invers för att hitta varje n med φ(n) = m.

Ofta ställda frågor

Varför är φ(1) = 1?

Eftersom sgd(1, 1) = 1: det enda talet från 1 till 1 är relativt prima med 1. Konventionen håller också formlerna giltiga, till exempel Gauss summa över delarna till n, som för n = 1 helt enkelt är φ(1) = 1.

Är φ samma sak som primtalsfunktionen?

Nej. π(n) räknar primtalen upp till n, φ(n) de tal upp till n som är relativt prima med n. φ(10) = 4 räknar 1, 3, 7 och 9, medan π(10) = 4 räknar 2, 3, 5 och 7. Att de är lika här är en slump: φ(12) = 4, men π(12) = 5.

Hur snabbt kan φ(n) beräknas?

Lika snabbt som n kan faktoriseras. Med kända primfaktorer räcker några multiplikationer; utan dem finns ingen känd snabb metod, och det är vad RSA bygger på. För tal upp till 10^18 tar faktoriseringen millisekunder i en webbläsare, för tal med hundratals siffror kan den ta år.

Vilka tal har minst φ(n) i förhållande till n?

Tal med många små primfaktorer. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… beror bara på vilka primtal som delar n, inte på deras potenser: för varje tvåpotens är det exakt 1/2, och för 30 = 2 × 3 × 5 är det 8/30, ungefär 27 %. Produkten av de 15 första primtalen, 614 889 782 588 491 410, har φ(n)/n ≈ 14 %, det lägsta värdet av alla tal upp till 10^18.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna fi-räknaren