Isi

• Langkah
• Bagian 1 dari 3: Tes Kesederhanaan
• Bagian 2 dari 3: Cara Kerja Tes Kesederhanaan
• Bagian 3 dari 3: Menggunakan Teorema Sisa Cina
• Tips
• Apa yang kamu butuhkan

Bilangan prima adalah bilangan yang hanya habis dibagi oleh dirinya sendiri dan oleh 1. Semua bilangan lainnya disebut bilangan komposit. Ada banyak cara untuk menentukan apakah suatu bilangan prima, dan semuanya memiliki kelebihan dan kekurangannya masing-masing. Di satu sisi, beberapa metode sangat akurat, tetapi cukup rumit jika Anda berurusan dengan jumlah besar. Di sisi lain, ada cara yang jauh lebih cepat, tetapi dapat menyebabkan hasil yang salah. Pilihan metode yang sesuai tergantung pada seberapa besar angka yang Anda kerjakan.

Langkah

Bagian 1 dari 3: Tes Kesederhanaan

Catatan: dalam semua formula n menunjukkan nomor yang akan diperiksa.

1. 1 Pencacahan pembagi. Cukup untuk membagi n ke semua bilangan prima dari 2 ke nilai yang dibulatkan (${ gaya tampilan { persegi {n}}}$).
2. 2 teorema kecil Fermat. Peringatan: terkadang tes akan salah mengidentifikasi bilangan komposit sebagai bilangan prima, bahkan untuk semua nilai a.
   • Mari kita pilih bilangan bulat Sebuahsehingga 2 a n - 1.
   • Jika a (mod n) = a (mod n) maka bilangan tersebut kemungkinan adalah bilangan prima. Jika persamaan tidak terpenuhi, bilangan n adalah komposit.
   • Periksa kesetaraan yang diberikan untuk beberapa nilai Sebuahuntuk meningkatkan kemungkinan bahwa bilangan yang diuji memang prima.
3. 3 Tes Miller-Rabin. Peringatan: terkadang, meskipun jarang, untuk beberapa nilai a, tes akan salah mengidentifikasi bilangan komposit sebagai bilangan prima.
   • Tentukan besaran s dan d sedemikian rupa sehingga ${ gaya tampilan n-1 = 2 ^ {s} * d}$.
   • Pilih bilangan bulat Sebuah dalam kisaran 2 a n - 1.
   • Jika a = +1 (mod n) atau -1 (mod n), maka n mungkin prima. Dalam hal ini, pergi ke hasil tes. Jika kesetaraan tidak berlaku, lanjutkan ke langkah berikutnya.
   • Kuadratkan jawaban Anda (${ gaya tampilan a ^ {2d}}$). Jika Anda mendapatkan -1 (mod n), maka n mungkin adalah bilangan prima. Dalam hal ini, pergi ke hasil tes. Jika persamaan gagal, ulangi (${ gaya tampilan a ^ {4d}}$ dan seterusnya) sampai ${ gaya tampilan a ^ {2 ^ {s-1} d}}$.
   • Jika pada beberapa langkah setelah mengkuadratkan angka selain ${ gaya tampilan pm 1}$ (mod n), Anda mendapat +1 (mod n), jadi n adalah bilangan komposit. Jika ${ displaystyle a ^ {2 ^ {s-1} d} neq pm 1}$ (mod n), maka n bukan prima.
   • Hasil tes: jika n lulus tes, ulangi untuk nilai lain Sebuahuntuk meningkatkan rasa percaya diri.

Bagian 2 dari 3: Cara Kerja Tes Kesederhanaan

1. 1 Pencacahan pembagi. Menurut definisi, nomor n sederhana hanya jika tidak habis dibagi 2 dan bilangan bulat lainnya kecuali 1 dan dirinya sendiri. Rumus di atas memungkinkan Anda untuk menghapus langkah-langkah yang tidak perlu dan menghemat waktu: misalnya, setelah memeriksa apakah suatu bilangan habis dibagi 3, tidak perlu memeriksa apakah bilangan itu habis dibagi 9.
   • Fungsi lantai (x) membulatkan x ke bilangan bulat terdekat yang kurang dari atau sama dengan x.
2. 2 Pelajari tentang aritmatika modular. Operasi "x mod y" (mod adalah singkatan dari kata Latin "modulo", yaitu, "modul") berarti "bagi x dengan y dan temukan sisanya." Dengan kata lain, dalam aritmatika modular, setelah mencapai nilai tertentu, yang disebut modul, angka "berubah" menjadi nol lagi. Misalnya, jam menghitung mundur dengan modul 12: ini menunjukkan jam 10, 11 dan 12, lalu kembali ke 1.
   • Banyak kalkulator memiliki kunci mod. Akhir bagian ini menunjukkan cara menghitung fungsi ini secara manual untuk jumlah besar.
