Apa itu Bilangan prima? — Matematika

Definisi 64.5 Matematika Sekolah Dasar dan Menengah · Bab 64 — Aritmetika: Pembagi dan Bilangan Prima

Bilangan prima adalah bilangan bulat $\geq 2$ yang pembaginya hanya $1$ dan dirinya sendiri. Bilangan prima di bawah $30$ adalah

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

Bilangan $1$ bukan prima (menurut kesepakatan), dan bilangan bulat $\geq 2$ yang bukan prima disebut komposit.

Pohon faktor 360: tiap langkahnya memisahkan faktor prima terkecilnya (berwarna merah). Membaca daun merahnya dan 5 yang terakhir: 360 = 23 × 32 × 5. — Pohon faktor $360$ : tiap langkahnya memisahkan faktor prima terkecilnya (berwarna merah). Membaca daun merahnya dan $5$ yang terakhir: $360 = 2^3 \times 3^2 \times 5$ .

Baca dalam konteks →

Definisi 6.12 Matematika Universitas — Tahun 1 · Bab 6 — Aritmetika Bilangan Bulat

Bilangan bulat $p \geq 2$ disebut prima bila pembagi positifnya hanya $1$ dan $p$ . Untuk $p$ prima dan $a \in \Z$ : entah $p \mid a$ , atau $\gcd(p, a) = 1$ . Akibatnya (Teorema 6.8), berlaku lema Euclid: jika $p \mid ab$ maka $p \mid a$ atau $p \mid b$ .

Contoh

Contoh 6.24 (Konvers Fermat gugur: $341$ )

Teorema kecil Fermat memberikan uji kekompositan yang murah: jika $a^{n-1} \not\equiv 1 \pmod n$ untuk suatu $a$ yang saling prima dengan $n$ , maka $n$ tidak prima. Dapatkah ujinya juga mengesahkan keprimaan? Tidak: ambil $n = 341 = 11 \times 31$ , yang komposit, dan $a = 2$ . Karena $2^{10} = 1024 = 3 \times 341 + 1$ ,

2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :

bilangan komposit $341$ lolos uji Fermat untuk basis $2$ (dan ia pseudoprima terkecil semacam itu). Basis $3$ menyingkap topengnya ( $3^{340} \not\equiv 1$ ), sehingga uji keprimaan yang praktis menjalankan ujinya pada beberapa basis, ditambah penghalusan — versi industri gagasan inilah yang mengesahkan bilangan prima besar pada Catatan 6.27. Moralnya: sebuah implikasi dan konversnya hidup secara terpisah (Catatan 1.10), bahkan untuk teorema.

Baca dalam konteks →

Contoh

Istilah terkait