Soal dan Pembahasan Olimpiade Matematika: Bilangan Prima

Bilangan prima adalah bilangan asli lebih besar dari 1 dan jika dan hanya jika pembagi positif dari bilangan itu hanya bilangan itu sendiri dan bilangan 1.
Bisa juga dikatakan bahwa bilangan prima adalah bilangan yang habis dibagi plus minus dirinya sendiri dan plus minus 1. Misalnya 37. 37 hanya habis dibagi plus minus dirinya sendiri dan habis dibagi plus minus 1. Bilangan prima yang pertama adalah : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, …
Dalam bentuk tabel semua bilangan prima dari 1 sampai 100 bisa kita tuliskan sebagai berikut :

$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$

Bilangan prima tersebut hanya satu yang merupakan bilangan genap, yaitu $2$ . Karena bilangan genap selanjutnya merupakan bilangan kelipatan $2$ , sehingga bilangan genap selain $2$ adalah bilangan komposit

Sifat-sifat yang cukup penting berhubungan dengan bilangan prima.

Semua bilangan prima adalah ganjil kecuali 2.
Banyaknya bilangan prima adalah tak terhingga.
Bilangan yang berakhiran (angka satuannya) 2, 4, 5, 6, 8, dan 0 adalah bukan bilangan prima. kecuali bilangan 2 dan 5.
Teorema Hadamard Poussin mengatakan bahwa, Banyaknya bilangan prima untuk x mendekati tak terhingga dinyatakan dengan pendekatan mendekati $\frac{x}{ln \, x}$

Dari sifat nomor 1 dikatakan bahwa semua bilangan prima adalah ganjil kecuali 2.
Dua bilangan prima yang ganjil yang berurutan disebut bilangan prima kembar.
Bisa dituliskan p dan p+2. Dan keduanya merupakan bilangan prima. Mempunyai selisih 2.
Berikut adalah beberapa pasangan-pasangan prima kembar.

(3 dan 5), (5 dan 7), (11 dan 13), (17 dan 19), (29 dan 31)

Apakah hanya pasangan-pasangan seperti itu yang merupakan pasangan bilangan prima kembar ?
Sekarang perhatikan dua bilangan berikut

100000000061 dan 100000000063 .

Keduanya merupakan bilangan prima. Dan selisih dua bilangan tersebut adalah 2. Jadi bisa dikatakan bahwa dua bilangan tersebut adalah pasangan prima kembar.

Perumusan bilangan prima yang gagal

Belum ada yang bisa menemukan secara pasti tentang perumusan bilangan prima. Di bawah ini akan diberikan beberapa perumusan yang gagal menghasilkan bilangan prima secara keseluruhan.

1. $F(n)=n^2-n+41$

Pernah diduga bahwa fungsi $F(n)=n^2-n+41$ menghasilkan bilangan prima untuk n bilangan asli. Bisa dicheck untuk n = 1, 2, 3, 4, dst. Tetapi ternyata rumus ini gagal ketika n = 41.
Karena $F(41)=41^2$ . bukan merupakan bilangan prima.
Sekarang bagaimana dengan rumus $F(n)=n^2+n+41$ .
Coba temukan, untuk n berapakah dia tidak prima.

2. $G(n)=2^{2^n}+1$

Ini adalah hasil pekerjaan Fermat. Fermat pernah menduga bahwa rumus tersebut adalah menghasilkan bilangan prima. Untuk n = 0, 1, 2, 3, 4 ini merupakan benar bilangan prima. Tetapi pertumbuhan bilangannya sangat besar, sehingga orang malas menguji kebenaran bilangan itu untuk n yang selanjutnya.
Tetapi pada tahun 1732 Leonhard Euler membuktikan bahwa untuk n = 5, G(5) = 4.294.967.297 bukan merupakan bilangan prima, karena nilai itu sama dengan 641 x 6.700.417.
Kemudian pada tahun 1880, F. Landry menunjukkan bahwa untuk n = 6 juga bukan bilangan prima.
Dan pada awal tahun 1970 untuk n = 7 juga bukan merupakan bilangan prima.
Dengan menggunakan computer terbukti yang merupakan bilangan prima hanya lima angka pertama saja.

3. $2^p-1$ .
Dinyatakan oleh Marin Marsenne dari Perancis. Dia menyatakan bahwa untuk p bilangan prima maka bentuk $2^p-1$ merupakan bilangan prima. Marsenne tahu bahwa untuk p = 11 akan didapatkan 2047. Yang ternyata angka tersebut bukan merupakan bilangan prima karena 2047 = 23 x 89, akan tetapi Marsenne yakin bahwa untuk p > 11, bilangan yang dihasilkan pasti bilangan prima.
Tetapi pada tahun 1903, untuk p = 67 dihasilkan 147573952588676412927 yang bukan merupakan bilangan prima karena bilangan itu sama dengan perkalian dari 193707721 x 761838257287.

