27
G.
Faktorisasi ke Bilangan Prima
Selanjutnya, dijelaskan pengertian dan sifat-sifat
suatu
bilangan
yang
disebut
dengan bilangan prima,
yaitu bilangan yang hanya dapat dibagi oleh 1 dan bilangan itu
sendiri. Bilangan prima memainkan peran
yang penting pada beberapa algoritma
kriptografi kunci publik, seperti algoritma ElGamal dan RSA.
Definisi 2.1.2.7. (Buchmann, 2000)
Suatu
bilangan
bulat p
>
1
disebut
prima
jika
p
hanya mempunyai tepat dua bilangan pembagi positif yaitu 1 dan p. Jika tidak, p disebut
komposit.
Jika
p
bilangan
prima
yang
membagi
suatu
bilangan
bulat
a, maka
p
disebut
pembagi prima dari a.
Contoh 2.1.2.12.
Bilangan bulat 2, 3, 5, 7 dan 11 adalah
bilangan
prima. Sedangkan 4, 6, 8, 9 dan 10
adalah bilangan komposit.
Teorema
2.1.2.8.
(Buchmann,
2000)
Setiap
bilangan
bulat
a
>
1
mempunyai
bilangan
pembagi prima.
Bukti:
Diketahui
bilangan
bulat
a
mempunyai
suatu
pembagi
yang
lebih
besar
dari
1,
yaitu a
sendiri.
Pandang
semua
pembagi a yang lebih besar dari 1, misalkan
p adalah
yang
terkecil. Maka p pastilah prima, sebab jika tidak,
maka p akan
mempunyai suatu
pembagi
b
dengan
1
<
b
< p =
a
.
Timbul
kontradiksi
dengan
asumsi
bahwa
p
adalah
pembagi terkecil dari a yang lebih besar dari 1.
 |