φ(n)
Faktor prima
Bagian relatif prima
Pembagi

          Tampilkan

          Selengkapnya tentang fungsi totient Euler

          Kalkulator totient Euler

          Dari bilangan 1 sampai 12, hanya 1, 5, 7, dan 11 yang tidak memiliki faktor persekutuan dengan 12, jadi φ(12) = 4. Fungsi totient Euler menghitung bilangan-bilangan relatif prima ini untuk setiap n. Masukkan bilangan hingga 10^18 untuk mendapatkan φ(n) beserta faktor primanya dan rumus perkalian yang dituliskan lengkap, melihat bilangan 1 sampai n dengan yang relatif prima disorot, memeriksa teorema Euler, menggambar φ(k) untuk hingga 100.000 bilangan sekaligus, atau menemukan setiap n dengan φ(n) tertentu. Masukkan bilangan bulat n hingga 10^18, atau pilih contoh soal. Kotak-kotak menampilkan φ(n), faktor prima n, bagian bilangan 1 sampai n yang relatif prima terhadap n, dan banyaknya pembagi, sedangkan langkah-langkahnya menuliskan rumus perkalian dengan bilangan Anda. Hingga n = 500, bilangan 1 sampai n digambar: yang relatif prima terhadap n diisi penuh, yang lain diberi warna bilangan prima terkecil yang mereka miliki bersama n. Arahkan penunjuk ke sebuah bilangan untuk melihat FPB-nya dengan n, dan klik untuk memakainya sebagai a dalam teorema Euler. Grafik menampilkan φ(k) untuk setiap k hingga batas tertentu; klik sebuah titik untuk membuka bilangan itu. Invers mendaftar setiap n dengan φ(n) = m; klik salah satunya untuk membukanya.

          Cara kerjanya

          1. Masukkan bilangan bulat n hingga 10^18, atau pilih contoh soal seperti φ(60), modulus RSA, atau bilangan Carmichael 561.
          2. Baca φ(n), faktor prima, dan rumus perkalian dengan bilangan Anda. Hingga 500, arahkan penunjuk ke bilangan 1 sampai n untuk melihat FPB-nya dengan n, dan klik salah satunya untuk memeriksa teorema Euler dengan bilangan itu.
          3. Beralih ke Grafik untuk melihat φ(k) untuk setiap k hingga 100.000, atau ke Invers untuk mendaftar setiap n dengan φ(n) = m.

          Cara menghitung φ(n)

          Faktorkan n menjadi bilangan prima dan kalikan n dengan (1 − 1/p) untuk setiap bilangan prima p yang membaginya. Untuk 60 = 2² × 3 × 5 hasilnya 60 × 1/2 × 2/3 × 4/5 = 16. Mencoret memberikan jumlah yang sama: dari 60 bilangan, 30 genap; dari 30 yang ganjil, 10 adalah kelipatan 3; dari 20 yang tersisa, 4 adalah kelipatan 5, sehingga tersisa 16. Untuk perpangkatan bilangan prima, rumusnya φ(p^k) = p^(k−1)(p − 1), dan nilai-nilainya dikalikan: φ(60) = 2 × 2 × 4. Bagian yang sulit adalah pemfaktorannya. Kalkulator ini memakai pembagian percobaan, uji keprimaan Miller–Rabin, dan metode rho Pollard, sehingga bahkan hasil kali 18 digit dari dua bilangan prima 9 digit hanya butuh sepersekian detik.

          Di mana totient dipakai

          φ(n) menghitung pecahan k/n antara 0 dan 1 yang sudah dalam bentuk paling sederhana, panjang langkah yang membawa jarum melewati setiap jam pada jam dengan n jam (1, 5, 7, dan 11 pada jam 12 jam), dan bilangan yang memiliki invers modulo n. Euler membuktikan bahwa a^φ(n) ≡ 1 (mod n) untuk setiap a yang relatif prima terhadap n, dan enkripsi RSA bertumpu pada hal itu: dengan n = 3233 = 61 × 53, φ(n) = 60 × 52 = 3.120, dan eksponen publik 17 memiliki pasangan privat 2.753, karena 17 × 2.753 = 15 × 3.120 + 1.

          Pertanyaan yang sering diajukan

          Apa itu fungsi totient Euler?

          φ(n) adalah banyaknya bilangan bulat dari 1 sampai n yang tidak memiliki faktor persekutuan dengan n selain 1. φ(9) = 6, karena 1, 2, 4, 5, 7, dan 8 relatif prima terhadap 9, sedangkan 3, 6, dan 9 berbagi faktor 3. Menurut kesepakatan, φ(1) = 1. Euler mempelajari fungsi ini pada tahun 1760-an; Gauss memberinya simbol φ pada 1801, dan James Joseph Sylvester nama Inggris totient pada 1879.

          Berapa φ dari bilangan prima?

          p − 1, karena setiap bilangan dari 1 sampai p − 1 relatif prima terhadap bilangan prima p, jadi φ(97) = 96. Untuk perpangkatan bilangan prima, φ(p^k) = p^k − p^(k−1), karena hanya kelipatan p yang memiliki faktor persekutuan dengannya: φ(81) = 81 − 27 = 54.

          Apa isi teorema Euler?

          Jika a dan n relatif prima, maka a^φ(n) bersisa 1 bila dibagi n. Untuk n = 60 dan a = 7: φ(60) = 16, dan 7^16 ≡ 1 (mod 60). Teorema kecil Fermat adalah kasus n prima. Sering kali eksponen yang lebih kecil sudah cukup: 7^4 = 2.401 = 40 × 60 + 1. Eksponen terkecil yang berlaku untuk setiap a yang relatif prima terhadap n adalah fungsi Carmichael λ(n), yang untuk 60 bernilai 4.

          Bisakah dua bilangan memiliki totient yang sama?

          Bisa, dan biasanya ada beberapa: φ(n) = 24 untuk n = 35, 39, 45, 52, 56, 70, 72, 78, 84, dan 90. Beberapa bilangan genap tidak pernah menjadi nilai φ, yang terkecil adalah 14, dan tidak ada bilangan ganjil di atas 1 yang menjadi nilainya, karena φ(n) genap mulai dari n = 3. Robert Carmichael menyatakan pada 1907 bahwa tidak ada nilai yang muncul tepat satu kali. Hal itu masih belum terbukti, dan Kevin Ford menunjukkan pada 1998 bahwa pengecualian mana pun harus lebih besar dari 10^(10^10).

          Seberapa besar bilangan yang bisa saya masukkan?

          Bilangan bulat apa pun hingga 10^18. Kalkulator memfaktorkannya dengan aritmetika bilangan bulat yang tepat di peramban Anda, sehingga φ(10^18) = 4 × 10^17 dan φ(999.999.866.000.004.473) = 999.999.864.000.004.608 tepat sampai digit terakhir. Bilangan 1 sampai n digambar hingga 500, grafik mencapai 100.000, dan invers berlaku untuk nilai hingga 10^10.

          Siap mencobanya?

          Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

          Ke Editor