Eulers phi-funktion forklaret
Skriv tallene fra 1 til 10 ned, og overstreg hvert tal, der har en fælles divisor med 10. Fire er tilbage: 1, 3, 7 og 9. Det antal, φ(10) = 4, er Eulers phi-funktion, en af de mest brugte funktioner i talteorien, fra brøker og ure til den kryptering, der beskytter betalinger på nettet.
At tælle indbyrdes primiske tal
To tal er indbyrdes primiske, når deres største fælles divisor er 1. φ(n) tæller de k fra 1 til n med sfd(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 og φ(1) = 1. Det samme antal dukker op mange steder. Det er antallet af brøker k/n mellem 0 og 1, der allerede er uforkortelige, antallet af skridtlængder, der fører en viser forbi hver time på et ur med n timer, og antallet af k, der har en invers modulo n, så k × x ≡ 1 (mod n) kan løses.
Produktformlen
Hvis primtallene, der går op i n, er p₁, p₂ …, så er φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Grunden er en si. Halvdelen af alle tal er lige, så når multiplerne af 2 fjernes, er brøkdelen 1 − 1/2 tilbage; af de resterende tal er hvert tredje et multiplum af 3, og så videre. Ifølge den kinesiske restklassesætning er betingelserne for forskellige primtal uafhængige, så brøkerne ganges simpelthen. For 100 = 2² × 5² giver det 100 × 1/2 × 4/5 = 40. To egenskaber giver samme resultat i en anden form: φ(p^k) = p^(k−1)(p − 1), og φ(mn) = φ(m) φ(n), når m og n er indbyrdes primiske, så φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Eulers sætning
Fermat bemærkede i 1640, at a^(p−1) ≡ 1 (mod p) for et primtal p og ethvert a, som p ikke går op i. Euler beviste den generelle version, udgivet i 1763: a^φ(n) ≡ 1 (mod n), når sfd(a, n) = 1. Beviset er kort. Gang de φ(n) tal, der er indbyrdes primiske med n, med a; produkterne er igen indbyrdes primiske med n og alle forskellige modulo n, så de er de samme tal i en anden rækkefølge, og sammenligner man de to produkter, står a^φ(n) ≡ 1 tilbage. Den mindste eksponent, der virker for et givet a, er dets orden, som altid går op i φ(n); den mindste, der virker for alle a på én gang, er Carmichael-funktionen λ(n). For 561 = 3 × 11 × 17 går λ(561) = 80 op i 560, så a^560 ≡ 1 (mod 561) for hvert a, der er indbyrdes primisk med 561, selvom 561 ikke er et primtal. Det er det mindste Carmichael-tal og grunden til, at Fermats test alene ikke kan bevise, at et tal er et primtal.
Gauss' divisorsum og gennemsnittet
Læg φ(d) sammen over divisorerne d i n, og du får altid n igen: for 12 er φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss beviste det i sine Disquisitiones Arithmeticae fra 1801; man ser det ved at forkorte brøkerne 1/12, 2/12 … 12/12 og sortere dem efter nævner. I gennemsnit er φ(k) omkring 0,61 k: gennemsnittet af φ(k)/k går mod 6/π² ≈ 0,6079, som også er sandsynligheden for, at to tilfældige hele tal er indbyrdes primiske, og φ(1) + … + φ(N) ligger tæt på 3N²/π². For N = 1.000 er summen 304.192, mod 3N²/π² ≈ 303.964.
Værdier, der aldrig forekommer
φ(n) er lige for hvert n fra 3 og op, fordi tallene, der er indbyrdes primiske med n, kommer i par k og n − k. Heller ikke hvert lige tal er en værdi: 14, 26, 34, 38 og 50 er de første, der aldrig forekommer, mens 24 er værdien for ti forskellige tal, fra 35 til 90. At finde dem er en endelig søgning, for for hvert primtal p, der går op i n, skal p − 1 gå op i φ(n). I 1907 påstod Robert Carmichael, at ingen værdi antages præcis én gang. Hans bevis var forkert, påstanden er stadig åben, og enhver undtagelse skulle være større end 10^(10^10). D. H. Lehmer spurgte i 1932, om φ(n) kan gå op i n − 1 for et sammensat n; der kendes intet eksempel.
Phi-funktionen i RSA
RSA vælger to store primtal p og q og offentliggør n = pq og en eksponent e. Da φ(n) = (p − 1)(q − 1), kan enhver, der kan opløse n, beregne φ(n) og derfra den private eksponent d med e × d ≡ 1 (mod φ(n)); Eulers sætning sikrer så, at (m^e)^d ≡ m (mod n). I lærebogseksemplet n = 3233 = 61 × 53 er φ(n) = 3.120, e = 17 og d = 2.753. Mange implementeringer bruger i stedet λ(n) = mfm(p − 1, q − 1), her 780, hvilket giver det mindre d = 413. At beregne φ(n) for et RSA-modul med 600 cifre er lige så svært som at opløse det: Ud fra n og φ(n) følger de to primtal med en enkelt kvadratrod.
Udforsk selv
Åbn lommeregneren, og indtast et vilkårligt n op til 10^18 for at se φ(n) med primfaktorerne og formlen. Op til 500 tegnes tallene 1 til n, de indbyrdes primiske udfyldt og de andre farvet efter det mindste primtal, de har til fælles med n, så produktformlen bliver en si, man kan tælle efter. Vælg et tal a for at tjekke Eulers sætning, skift til Graf for at se φ(k) op til 100.000 med primtallene på linjen φ(p) = p − 1, eller til Invers for at finde hvert n med φ(n) = m.
Ofte stillede spørgsmål
Hvorfor er φ(1) = 1?
Fordi sfd(1, 1) = 1: Det eneste tal fra 1 til 1 er indbyrdes primisk med 1. Konventionen holder også formlerne gyldige, for eksempel Gauss' sum over divisorerne i n, som for n = 1 bare er φ(1) = 1.
Er φ det samme som primtalsfunktionen?
Nej. π(n) tæller primtallene op til n, φ(n) de tal op til n, der er indbyrdes primiske med n. φ(10) = 4 tæller 1, 3, 7 og 9, mens π(10) = 4 tæller 2, 3, 5 og 7. At de er ens her, er et tilfælde: φ(12) = 4, men π(12) = 5.
Hvor hurtigt kan φ(n) beregnes?
Lige så hurtigt, som n kan opløses. Med kendte primfaktorer er det nogle få multiplikationer; uden dem kendes ingen hurtig metode, og det er det, RSA bygger på. For tal op til 10^18 tager faktoriseringen millisekunder i en browser, for tal med hundredvis af cifre kan den tage år.
Hvilke tal har det mindste φ(n) i forhold til n?
Tal med mange små primfaktorer. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… afhænger kun af, hvilke primtal der går op i n, ikke af deres potenser: For enhver potens af 2 er det præcis 1/2, og for 30 = 2 × 3 × 5 er det 8/30, cirka 27 %. Produktet af de første 15 primtal, 614.889.782.588.491.410, har φ(n)/n ≈ 14 %, den laveste værdi af alle tal op til 10^18.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn phi-lommeregneren