Funkcja Eulera wyjaśniona
Wypisz liczby od 1 do 10 i skreśl każdą, która ma wspólny dzielnik z 10. Zostają cztery: 1, 3, 7 i 9. Ta liczba, φ(10) = 4, to funkcja Eulera, jedna z najczęściej używanych funkcji teorii liczb, od ułamków i zegarów po szyfrowanie chroniące płatności w internecie.
Liczenie liczb względnie pierwszych
Dwie liczby są względnie pierwsze, gdy ich największy wspólny dzielnik wynosi 1. φ(n) liczy te k od 1 do n, dla których NWD(k, n) = 1: φ(9) = 6, φ(10) = 4, φ(12) = 4 i φ(1) = 1. Ta sama liczba pojawia się w wielu miejscach. To liczba ułamków k/n między 0 a 1, które są już nieskracalne, liczba długości kroków, przy których wskazówka zegara z n godzinami przechodzi przez każdą godzinę, i liczba tych k, które mają odwrotność modulo n, tak że k × x ≡ 1 (mod n) ma rozwiązanie.
Wzór iloczynowy
Jeśli liczbami pierwszymi dzielącymi n są p₁, p₂ …, to φ(n) = n × (1 − 1/p₁) × (1 − 1/p₂) × …. Powodem jest sito. Połowa wszystkich liczb jest parzysta, więc usunięcie wielokrotności 2 zostawia część 1 − 1/2; z pozostałych liczb co trzecia jest wielokrotnością 3 i tak dalej. Z chińskiego twierdzenia o resztach warunki dla różnych liczb pierwszych są niezależne, więc części po prostu się mnożą. Dla 100 = 2² × 5² daje to 100 × 1/2 × 4/5 = 40. Dwie własności dają ten sam wynik w innej postaci: φ(p^k) = p^(k−1)(p − 1) oraz φ(mn) = φ(m) φ(n), gdy m i n są względnie pierwsze, więc φ(100) = φ(4) × φ(25) = 2 × 20 = 40.
Twierdzenie Eulera
Fermat zauważył w 1640 roku, że a^(p−1) ≡ 1 (mod p) dla liczby pierwszej p i każdego a niepodzielnego przez p. Euler udowodnił ogólną wersję, opublikowaną w 1763 roku: a^φ(n) ≡ 1 (mod n), gdy tylko NWD(a, n) = 1. Dowód jest krótki. Pomnóż przez a te φ(n) liczb, które są względnie pierwsze z n; iloczyny znów są względnie pierwsze z n i wszystkie różne modulo n, więc to te same liczby w innej kolejności, a porównanie obu iloczynów zostawia a^φ(n) ≡ 1. Najmniejszy wykładnik, który działa dla danego a, to jego rząd, który zawsze dzieli φ(n); najmniejszy, który działa dla wszystkich a naraz, to funkcja Carmichaela λ(n). Dla 561 = 3 × 11 × 17 liczba λ(561) = 80 dzieli 560, więc a^560 ≡ 1 (mod 561) dla każdego a względnie pierwszego z 561, choć 561 nie jest liczbą pierwszą. To najmniejsza liczba Carmichaela i powód, dla którego sam test Fermata nie może dowieść, że liczba jest pierwsza.
Suma Gaussa po dzielnikach i średnia
Dodaj φ(d) po dzielnikach d liczby n, a zawsze otrzymasz z powrotem n: dla 12 mamy φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. Gauss udowodnił to w swoich Disquisitiones Arithmeticae z 1801 roku; widać to, gdy skróci się ułamki 1/12, 2/12 … 12/12 i posortuje je według mianowników. Średnio φ(k) wynosi około 0,61 k: średnia φ(k)/k dąży do 6/π² ≈ 0,6079, co jest też prawdopodobieństwem, że dwie losowe liczby całkowite są względnie pierwsze, a φ(1) + … + φ(N) jest bliskie 3N²/π². Dla N = 1 000 suma wynosi 304 192, wobec 3N²/π² ≈ 303 964.
Wartości, które nigdy nie występują
φ(n) jest parzyste dla każdego n od 3 wzwyż, bo liczby względnie pierwsze z n występują parami k i n − k. Nie każda liczba parzysta jest wartością: 14, 26, 34, 38 i 50 to pierwsze, które nigdy nie występują, a 24 jest wartością dla dziesięciu różnych liczb, od 35 do 90. Ich znalezienie to skończone przeszukiwanie, bo dla każdej liczby pierwszej p dzielącej n liczba p − 1 musi dzielić φ(n). W 1907 roku Robert Carmichael twierdził, że żadna wartość nie jest przyjmowana dokładnie raz. Jego dowód był błędny, problem pozostaje otwarty, a każdy wyjątek musiałby być większy niż 10^(10^10). D. H. Lehmer zapytał w 1932 roku, czy φ(n) może dzielić n − 1 dla złożonego n; żaden przykład nie jest znany.
Funkcja Eulera w RSA
RSA wybiera dwie duże liczby pierwsze p i q i publikuje n = pq oraz wykładnik e. Ponieważ φ(n) = (p − 1)(q − 1), każdy, kto potrafi rozłożyć n, może obliczyć φ(n), a z niej prywatny wykładnik d, dla którego e × d ≡ 1 (mod φ(n)); twierdzenie Eulera gwarantuje wtedy, że (m^e)^d ≡ m (mod n). W podręcznikowym przykładzie n = 3233 = 61 × 53 mamy φ(n) = 3 120, e = 17 i d = 2 753. Wiele implementacji używa zamiast tego λ(n) = NWW(p − 1, q − 1), tu 780, co daje mniejsze d = 413. Obliczenie φ(n) dla modułu RSA o 600 cyfrach jest tak samo trudne jak jego rozkład: z n i φ(n) obie liczby pierwsze wynikają za pomocą jednego pierwiastka kwadratowego.
Odkrywaj sam
Otwórz kalkulator i wpisz dowolne n do 10^18, aby zobaczyć φ(n) z czynnikami pierwszymi i wzorem. Do 500 rysowane są liczby od 1 do n, względnie pierwsze wypełnione, a pozostałe w kolorze najmniejszej liczby pierwszej, którą dzielą z n, więc wzór iloczynowy staje się sitem, które można policzyć. Wybierz liczbę a, aby sprawdzić twierdzenie Eulera, przełącz na Wykres, aby zobaczyć φ(k) do 100 000 z liczbami pierwszymi na prostej φ(p) = p − 1, albo na Odwrotność, aby znaleźć każde n z φ(n) = m.
Często zadawane pytania
Dlaczego φ(1) = 1?
Ponieważ NWD(1, 1) = 1: jedyna liczba od 1 do 1 jest względnie pierwsza z 1. Ta umowa utrzymuje też poprawność wzorów, na przykład sumy Gaussa po dzielnikach n, która dla n = 1 jest po prostu φ(1) = 1.
Czy φ to to samo co funkcja liczby liczb pierwszych?
Nie. π(n) liczy liczby pierwsze do n, a φ(n) liczby do n względnie pierwsze z n. φ(10) = 4 liczy 1, 3, 7 i 9, a π(10) = 4 liczy 2, 3, 5 i 7. Zgadzają się tu przypadkiem: φ(12) = 4, ale π(12) = 5.
Jak szybko można obliczyć φ(n)?
Tak szybko, jak da się rozłożyć n. Przy znanych czynnikach pierwszych to kilka mnożeń; bez nich nie jest znana żadna szybka metoda i na tym opiera się RSA. Dla liczb do 10^18 rozkład zajmuje w przeglądarce milisekundy, dla liczb o setkach cyfr może trwać latami.
Które liczby mają najmniejsze φ(n) w stosunku do n?
Liczby z wieloma małymi czynnikami pierwszymi. φ(n)/n = (1 − 1/p₁)(1 − 1/p₂)… zależy tylko od tego, jakie liczby pierwsze dzielą n, a nie od ich potęg: dla każdej potęgi 2 wynosi dokładnie 1/2, a dla 30 = 2 × 3 × 5 wynosi 8/30, około 27 %. Iloczyn pierwszych 15 liczb pierwszych, 614 889 782 588 491 410, ma φ(n)/n ≈ 14 %, najmniej spośród wszystkich liczb do 10^18.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz kalkulator