3. 3 Pelajari tentang perangkap Teorema Kecil Fermat. Semua angka yang kondisi pengujiannya tidak terpenuhi adalah gabungan, tetapi angka lainnya hanya mungkin sederhana. Jika Anda ingin menghindari hasil yang salah, cari n dalam daftar "bilangan Carmichael" (bilangan komposit yang memenuhi tes ini) dan "bilangan pseudoprime Fermat" (angka-angka ini memenuhi kondisi pengujian hanya untuk beberapa nilai Sebuah).
4. 4 Jika nyaman, gunakan tes Miller-Rabin. Meskipun metode ini agak rumit untuk perhitungan manual, metode ini sering digunakan dalam program komputer. Ini memberikan kecepatan yang dapat diterima dan lebih sedikit kesalahan daripada metode Fermat. Bilangan komposit tidak akan dianggap sebagai bilangan prima jika perhitungan dilakukan lebih dari nilai Sebuah... Jika Anda secara acak memilih nilai yang berbeda Sebuah dan untuk semuanya tes akan memberikan hasil positif, kita dapat mengasumsikan dengan tingkat kepercayaan yang cukup tinggi bahwa n adalah bilangan prima.
5. 5 Untuk bilangan besar, gunakan aritmatika modular. Jika Anda tidak memiliki kalkulator mod, atau kalkulator tidak dirancang untuk menangani bilangan sebesar itu, gunakan properti daya dan aritmatika modular untuk mempermudah penghitungan. Di bawah ini adalah contoh untuk ${ gaya tampilan 3 ^ {50}}$ mod 50:
   • Tulis ulang ekspresi dalam bentuk yang lebih nyaman: ${ gaya tampilan (3 ^ {25} * 3 ^ {25})}$ mod 50. Perhitungan manual mungkin memerlukan penyederhanaan lebih lanjut.
   • ${ gaya tampilan (3 ^ {25} * 3 ^ {25})}$ mod 50 = ${ gaya tampilan (3 ^ {25}}$ mod 50 ${ gaya tampilan * 3 ^ {25}}$ mod 50) mod 50. Di sini kami memperhitungkan properti perkalian modular.
   • ${ gaya tampilan 3 ^ {25}}$ mod 50 = 43.
   • ${ gaya tampilan (3 ^ {25}}$ mod 50 ${ gaya tampilan * 3 ^ {25}}$ mod 50) mod 50 = ${ gaya tampilan (43 * 43)}$ mod 50.
   • ${ gaya tampilan = 1849}$ mod 50.
   • ${ gaya tampilan = 49}$.

Bagian 3 dari 3: Menggunakan Teorema Sisa Cina

1. 1 Pilih dua nomor. Salah satu angka harus komposit, dan yang lainnya harus persis seperti yang ingin Anda uji kesederhanaannya.
   • Nomor1 = 35
   • Nomor2 = 97
2. 2 Pilih dua nilai yang lebih besar dari nol dan, masing-masing, lebih kecil dari angka Number1 dan Number2. Nilai-nilai ini tidak boleh sama.
   • Nilai1 = 1
   • Nilai2 = 2
3. 3 Hitung MMI (Mathematical Multiplicative Inverse) untuk Angka1 dan Angka2.
   • Hitung MMI
     • MMI1 = Nomor2 ^ -1 Mod Nomor1
     • MMI2 = Nomor1 ^ -1 Mod Nomor2
   • Hanya untuk bilangan prima (ini akan memberikan nomor untuk bilangan komposit, tetapi itu bukan MMI-nya):
     • MMI1 = (Nomor2 ^ (Nomor1-2))% Nomor1
     • MMI2 = (Nomor1 ^ (Nomor2-2))% Nomor2
   • Sebagai contoh:
     • MMI1 = (97 ^ 33)% 35
     • MMI2 = (35 ^ 95)% 97
