Anda Tidak Akan Percaya! Ini Dia Cara Mudah Mencari Bilangan Prima Tanpa Kalkulator!

Ini Dia Cara Mudah Mencari Bilangan Prima Tanpa Kalkulator! – Tahukah anda sobat Antrakasa, bahwa Bilangan prima adalah bilangan asli yang hanya bisa dibagi oleh 1 dan dirinya sendiri. Contoh bilangan prima antara 1 sampai 100 adalah 2, 3, 5, 7, 11, 13, 17, 19, 23, dan seterusnya. Bilangan prima memiliki banyak kegunaan dalam matematika dan teknologi. Misalnya, bilangan prima digunakan untuk menyederhanakan pecahan, menentukan FPB dan KPK, membuat algoritma komputer, dan mengacak kunci dalam sistem enkripsi.

Namun, bagaimana cara menentukan bilangan prima dengan mudah tanpa menggunakan kalkulator? Apakah ada trik atau rumus yang bisa kita gunakan? Jawabannya adalah ada! Berikut ini adalah 10 cara mudah mencari bilangan prima tanpa kalkulator yang bisa Anda coba sendiri.

1. Menggunakan Faktor Bilangan

Cara paling sederhana untuk menentukan bilangan prima adalah dengan menggunakan faktor bilangan. Faktor bilangan adalah bilangan yang bisa habis membagi suatu bilangan. Jika suatu bilangan hanya memiliki dua faktor bilangan, yaitu 1 dan dirinya sendiri, maka bilangan tersebut adalah bilangan prima. Sebaliknya, jika suatu bilangan memiliki lebih dari dua faktor bilangan, maka bilangan tersebut adalah bilangan komposit.

Contoh: Apakah 17 adalah bilangan prima?

Cara menentukan faktor bilangan 17 adalah dengan mencoba membagi 17 dengan semua bilangan asli yang lebih kecil dari atau sama dengan 17. Jika hasil pembagian tersebut tidak ada yang menghasilkan sisa nol (bulat), maka 17 adalah bilangan prima.

17 : 1 = 17 (bulat)

17 : 2 = 8.5 (tidak bulat)

17 : 3 = 5.67 (tidak bulat)

17 : 4 = 4.25 (tidak bulat)

17 : 5 = 3.4 (tidak bulat)

17 : 6 = 2.83 (tidak bulat)

17 : 7 = 2.43 (tidak bulat)

17 : 8 = 2.13 (tidak bulat)

17 : 9 = 1.89 (tidak bulat)

17 : 10 = 1.7 (tidak bulat)

17 : 11 = 1.55 (tidak bulat)

17 : 12 = 1.42 (tidak bulat)

17 : 13 = 1.31 (tidak bulat)

17 : 14 = 1.21 (tidak bulat)

17 : 15 = 1.13 (tidak bulat)

17 : 16 = 1.06 (tidak bulat)

17 : 17 = 1 (bulat)

Dari hasil pembagian di atas, kita bisa melihat bahwa hanya ada dua hasil yang menghasilkan sisa nol (bulat), yaitu ketika membagi dengan angka 1 dan 17. Ini berarti bahwa faktor bilangan 17 adalah 1 dan 17. Karena hanya ada dua faktor bilangan, maka 17 adalah bilangan prima.

2. Menggunakan Sifat Bilangan Prima

Cara lain untuk menentukan bilangan prima adalah dengan menggunakan sifat bilangan prima. Sifat bilangan prima adalah sebagai berikut:

  • Bilangan prima selalu lebih besar dari 1.
  • Bilangan prima selalu ganjil, kecuali angka 2.
  • Bilangan prima selalu tidak habis dibagi oleh bilangan genap, kecuali angka 2.
  • Bilangan prima selalu tidak habis dibagi oleh bilangan kelipatan 5, kecuali angka 5.
  • Bilangan prima selalu memiliki jumlah digit yang ganjil, kecuali angka 2 dan 5.

Contoh: Apakah 31 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan sifat bilangan prima adalah dengan memeriksa apakah bilangan tersebut memenuhi sifat-sifat di atas. Jika ya, maka bilangan tersebut kemungkinan besar adalah bilangan prima. Jika tidak, maka bilangan tersebut pasti bukan bilangan prima.

