Banyaknya bilangan bulat sampai 36 yang tidak punya pembagi persekutuan dengannya ialah 12. Resep hasil kali mengambil 36 dan membuang bagian yang habis dibagi setiap faktor primanya. Kalikan dengan (1 − 1/2) untuk menghapus bilangan genap dan dengan (1 − 1/3) untuk menghapus kelipatan 3, dan meja kerja memperlihatkan 12. Karena 36 = 2²·3², hanya kedua prima inilah yang dapat membaginya.
Tautan kedua menghitung hal yang sama secara berbeda dengan inklusi-eksklusi: delapan belas kelipatan 2, dua belas kelipatan 3, dan enam kelipatan 6 yang ditambahkan kembali sekali karena telah dikurangi dua kali. 36 − 18 − 12 + 6 = 12. Kedua resep harus cocok, dan cocok karena habis dibagi 2 atau 3 persis berarti tidak saling prima dengan 36. φ adalah bilangan yang membuat aritmetika RSA bekerja. Teorema Euler menyatakan a^φ(n) ≡ 1 (mod n) untuk setiap a yang saling prima dengan n, sehingga ukuran himpunan ini adalah ukuran periodenya.
Jawaban
12
Cara membacanya
36·(1 − 1/2)(1 − 1/3) di meja kerja. Tautan kedua ialah nilai yang dihitung dengan inklusi-eksklusi, dan yang ketiga faktorisasi 2²·3² yang memberi tahu prima mana yang dihitung.
Sumber
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
Kerjakan di kalkulator
Tautan ini membuka kalkulator yang tepat dengan angka soal ini sudah diketik. Baris di atas adalah yang seharusnya ditampilkan layar — periksa sendiri.