Salah satu cara mencari bilangan prima yang benar yaitu menggunakan cara yang dilakukan oleh Erastothenes dari Kirene yang dikenal dengan Sieve of Erastothenes.
Langkah ini banyak digunakan siswa SD saat pengenalan bilangan prima pada saat sekolah dasar. Biasanya untuk siswa setingkat SD, bilangan prima yang dicari dibatasi dari 0 sampai 100. Dibawah ini diberikan langkah-langkah mencari bilangan prima dari 0 sampai 100.

Langkah-langkahnya :
Buat tabel bilangan berukuran 10 x 10

Coret bilangan 1 karena bukan prima
Lingkari angka 2 dan coret kelipatan 2
Lingkari angka 3 dan coret kelipatan 3
Lingkari angka 5 dan coret kelipatan 5
Lingkari angka 7 dan coret kelipatan 7

Maka nanti angka yang dilingkari dan yang belum dicoret merupakan bilangan prima.

Ukuran table bilangan tidak menjadi masalah. Hanya saja ketika table itu rapi, maka kita akan semakin mudah dalam melakukan pencoretan.
Tabel yang mudah untuk dilakukan pencoretan adalah table yang lebarnya 10 satuan atau 5 satuan. Disarankan menggunakan table seperti itu agar pencoretan lebih mudah dilakukan.

Teorema :

“Untuk setiap bilangan majemuk n ada bilangan prima p sehingga p membagi n dan p kurang dari atau sama dengan akar n”

Dari Teorema tersebut dapat disimpulkan bahwa, untuk mengecek bilangan prima dibawah n, maka kita perlu memperhatikan akar n, pencoretan hanya berhenti pada akar n atau kurang dari akar n.
Misalnya, kita akan mengecek bilangan prima dibawah 200 (0 sampai 200). Maka yang perlu kita cek hanya sampai 13. Karena bilangan prima terbesar yang lebih kecil dari akar 200 adalah 13. $\sqrt{200}=14,14...$ . Sehingga kita hanya perlu mengecek kelipatan 2, 3, 5, 7, 11, dan 13.

Tentang prima yang lain :

Jika p merupakan bilangan prima dan $n^2$ habis dibagi p maka $n^2$ juga akan habis dibagi p.
Setiap bilangan asli lebih besar 1 yang merupakan bilangan majemuk (bilangan majemuk adalah bilangan asli yang bukan prima) bisa dituliskan dalam perkalian beberapa bilangan prima. Ini adalah teorema faktorisasi.
Misalkan p adalah bilangan prima. Jika p membagi ab maka p membagi a dan p membagi b. dalam notasi teori bilangan dituliskan jika $p \mid ab$ maka $p \mid a$ atau $p \mid b$ .
Conjecture yang menarik. Setiap bilangan genap dapat dinyatakan sebagai jumlah dua bilangan prima. Umumnya dapat dinyatakan dalam satu cara. Ada juga yang dapat dinyatakan dalam dua cara, tiga cara, dst. Conjecture ini dikemukakan oleh Goldbach. Sampai saat ini masih belum ada yang bisa mebuktikan.
Ini adalah deret yang dibuat fermat. Yaitu yang terdiri dari bilangan factorial. Deret ini adalah deret bilangan prima yang gagal. Beberapa suku awal menghasilkan bilangan prima. Akan tetapi selanjutnya gagal menghasilkan bilangan prima.

3! – 2! + 1! = 5

4! – 3! + 2! – 1! = 19

5! – 4! + 3! – 2! + 1! = 101

6! – 5! + 4! – 3! + 2! – 1! = 619

7! – 6! + 5! – 4! + 3! – 2! + 1! = 4421

8! – 7! + 6! – 5! + 4! – 3! + 2! – 1! = 35899

Sampai di sini, semua bilangan yang terbentuk adalah bilangan prima. Sungguh unik bukan. Tetapi lanjutan dari deret ini bukan bilangan prima.

9! – 8! + 7! – 6! + 5! – 4! + 3! – 2! + 1! = 326981

326981 bukanlah merupakan bilangan prima. Karena 326981 = 79 x 4139.
Deret ini gagal menghasilkan bilangan prima.

13 adalah satu dari banyak bilangan prima yang lain. Banyak juga orang yang menyebut bahwa 13 adalah angka sial. Sekarang kita perhatikan jika 1 dibagi angka 13 tersebut.

$\frac{1}{13}=0,076923076923 \dots$ angka 076923 akan berulang terus.

Dan ternyata, angka ini unik jika dikalikan dengan angka 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, dan 12. Bilangan yang dihasilkan adalah bilangan 076923 dan 153846 dengan urutan digit-digitnya yang berbeda.

(153846 = 2 x 3 x 3 x 3 x 7 x 11 x 37)

1 x 076923 = 076923

2 x 076923 = 153846

3 x 076923 = 230769

4 x 076923 = 307692

5 x 076923 = 384615

6 x 076923 = 461538

7 x 076923 = 538461

8 x 076923 = 615384

9 x 076923 = 692307

10 x 076923 = 769230

11 x 076923 = 846153

12 x 076923 = 923076

Soal dan Pembahasan Olimpiade Matematika

Winalite

Thursday, May 31, 2012

Bilangan Prima

No comments:

Post a Comment

Translate

Followers