31 > 1 (memenuhi)

31 ganjil (memenuhi)

31 tidak habis dibagi oleh bilangan genap (memenuhi)

31 tidak habis dibagi oleh bilangan kelipatan 5 (memenuhi)

31 memiliki jumlah digit yang ganjil (memenuhi)

Dari pemeriksaan di atas, kita bisa melihat bahwa 31 memenuhi semua sifat bilangan prima. Ini berarti bahwa 31 kemungkinan besar adalah bilangan prima. Untuk memastikannya, kita bisa mencoba membagi 31 dengan beberapa bilangan prima yang lebih kecil dari akar kuadrat dari 31. Jika tidak ada yang habis membaginya, maka 31 adalah bilangan prima.

Akar kuadrat dari 31 adalah sekitar 5.57. Bilangan prima yang lebih kecil dari akar kuadrat dari 31 adalah 2, 3, dan 5. Kita coba membagi 31 dengan ketiga bilangan tersebut.

31 : 2 = 15.5 (tidak bulat)

31 : 3 = 10.33 (tidak bulat)

31 : 5 = 6.2 (tidak bulat)

Dari hasil pembagian di atas, kita bisa melihat bahwa tidak ada yang habis membagi 31. Ini berarti bahwa 31 adalah bilangan prima.

3. Menggunakan Saringan Eratosthenes

Saringan Eratosthenes adalah salah satu metode klasik untuk mencari bilangan prima dalam suatu rentang tertentu. Metode ini ditemukan oleh seorang matematikawan Yunani bernama Eratosthenes pada abad ke-3 SM. Cara kerja metode ini adalah dengan menyaring atau mengeliminasi semua bilangan komposit dalam rentang tersebut dan menyisakan hanya bilangan prima saja.

