φ(n)
Czynniki pierwsze
Udział względnie pierwszych
Dzielniki

          Pokaż

          Więcej o funkcji Eulera

          Kalkulator funkcji Eulera

          Spośród liczb od 1 do 12 tylko 1, 5, 7 i 11 nie mają wspólnego dzielnika z 12, więc φ(12) = 4. Funkcja Eulera liczy takie liczby względnie pierwsze dla dowolnego n. Wpisz liczbę do 10^18, aby otrzymać φ(n) z czynnikami pierwszymi i rozpisanym wzorem iloczynowym, zobaczyć liczby od 1 do n z wyróżnionymi względnie pierwszymi, sprawdzić twierdzenie Eulera, narysować φ(k) dla nawet 100 000 liczb naraz albo znaleźć każde n o danym φ(n). Wpisz liczbę całkowitą n do 10^18 albo wybierz rozwiązany przykład. Kafelki pokazują φ(n), czynniki pierwsze n, udział liczb od 1 do n względnie pierwszych z n i liczbę dzielników, a kroki rozpisują wzór iloczynowy na twoich liczbach. Do n = 500 rysowane są liczby od 1 do n: względnie pierwsze z n są wypełnione, pozostałe mają kolor najmniejszej liczby pierwszej, którą dzielą z n. Wskaż liczbę, aby zobaczyć jej NWD z n, i kliknij ją, aby użyć jej jako a w twierdzeniu Eulera. Wykres pokazuje φ(k) dla każdego k do pewnej granicy; kliknij punkt, aby otworzyć tę liczbę. Odwrotność wypisuje każde n z φ(n) = m; kliknij jedno z nich, aby je otworzyć.

          Jak to działa

          1. Wpisz liczbę całkowitą n do 10^18 albo wybierz rozwiązany przykład, taki jak φ(60), moduł RSA lub liczba Carmichaela 561.
          2. Odczytaj φ(n), czynniki pierwsze i wzór iloczynowy na twoich liczbach. Do 500 wskaż liczby od 1 do n, aby zobaczyć ich NWD z n, i kliknij jedną z nich, aby sprawdzić na niej twierdzenie Eulera.
          3. Przełącz na Wykres, aby zobaczyć φ(k) dla każdego k do 100 000, albo na Odwrotność, aby wypisać każde n z φ(n) = m.

          Jak oblicza się φ(n)

          Rozłóż n na czynniki pierwsze i pomnóż n przez (1 − 1/p) dla każdej liczby pierwszej p, która dzieli n. Dla 60 = 2² × 3 × 5 daje to 60 × 1/2 × 2/3 × 4/5 = 16. Skreślanie daje tę samą liczbę: z 60 liczb 30 jest parzystych; z 30 nieparzystych 10 to wielokrotności 3; z 20 pozostałych 4 to wielokrotności 5, a zostaje 16. Dla potęgi liczby pierwszej wzór ma postać φ(p^k) = p^(k−1)(p − 1), a wartości się mnoży: φ(60) = 2 × 2 × 4. Trudny jest rozkład na czynniki. Kalkulator używa dzielenia próbnego, testu pierwszości Millera–Rabina i metody rho Pollarda, więc nawet 18-cyfrowy iloczyn dwóch 9-cyfrowych liczb pierwszych zajmuje ułamek sekundy.

          Gdzie używa się funkcji Eulera

          φ(n) liczy ułamki k/n między 0 a 1, które są już nieskracalne, długości kroków, przy których wskazówka zegara z n godzinami przechodzi przez każdą godzinę (1, 5, 7 i 11 na zegarze 12-godzinnym), oraz liczby, które mają odwrotność modulo n. Euler udowodnił, że a^φ(n) ≡ 1 (mod n) dla każdego a względnie pierwszego z n, i na tym opiera się szyfrowanie RSA: dla n = 3233 = 61 × 53 mamy φ(n) = 60 × 52 = 3 120, a wykładnik publiczny 17 ma prywatnego partnera 2 753, bo 17 × 2 753 = 15 × 3 120 + 1.

          Często zadawane pytania

          Czym jest funkcja Eulera?

          φ(n) to liczba liczb całkowitych od 1 do n, które nie mają z n wspólnego dzielnika poza 1. φ(9) = 6, bo 1, 2, 4, 5, 7 i 8 są względnie pierwsze z 9, a 3, 6 i 9 mają z nią wspólny czynnik 3. Umownie φ(1) = 1. Euler badał tę funkcję w latach 60. XVIII wieku; Gauss nadał jej symbol φ w 1801 roku, a James Joseph Sylvester angielską nazwę totient w 1879 roku.

          Ile wynosi φ liczby pierwszej?

          p − 1, bo każda liczba od 1 do p − 1 jest względnie pierwsza z liczbą pierwszą p, więc φ(97) = 96. Dla potęgi liczby pierwszej φ(p^k) = p^k − p^(k−1), bo tylko wielokrotności p mają z nią wspólny dzielnik: φ(81) = 81 − 27 = 54.

          Co mówi twierdzenie Eulera?

          Jeśli a i n są względnie pierwsze, to a^φ(n) daje resztę 1 z dzielenia przez n. Dla n = 60 i a = 7: φ(60) = 16, a 7^16 ≡ 1 (mod 60). Małe twierdzenie Fermata to przypadek pierwszego n. Często wystarcza już mniejszy wykładnik: 7^4 = 2 401 = 40 × 60 + 1. Najmniejszy wykładnik, który działa dla każdego a względnie pierwszego z n, to funkcja Carmichaela λ(n), dla 60 równa 4.

          Czy dwie liczby mogą mieć tę samą wartość φ?

          Tak, i zwykle jest ich kilka: φ(n) = 24 dla n = 35, 39, 45, 52, 56, 70, 72, 78, 84 i 90. Niektóre liczby parzyste nigdy nie są wartością φ, najmniejsza z nich to 14, a żadna liczba nieparzysta większa od 1 nią nie jest, bo φ(n) jest parzyste od n = 3. Robert Carmichael twierdził w 1907 roku, że żadna wartość nie jest przyjmowana dokładnie raz. Wciąż nie jest to udowodnione, a Kevin Ford pokazał w 1998 roku, że wyjątek musiałby być większy niż 10^(10^10).

          Jak duże liczby mogę wpisać?

          Dowolną liczbę całkowitą do 10^18. Kalkulator rozkłada ją w dokładnej arytmetyce całkowitej w twojej przeglądarce, więc φ(10^18) = 4 × 10^17 i φ(999 999 866 000 004 473) = 999 999 864 000 004 608 zgadzają się do ostatniej cyfry. Liczby od 1 do n są rysowane do 500, wykres sięga 100 000, a odwrotność działa dla wartości do 10^10.

          Chcesz wypróbować?

          Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

          Przejdź do edytora