4. 4 Buat tabel untuk setiap MMI hingga modul log2:
   • Untuk MMI1
     • F (1) = Angka2% Angka1 = 97% 35 = 27
     • F (2) = F (1) * F (1)% Angka1 = 27 * 27% 35 = 29
     • F (4) = F (2) * F (2)% Angka1 = 29 * 29% 35 = 1
     • F (8) = F (4) * F (4)% Angka1 = 1 * 1% 35 = 1
     • F (16) = F (8) * F (8)% Angka1 = 1 * 1% 35 = 1
     • F (32) = F (16) * F (16)% Angka1 = 1 * 1% 35 = 1
   • Hitung Angka Berpasangan 1 - 2
     • 35 -2 = 33 (10001) basis 2
     • MMI1 = F (33) = F (32) * F (1) mod 35
     • MMI1 = F (33) = 1 * 27 mod 35
     • MMI1 = 27
   • Untuk MMI2
     • F (1) = Angka1% Angka2 = 35% 97 = 35
     • F (2) = F (1) * F (1)% Angka2 = 35 * 35 mod 97 = 61
     • F (4) = F (2) * F (2)% Angka2 = 61 * 61 mod 97 = 35
     • F (8) = F (4) * F (4)% Angka2 = 35 * 35 mod 97 = 61
     • F (16) = F (8) * F (8)% Angka2 = 61 * 61 mod 97 = 35
     • F (32) = F (16) * F (16)% Angka2 = 35 * 35 mod 97 = 61
     • F (64) = F (32) * F (32)% Angka2 = 61 * 61 mod 97 = 35
     • F (128) = F (64) * F (64)% Angka2 = 35 * 35 mod 97 = 61
   • Hitung Pasangan Angka 2 - 2
     • 97 - 2 = 95 = (1011111) basis 2
     • MMI2 = (((((F (64) * F (16)% 97) * F (8)% 97) * F (4)% 97) * F (2)% 97) * F (1)% 97)
     • MMI2 = (((((35 * 35)% 97) * 61)% 97) * 35% 97) * 61% 97) * 35% 97)
     • MMI2 = 61
5. 5 Hitung (Nilai1 * Angka2 * MMI1 + Nilai2 * Angka1 * MMI2)% (Nomor1 * Angka2)
   • Jawaban = (1 * 97 * 27 + 2 * 35 * 61)% (97 * 35)
   • Jawaban = (2619 + 4270)% 3395
   • Jawaban = 99
6. 6 Periksa bahwa Nomor1 bukan bilangan prima
   • Hitung (Jawaban - Nilai1)% Nomor1
   • 99 – 1 % 35 = 28
   • Karena 28 lebih besar dari 0, 35 bukan bilangan prima.
7. 7 Periksa apakah Angka2 adalah bilangan prima.
   • Hitung (Jawaban - Nilai2)% Nomor2
   • 99 – 2 % 97 = 0
   • Karena 0 adalah 0, 97 kemungkinan besar adalah bilangan prima.
8. 8 Ulangi langkah 1 sampai 7 setidaknya dua kali lagi.
   • Jika Anda mendapatkan 0 di langkah 7:
     • Gunakan Number1 yang berbeda jika Number1 bukan bilangan prima.
     • Gunakan Number1 lain jika Number1 prima. Dalam hal ini, Anda harus mendapatkan 0 di langkah 6 dan 7.
     • Gunakan Arti1 dan Arti2 yang berbeda.
   • Jika pada langkah 7 Anda secara konsisten mendapatkan 0, maka Nomor 2 sangat mungkin menjadi prima.
   • Langkah 1 hingga 7 dapat mengakibatkan kesalahan jika Angka1 bukan bilangan prima dan Angka2 adalah pembagi Angka1. Metode yang dijelaskan berfungsi dalam semua kasus ketika kedua bilangan prima.
   • Alasan Anda perlu mengulangi langkah 1 hingga 7 adalah karena dalam beberapa kasus, meskipun Angka1 dan Angka 2 bukan bilangan prima, pada langkah 7 Anda akan mendapatkan 0 (untuk satu atau kedua angka). Ini jarang terjadi.Pilih Angka1 lain (gabungan), dan jika Angka2 bukan bilangan prima, maka Angka2 tidak akan sama dengan nol pada langkah 7 (kecuali untuk kasus ketika Angka1 adalah pembagi Angka2 - di sini bilangan prima akan selalu sama dengan nol pada langkah 7).

Tips

• Bilangan prima dari 168 hingga 1000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79 , 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211 , 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359 , 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509 , 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673 , 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853 , 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997.
• Meskipun pengujian brute force adalah tes yang membosankan ketika bekerja dengan jumlah besar, itu cukup efisien untuk jumlah kecil. Bahkan dalam kasus bilangan besar, mulailah dengan menguji pembagi kecil, dan kemudian beralih ke metode yang lebih canggih untuk memeriksa kesederhanaan bilangan (jika pembagi kecil tidak ditemukan).

Apa yang kamu butuhkan

• Kertas, pena atau komputer