Cara menggunakan saringan Eratosthenes adalah sebagai berikut:

  1. Tulis semua bilangan asli mulai dari 2 sampai batas atas rentang yang ditentukan.
  2. Pilih bilangan terkecil yang belum disaring (awalnya adalah angka 2 dan tandai sebagai bilangan prima.
  3. Coret semua kelipatan dari bilangan yang dipilih tersebut.
  4. Ulangi langkah 2 dan 3 sampai tidak ada lagi bilangan yang bisa dipilih atau dicoret.
  5. Bilangan yang tidak dicoret adalah bilangan prima dalam rentang tersebut.

Contoh: Cari semua bilangan prima antara 1 sampai 50 dengan menggunakan saringan Eratosthenes.

Cara menggunakan saringan Eratosthenes untuk mencari bilangan prima antara 1 sampai 50 adalah sebagai berikut:

  1. Tulis semua bilangan asli mulai dari 2 sampai 50. Angka 1 tidak ditulis karena bukan bilangan prima.
  2. Pilih bilangan terkecil yang belum disaring, yaitu angka 2, dan tandai sebagai bilangan prima.
  3. Coret semua kelipatan dari angka 2, yaitu 4, 6, 8, 10, …, sampai 50.
  4. Pilih bilangan terkecil yang belum disaring, yaitu angka 3, dan tandai sebagai bilangan prima.
  5. Coret semua kelipatan dari angka 3, yaitu 6, 9, 12, 15, …, sampai 48.
  6. Pilih bilangan terkecil yang belum disaring, yaitu angka 5, dan tandai sebagai bilangan prima.
  7. Coret semua kelipatan dari angka 5, yaitu 10, 15, 20, 25, …, sampai 50.
  8. Pilih bilangan terkecil yang belum disaring, yaitu angka 7, dan tandai sebagai bilangan prima.
  9. Coret semua kelipatan dari angka 7, yaitu 14, 21, 28, 35, …, sampai 49.
  10. Tidak ada lagi bilangan yang bisa dipilih atau dicoret. Bilangan yang tidak dicoret adalah bilangan prima dalam rentang tersebut.

Bilangan prima antara 1 sampai 50 adalah: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, dan 47.

4. Menggunakan Rumus Bilangan Prima

Rumus bilangan prima adalah suatu rumus matematika yang bisa menghasilkan bilangan prima jika kita memasukkan nilai tertentu ke dalamnya. Rumus bilangan prima bisa membantu kita untuk mencari bilangan prima tanpa harus melakukan pembagian atau penyaringan. Namun, rumus bilangan prima biasanya hanya berlaku untuk rentang nilai tertentu dan tidak selalu menghasilkan bilangan prima untuk setiap nilai yang dimasukkan.

Contoh: Rumus n2+n+41 adalah salah satu rumus bilangan prima yang ditemukan oleh matematikawan bernama Leonhard Euler. Rumus ini bisa menghasilkan bilangan prima jika kita memasukkan nilai n antara -40 sampai +39. Jika kita memasukkan nilai n di luar rentang tersebut, maka rumus ini tidak selalu menghasilkan bilangan prima.

Misalnya:

Jika n = -40 maka n2+n+41 = (-40)2+(-40)+41 = (1600)+(-40)+41 = (1601)+41 = (1642) bukan bilangan prima.

Jika n = -39 maka n2+n+41 = (-39)2+(-39)+41 = (1521)+(-39)+41 = (1482)+41 = (1523) adalah bilangan prima.

Jika n = – 38 maka n2+n+41 = (-38)2+(-38)+41 = (1444)+(-38)+41 = (1406)+41 = (1447) adalah bilangan prima.

Jika n = -37 maka n2+n+41 = (-37)2+(-37)+41 = (1369)+(-37)+41 = (1332)+41 = (1373) adalah bilangan prima.

…

Jika n = 37 maka n2+n+41 = (37)2+(37)+41 = (1369)+(37)+41 = (1406)+41 = (1447) adalah bilangan prima.

Jika n = 38 maka n2+n+41 = (38)2+(38)+41 = (1444)+(38)+41 = (1482)+41 = (1523) adalah bilangan prima.

Jika n = 39 maka n2+n+41 = (39)2+(39)+41 = (1521)+(39)+41 = (1560)+41 = (1601) bukan bilangan prima.

Jika n = 40 maka n2+n+41 = (40)2+(40)+41 = (1600)+(40)+41 = (1640)+41 = (1681) bukan bilangan prima.

5. Menggunakan Rumus Wilson

Rumus Wilson adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima dengan menggunakan konsep faktorial. Faktorial adalah hasil perkalian dari suatu bilangan asli dengan semua bilangan asli yang lebih kecil darinya. Faktorial ditulis dengan tanda seru (!) di belakang bilangan tersebut. Contoh: 5! = 5 x 4 x 3 x 2 x 1 = 120.

Rumus Wilson berbunyi sebagai berikut: Jika p adalah bilangan prima, maka (p-1)! + 1 habis dibagi oleh p. Sebaliknya, jika p bukan bilangan prima, maka (p-1)! + 1 tidak habis dibagi oleh p.

Contoh: Apakah 13 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus Wilson adalah dengan menghitung nilai dari (p-1)! + 1 dan membaginya dengan p. Jika hasil pembagian tersebut menghasilkan sisa nol, maka p adalah bilangan prima. Jika tidak, maka p bukan bilangan prima.

(13-1)! + 1 = 12! + 1

= 12 x 11 x 10 x … x 3 x 2 x 1 + 1

= 479001600 + 1

= 479001601

479001601 : 13 = 36846277 (bulat)

Dari hasil perhitungan di atas, kita bisa melihat bahwa (13-1)! + 1 habis dibagi oleh 13. Ini berarti bahwa 13 adalah bilangan prima.

6. Menggunakan Rumus Fermat

Rumus Fermat adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima dengan menggunakan konsep pangkat. Pangkat adalah hasil perkalian dari suatu bilangan dengan dirinya sendiri sebanyak beberapa kali. Pangkat ditulis dengan tanda pangkat (^) di belakang bilangan tersebut. Contoh: 34 = 3 x 3 x 38 maka n2+n+41 = (-38)2+(-38)+41 = (1444)+(-38)+41 = (1406)+41 = (1447) adalah bilangan prima.

Jika n = -37 maka n2+n+41 = (-37)2+(-37)+41 = (1369)+(-37)+41 = (1332)+41 = (1373) adalah bilangan prima.

…

Jika n = 37 maka n2+n+41 = (37)2+(37)+41 = (1369)+(37)+41 = (1406)+41 = (1447) adalah bilangan prima.

Jika n = 38 maka n2+n+41 = (38)2+(38)+41 = (1444)+(38)+41 = (1482)+41 = (1523) adalah bilangan prima.

Jika n = 39 maka n2+n+41 = (39)2+(39)+41 = (1521)+(39)+41 = (1560)+41 = (1601) bukan bilangan prima.

Jika n = 40 maka n2+n+41 = (40)2+(40)+41 = (1600)+(40)+41 = (1640)+41 = (1681) bukan bilangan prima.

5. Menggunakan Rumus Wilson

Rumus Wilson adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima dengan menggunakan konsep faktorial. Faktorial adalah hasil perkalian dari suatu bilangan asli dengan semua bilangan asli yang lebih kecil darinya. Faktorial ditulis dengan tanda seru (!) di belakang bilangan tersebut. Contoh: 5! = 5 x 4 x 3 x 2 x 1 = 120.

Rumus Wilson berbunyi sebagai berikut: Jika p adalah bilangan prima, maka (p-1)! + 1 habis dibagi oleh p. Sebaliknya, jika p bukan bilangan prima, maka (p-1)! + 1 tidak habis dibagi oleh p.

Contoh: Apakah 13 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus Wilson adalah dengan menghitung nilai dari (p-1)! + 1 dan membaginya dengan p. Jika hasil pembagian tersebut menghasilkan sisa nol, maka p adalah bilangan prima. Jika tidak, maka p bukan bilangan prima.

(13-1)! + 1 = 12! + 1

= 12 x 11 x 10 x … x 3 x 2 x 1 + 1

= 479001600 + 1

= 479001601

479001601 : 13 = 36846277 (bulat)

Dari hasil perhitungan di atas, kita bisa melihat bahwa (13-1)! + 1 habis dibagi oleh 13. Ini berarti bahwa 13 adalah bilangan prima.

6. Menggunakan Rumus Fermat

Rumus Fermat adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima dengan menggunakan konsep pangkat. Pangkat adalah hasil perkalian dari suatu bilangan dengan dirinya sendiri sebanyak beberapa kali. Pangkat ditulis dengan tanda pangkat (^) di belakang bilangan tersebut. Contoh: 34 = 3 x 3 x 3 x 3 = 81.

Rumus Fermat berbunyi sebagai berikut: Jika p adalah bilangan prima dan a adalah bilangan asli yang tidak habis dibagi oleh p, maka ap-1 – 1 habis dibagi oleh p. Sebaliknya, jika p bukan bilangan prima, maka ap-1 – 1 tidak habis dibagi oleh p.

Contoh: Apakah 11 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus Fermat adalah dengan memilih suatu bilangan asli a yang tidak habis dibagi oleh p, lalu menghitung nilai dari ap-1 – 1 dan membaginya dengan p. Jika hasil pembagian tersebut menghasilkan sisa nol, maka p adalah bilangan prima. Jika tidak, maka p bukan bilangan prima.

Misalnya kita memilih a = 2. Kita periksa apakah 2 habis dibagi oleh 11. Ternyata tidak, karena 11 : 2 = 5.5. Ini berarti bahwa kita bisa menggunakan a = 2 untuk rumus Fermat.

211-1 – 1 = 210 – 1

= 1024 – 1

= 1023

1023 : 11 = 93 (bulat)

Dari hasil perhitungan di atas, kita bisa melihat bahwa 211-1 – 1 habis dibagi oleh 11. Ini berarti bahwa 11 adalah bilangan prima.

7. Menggunakan Rumus Mersenne

Rumus Mersenne adalah suatu rumus matematika yang bisa digunakan untuk mencari bilangan prima dengan menggunakan konsep pangkat dua. Pangkat dua adalah hasil perkalian dari suatu bilangan dengan dirinya sendiri. Pangkat dua ditulis dengan tanda pangkat (^) di belakang bilangan tersebut dan nilai pangkatnya adalah dua. Contoh: 52 = 5 x 5 = 25.

Rumus Mersenne berbunyi sebagai berikut: Jika n adalah bilangan asli dan Mn = 2n – 1 adalah bilangan prima, maka n juga harus bilangan prima. Sebaliknya, jika n bukan bilangan prima, maka Mn juga bukan bilangan prima.

Contoh: Apakah M7 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus Mersenne adalah dengan menghitung nilai dari Mn dan memeriksa apakah n adalah bilangan prima atau bukan. Jika n adalah bilangan prima dan Mn juga bilangan prima, maka Mn adalah bilangan prima Mersenne. Jika n bukan bilangan prima atau Mn bukan bilangan prima, maka Mn bukan bilangan prima Mersenne.

M7 = 27 – 1

= 128 – 1

= 127

Kita periksa apakah n = 7 adalah bilangan prima atau bukan. Kita bisa menggunakan salah satu cara yang sudah dijelaskan sebelumnya, misalnya dengan menggunakan faktor bilangan. Jika kita mencoba membagi 7 dengan semua bilangan asli yang lebih kecil dari atau sama dengan 7, kita akan mendapatkan hasil sebagai berikut:

7 : 1 = 7 (bulat)

7 : 2 = 3.5 (tidak bulat)

7 : 3 = 2.33 (tidak bulat)

7 : 4 = 1.75 (tidak bulat)

7 : 5 = 1.4 (tidak bulat)

7 : 6 = 1.17 (tidak bulat)

7 : 7 = 1 (bulat)

Dari hasil pembagian di atas, kita bisa melihat bahwa hanya ada dua hasil yang menghasilkan sisa nol (bulat), yaitu ketika membagi dengan angka 1 dan 7. Ini berarti bahwa faktor bilangan 7 adalah 1 dan 7. Karena hanya ada dua faktor bilangan, maka 7 adalah bilangan prima.

Kemudian kita periksa apakah M7 = 127 adalah bilangan prima atau bukan. Kita bisa menggunakan salah satu cara yang sudah dijelaskan sebelumnya, misalnya dengan menggunakan sifat bilangan prima. Jika kita memeriksa sifat-sifat bilangan prima pada angka 127, kita akan mendapatkan hasil sebagai berikut:

127 > 1 (memenuhi)

127 ganjil (memenuhi)

127 tidak habis dibagi oleh bilangan genap (memenuhi)

127 tidak habis dibagi oleh bilangan kelipatan 5 (memenuhi)

127 memiliki jumlah digit yang ganjil (memenuhi)

Dari pemeriksaan di atas, kita bisa melihat bahwa 127 memenuhi semua sifat bilangan prima. Ini berarti bahwa 127 kemungkinan besar adalah bilangan prima. Untuk memastikannya, kita bisa mencoba membagi 127 dengan beberapa bilangan prima yang lebih kecil dari akar kuadrat dari 127. Jika tidak ada yang habis membaginya, maka 127 adalah bilangan prima.

Akar kuadrat dari 127 adalah sekitar 11.27. Bilangan prima yang lebih kecil dari akar kuadrat dari 127 adalah 2, 3, 5, dan 7 Kita coba membagi 127 dengan keempat bilangan tersebut.

127 : 2 = 63.5 (tidak bulat)

127 : 3 = 42.33 (tidak bulat)

127 : 5 = 25.4 (tidak bulat)

127 : 7 = 18.14 (tidak bulat)

Dari hasil pembagian di atas, kita bisa melihat bahwa tidak ada yang habis membagi 127. Ini berarti bahwa 127 adalah bilangan prima.

Karena n = 7 adalah bilangan prima dan M7 = 127 juga bilangan prima, maka M7 adalah bilangan prima Mersenne.

8. Menggunakan Rumus Lucas-Lehmer

Rumus Lucas-Lehmer adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima Mersenne dengan menggunakan konsep deret. Deret adalah susunan angka yang memiliki pola tertentu. Contoh: Deret ganjil adalah 1, 3, 5, 7, …, dan seterusnya.

Rumus Lucas-Lehmer berbunyi sebagai berikut: Jika p adalah bilangan prima lebih besar dari 2 dan Mp = 2p – 1 adalah bilangan prima Mersenne, maka Mp habis dibagi oleh Sp-1, di mana Sp-1 adalah suku ke-(p-1) dari deret Lucas-Lehmer yang didefinisikan sebagai berikut:

  • S0 = 4
  • Sn+1 = Sn2 – 2 untuk n > 0

Contoh: Apakah M5 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus Lucas-Lehmer adalah dengan menghitung nilai dari Mp dan Sp-1, lalu memeriksa apakah Mp habis dibagi oleh Sp-1. Jika ya, maka Mp adalah bilangan prima Mersenne. Jika tidak, maka Mp bukan bilangan prima Mersenne.

M5 = 25 – 1

= 32 – 1

= 31

Suku pertama dari deret Lucas-Lehmer adalah S0 = 4.

Suku kedua dari deret Lucas-Lehmer adalah S1 = S02 – 2 = (4)2 – 2 = (16) – 2 = (14).

Suku ketiga dari deret Lucas-Lehmer adalah S2 = S12 – 2 = (14)2 2 = (196) – 2 = (194).

Suku keempat dari deret Lucas-Lehmer adalah S3 = S22 – 2 = (194)2 – 2 = (37636) – 2 = (37634).

Karena p = 5, maka kita perlu mencari suku ke-(p-1) dari deret Lucas-Lehmer, yaitu S4.

Suku kelima dari deret Lucas-Lehmer adalah S4 = S32 – 2 = (37634)2 – 2 = (1416317954) – 2 = (1416317952).

Kita periksa apakah M5 = 31 habis dibagi oleh S4 = 1416317952.

1416317952 : 31 = 45687676.84 (tidak bulat)

Dari hasil perhitungan di atas, kita bisa melihat bahwa M5 tidak habis dibagi oleh S4. Ini berarti bahwa M5 bukan bilangan prima Mersenne.

9. Menggunakan Rumus Miller-Rabin

Rumus Miller-Rabin adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima dengan menggunakan konsep modular. Modular adalah sisa hasil pembagian dari suatu bilangan dengan bilangan lain. Modular ditulis dengan tanda persen (%) di antara dua bilangan tersebut. Contoh: 7 % 3 = 1, karena 7 : 3 = 2 sisa 1.

Rumus Miller-Rabin berbunyi sebagai berikut: Jika p adalah bilangan prima ganjil lebih besar dari 3 dan p-1 dapat ditulis sebagai d x 2r, di mana d adalah bilangan ganjil dan r adalah bilangan asli, maka untuk setiap a yang tidak habis dibagi oleh p dan lebih kecil dari p, salah satu dari dua kondisi berikut harus terpenuhi:

  • ad % p = 1, atau
  • ad x 2k % p = -1 untuk setiap k antara 0 sampai r-1.

Jika kedua kondisi tersebut tidak terpenuhi untuk suatu a tertentu, maka p pasti bukan bilangan prima. Jika kedua kondisi tersebut terpenuhi untuk semua a yang dicoba, maka p kemungkinan besar adalah bilangan prima.

Contoh: Apakah 17 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus Miller-Rabin adalah dengan menghitung nilai dari d dan r, lalu memilih suatu bilangan a yang tidak habis dibagi oleh p dan lebih kecil dari p, kemudian memeriksa apakah salah satu dari dua kondisi tersebut terpenuhi. Jika tidak, maka p bukan bilangan prima. Jika ya, maka p kemungkinan besar adalah bilangan prima.

p-1 = 17-1 = 16

d x 2r = 16

d = 1 dan r = 4

Misalnya kita memilih a = 2. Kita periksa apakah 2 habis dibagi oleh 17. Ternyata tidak, karena 17 : 2 = 8.5. Ini berarti bahwa kita bisa menggunakan a = 2 untuk rumus Miller-Rabin.

Kita periksa apakah kondisi pertama terpenuhi.

ad % p = 21 % 17

= 2 % 17

= 2

Karena 2 tidak sama dengan 1, maka kondisi pertama tidak terpenuhi.

Kita periksa apakah kondisi kedua terpenuhi.

ad x 2k % p = -1 untuk setiap k antara 0 sampai r-1.

Karena r = 4, maka k antara 0 sampai 3. Kita coba untuk setiap nilai k.

Jika k = 0, maka ad x 2k % p = ad x 20 % p = ad x 1 % p = ad % p = 21 % 17 = (2) % 17 = (2). Karena 2 tidak sama dengan -1, maka kondisi kedua tidak terpenuhi untuk k = 0.

Jika k = 1, maka ad x 2k % p = ad x 21 % p = ad x 2 % p = a2d % p = 22 % 17 = (4) % 17 = (4). Karena 4 tidak sama dengan -1, maka kondisi kedua tidak terpenuhi untuk k = 1.

Jika k = 2, maka ad x 2k % p = ad x 22 % p = ad x 4 % p = a4d % p = 24 % 17 = (16) % 17 = (16). Karena 16 tidak sama dengan -1, maka kondisi kedua tidak terpenuhi untuk k = 2.

Jika k = 3, maka ad x 2k % p = ad x 23 % p = ad x 8 % p = a8d % p = 28 % 17 = (256) % 17 = (-1). Karena -1 sama dengan -1, maka kondisi kedua terpenuhi untuk k = 3.

Karena salah satu dari dua kondisi tersebut terpenuhi untuk a = 2, maka 17 kemungkinan besar adalah bilangan prima.

10. Menggunakan Rumus AKS

Rumus AKS adalah suatu rumus matematika yang bisa digunakan untuk menentukan bilangan prima dengan menggunakan konsep binomial. Binomial adalah suatu bentuk aljabar yang terdiri dari dua suku yang dipisahkan oleh tanda tambah (+) atau kurang (-). Contoh: (x + y) dan (a – b) adalah binomial.

Rumus AKS berbunyi sebagai berikut: Jika p adalah bilangan prima ganjil lebih besar dari 3 dan n adalah bilangan asli yang tidak habis dibagi oleh p, maka (x + n)p – (xp + n) habis dibagi oleh p. Sebaliknya, jika p bukan bilangan prima, maka (x + n)p – (xp + n) tidak habis dibagi oleh p.

Contoh: Apakah 19 adalah bilangan prima?

Cara menentukan bilangan prima dengan menggunakan rumus AKS adalah dengan memilih suatu bilangan asli n yang tidak habis dibagi oleh p, lalu menghitung nilai dari (x + n)p – (xp + n) dan memeriksa apakah hasilnya habis dibagi oleh p. Jika ya, maka p adalah bilangan prima. Jika tidak, maka p bukan bilangan prima.

Misalnya kita memilih n = 3. Kita periksa apakah 3 habis dibagi oleh 19. Ternyata tidak, karena 19 : 3 = 6.33. Ini berarti bahwa kita bisa menggunakan n = 3 untuk rumus AKS.

Kita hitung nilai dari (x + n)p – (xp + n).

(x + 3)19 – (x19 + 3)

= x19 + 57x18 + 912x17 + … + 912x2 + 57x + 3 – (x19 + 3)

= x19 + 57x18 + 912x17 + … + 912x2 + 57x – x19

= 57x18 + 912x17 + … + 912x2 + 57x

Kita periksa apakah hasilnya habis dibagi oleh p = 19.

(57x18 + 912x17 + … + 912x2 + 57x) : 19 = (3x18 + 48x17 + … + 48x2 + 3x) (bulat)

Dari hasil perhitungan di atas, kita bisa melihat bahwa (x + n)p – (xp + n) habis dibagi oleh p. Ini berarti bahwa p adalah bilangan prima.

Akhir Kata

Bilangan prima adalah bilangan yang menarik dan bermanfaat untuk dipelajari. Ada banyak cara untuk mencari bilangan prima tanpa kalkulator, baik dengan menggunakan logika, sifat-sifat, rumus-rumus, atau metode-metode matematika lainnya. Semoga artikel ini bisa membantu Anda untuk lebih memahami bilangan prima dan cara mencari bilangan prima dengan mudah tanpa kalkulator.

Scroll to Top