Liczba liczb całkowitych do 36, które nie mają z nią wspólnego czynnika, to 12. Przepis iloczynowy bierze 36 i odrzuca ułamki podzielne przez każdy czynnik pierwszy: pomnóż przez (1 − 1/2), żeby odrzucić parzyste, przez (1 − 1/3), żeby odrzucić wielokrotności trójki, a stół roboczy wypisze 12. Ponieważ 36 = 2²·3², te dwie liczby pierwsze są jedynymi, które mogą być wspólne.
Drugi link liczy to samo w drugą stronę, przez włączenia i wyłączenia: osiemnaście wielokrotności 2, dwanaście wielokrotności 3 i sześć wielokrotności 6 odjętych dwa razy, więc dodanych z powrotem raz — 36 − 18 − 12 + 6 = 12. Oba przepisy muszą się zgodzić, a powód, dla którego się zgadzają, to że „podzielne przez 2 lub 3” to dokładnie „nierelatywne pierwsze z 36”. φ to liczba, na której działa arytmetyka RSA: twierdzenie Eulera mówi a^φ(n) ≡ 1 (mod n) dla każdego a względnie pierwszego z n, więc rozmiar tego zliczenia to rozmiar cyklu.
Odpowiedź
12
Jak to czytać
36·(1 − 1/2)(1 − 1/3) na stole roboczym. Drugi link to zliczenie przez włączenia i wyłączenia, a trzeci to rozkład 2²·3², który mówi, które liczby pierwsze się liczą.
Źródło
Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.