φ(n)
Primfaktorer
Andel indbyrdes primiske
Divisorer

          Vis

          Mere om Eulers phi-funktion

          Lommeregner for Eulers phi-funktion

          Af tallene fra 1 til 12 har kun 1, 5, 7 og 11 ingen fælles divisor med 12, så φ(12) = 4. Eulers phi-funktion tæller disse indbyrdes primiske tal for ethvert n. Indtast et tal op til 10^18 for at få φ(n) med primfaktorerne og produktformlen skrevet ud, se tallene 1 til n med de indbyrdes primiske fremhævet, tjekke Eulers sætning, tegne φ(k) for op til 100.000 tal på én gang eller finde hvert n med et givet φ(n). Indtast et helt tal n op til 10^18, eller vælg et gennemregnet eksempel. Felterne viser φ(n), primfaktorerne i n, andelen af tallene 1 til n, der er indbyrdes primiske med n, og antallet af divisorer, og trinnene skriver produktformlen ud med dine tal. Op til n = 500 tegnes tallene 1 til n: De indbyrdes primiske er udfyldt, de andre har farven for det mindste primtal, de har til fælles med n. Peg på et tal for at se dets sfd med n, og klik på det for at bruge det som a i Eulers sætning. Graf viser φ(k) for hvert k op til en grænse; klik på et punkt for at åbne det tal. Invers viser hvert n med φ(n) = m; klik på et af dem for at åbne det.

          Sådan virker det

          1. Indtast et helt tal n op til 10^18, eller vælg et gennemregnet eksempel som φ(60), et RSA-modul eller Carmichael-tallet 561.
          2. Aflæs φ(n), primfaktorerne og produktformlen med dine tal. Op til 500 kan du pege på tallene 1 til n for at se deres sfd med n og klikke på et af dem for at tjekke Eulers sætning med det.
          3. Skift til Graf for at se φ(k) for hvert k op til 100.000, eller til Invers for at få vist hvert n med φ(n) = m.

          Sådan beregnes φ(n)

          Opløs n i primfaktorer, og gang n med (1 − 1/p) for hvert primtal p, der går op i n. For 60 = 2² × 3 × 5 giver det 60 × 1/2 × 2/3 × 4/5 = 16. Overstregning giver samme antal: Af de 60 tal er 30 lige; af de 30 ulige er 10 multipla af 3; af de 20, der er tilbage, er 4 multipla af 5, og så er der 16 tilbage. For en primtalspotens er formlen φ(p^k) = p^(k−1)(p − 1), og værdierne ganges: φ(60) = 2 × 2 × 4. Det svære er faktoriseringen. Lommeregneren bruger prøvedivision, en Miller-Rabin-primtalstest og Pollards rho-metode, så selv et 18-cifret produkt af to 9-cifrede primtal tager en brøkdel af et sekund.

          Hvor phi-funktionen bruges

          φ(n) tæller de brøker k/n mellem 0 og 1, der allerede er uforkortelige, de skridtlængder, der fører en viser forbi hver time på et ur med n timer (1, 5, 7 og 11 på et 12-timers ur), og de tal, der har en invers modulo n. Euler beviste, at a^φ(n) ≡ 1 (mod n) for hvert a, der er indbyrdes primisk med n, og RSA-kryptering bygger på det: Med n = 3233 = 61 × 53 er φ(n) = 60 × 52 = 3.120, og den offentlige eksponent 17 har den private partner 2.753, fordi 17 × 2.753 = 15 × 3.120 + 1.

          Ofte stillede spørgsmål

          Hvad er Eulers phi-funktion?

          φ(n) er antallet af hele tal fra 1 til n, der ikke har nogen fælles divisor med n ud over 1. φ(9) = 6, fordi 1, 2, 4, 5, 7 og 8 er indbyrdes primiske med 9, mens 3, 6 og 9 deler faktoren 3. Efter konvention er φ(1) = 1. Euler studerede funktionen i 1760'erne; Gauss gav den symbolet φ i 1801, og James Joseph Sylvester det engelske navn totient i 1879.

          Hvad er φ af et primtal?

          p − 1, fordi hvert tal fra 1 til p − 1 er indbyrdes primisk med et primtal p, så φ(97) = 96. For en primtalspotens er φ(p^k) = p^k − p^(k−1), fordi kun multiplerne af p har en fælles divisor med den: φ(81) = 81 − 27 = 54.

          Hvad siger Eulers sætning?

          Hvis a og n er indbyrdes primiske, giver a^φ(n) resten 1 ved division med n. For n = 60 og a = 7: φ(60) = 16, og 7^16 ≡ 1 (mod 60). Fermats lille sætning er tilfældet, hvor n er et primtal. Ofte virker en mindre eksponent allerede: 7^4 = 2.401 = 40 × 60 + 1. Den mindste eksponent, der virker for hvert a, der er indbyrdes primisk med n, er Carmichael-funktionen λ(n), som for 60 er 4.

          Kan to tal have samme phi-værdi?

          Ja, og som regel har flere det: φ(n) = 24 for n = 35, 39, 45, 52, 56, 70, 72, 78, 84 og 90. Nogle lige tal er aldrig en værdi af φ, det mindste er 14, og intet ulige tal over 1 er det, fordi φ(n) er lige fra n = 3. Robert Carmichael påstod i 1907, at ingen værdi antages præcis én gang. Det er stadig ikke bevist, og Kevin Ford viste i 1998, at en undtagelse skulle være større end 10^(10^10).

          Hvor store tal kan jeg indtaste?

          Ethvert helt tal op til 10^18. Lommeregneren opløser det med eksakt heltalsaritmetik i din browser, så φ(10^18) = 4 × 10^17 og φ(999.999.866.000.004.473) = 999.999.864.000.004.608 passer til sidste ciffer. Tallene 1 til n tegnes op til 500, grafen går op til 100.000, og den inverse virker for værdier op til 10^10.

          Er du klar til at prøve?

          Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

          Gå til Editor