 BAB 2
LANDASAN TEORI
Sebelum kita
membahas
mengenai
uji
primalitas,
terlebih
dahulu
kita
bicarakan
beberapa definisi yang diperlukan serta beberapa teorema dan sifat-sifat yang penting dalam
teori bilangan.
2.1
Teori Bilangan
Prima
Definisi 2.1.1 (Bilangan
Prima)
Suatu
bilangan bulat
positif p
yang
lebih besar dari
1
disebut bilangan
prima, jika
pembagi positifnya hanyalah 1 dan p. Bilangan bulat positif yang lebih besar dari 1
dan tidak prima disebut sebagai bilangan komposit.
Dari
definisi
ini
jelas
bahwa
1
bukan
bilangan
prima
meskipun pembagi
positif dari 1
hanyalah dia sendiri. Juga
jelas bahwa
satu - satunya bilangan prima
yang genap adalah bilangan 2.
2.2
Greatest Common
Divisor (Pembagi
Persekutuan Terbesar)
Definisi 2.2.1
Suatu bilangan bulat b dikatakan dapat habis dibagi oleh bilangan bulat a ? 0, ditulis
dengan notasi a | b, jika terdapat bilangan bulat c sedemikian sehingga b = ac. Kita
tuliskan a | b untuk menunjukkan bahwa b tidak habis dibagi a.
|
|
6
Definisi 2.2.2
Kita
ambil bilangan –
bilangan bulat positif a
dan
b,
dengan
setidaknya salah satu
dari
keduanya
tidak
sama
dengan
0.
Greatest
Common Divisor
dari
a
dan
b,
ditandakan dengan gcd(a,b) adalah bilangan bulat positif d
yang memenuhi syarat –
syarat:
(i)
d | a dan d | b.
(ii)
Jika c | a dan c | b, maka c = d.
Definisi 2.2.3
Dua bilangan – bilangan bulat a dan b, di mana salah satu dari keduanya tidak sama
dengan 0, dikatakan relatif prima jika
gcd(a, b) = 1.
Teorema
2.2.1 Algoritma
pembagian
Diberikan
bilangan
–
bilangan
bulat
a dan
b,
di
mana
b
>
0.
Maka
terdapatlah
bilangan bulat unik q dan r yang memenuhi:
a
= qb + r, 0 = r < b.
Bilangan
–
bilangan
q
dan
r
berturut –
turut disebut
sebagai
hasil
bagi
dan
sisa
dalam pembagian a oleh b.
Teorema di atas berlaku sebagai fondasi utama teorema – teorema dan
algoritma – algoritma yang akan dikembangan berikutnya.
Di bawah
ini
diberikan beberapa
sifat tentang
divisibilitas
dari bilangan –
bilangan bulat.
|
|
7
Teorema
2.2.2 Sifat bilangan
Untuk bilangan – bilangan bulat sebarang a, b, c berlaku:
(i)
a
|
0, 1 | a, a | a.
(ii)
a
|
1 jika dan hanya jika a = ±1.
(iii)
Jika a | b dan
c | d, maka ac | bd.
(iv) Jika a | b dan b | c, maka a | c.
(v)
a
|
b dan b | a jika dan hanya jika a = ±b.
(vi) Jika a | b dan b ? 0, maka | a | = | b |.
(vii) Jika a | b dan a | c, maka a | (bx + cy) untuk semua bilangan bulat x, y.
Teorema
berikut
ini
menyatakan
bahwa
gcd(a, b) dapat
dinyatakan sebagai
kombinasi linear dari a dan b. Kombinasi linear dari a dan b adalah ekspresi dari ax
+ by, di mana x dan y adalah bilangan – bilangan bulat sebarang.
Teorema
2.2.3
Kita
misalkan a
dan
b
adalah
bilangan –
bilangan
bulat,
di
mana keduanya
tidak
bersama – sama 0. Maka terdapatlah bilangan – bilangan bulat
x
dan y sedemikian
sehingga:
gcd(a, b) = ax + by .
Teorema
berikut
ini
mengkarakterisasikan
dua
bilangan
bulat
yang
relatif
prima dengan kombinasi liniernya.
|
 8
Teorema
2.2.4
Misalkan a dan b adalah bilangan - bilangan bulat, di mana keduanya tidak bersama -
sama 0. Maka a dan b relatif prima jika dan hanya jika terdapat bilangan – bilangan
bulat x dan y yang memenuhi persamaan 1 = ax + by.
Bukti
Jika a dan b adalah relatif prima maka
gcd(a, b) = 1 . Dengan Teorema 2.2.3
terdapatlah bilangan bulat x dan y yang memenuhi 1 = ax + by. Dan untuk
konversnya,
kita
misalkan bahwa 1
=
ax
+
by untuk
bilangan
bulat
x
dan y, dan
d
=
gcd(a, b)
. Karena d | a
dan d | b, dengan Teorema 2.2.2 (bagian
vii)
menghasilkan d | (ax + by), atau d | 1. Oleh karena d adalah bilangan bulat positif,
kondisi terakhir ini mengharuskan d sama dengan 1, sehingga a dan b relatif prima.
2.3
Teori Modulo
Definisi 2.3.1
Diberikan suatu
bilangan
bulat
positif
m.
Untuk
bilangan
bulat
a dan b,
maka
a
dikatakan kongruen terhadap
b modulo m jika m (a – b).
| (a – b).
Jika
a kongruen
terhadap
b
modulo
m,
maka
kita
nyatakan
dengan
a
=
b(mod m) . Jika m | (a – b), kita nyatakan dengan a = b(mod m) dan kita baca a
, dan kita baca a
tidak kongruen dengan b modulo m. Bilangan bulat positif m disebut sebagai
modulus. Bentuk jamak dari modulus adalah moduli.
|
|
9
Teorema
2.3.1
Terdapat bilangan bulat a dan b, maka
a
=
b(mod m) jika
hanya jika terdapat
bilangan bulat k yang memenuhi a = b + km.
Bukti
Jika a = b(mod m) , maka m | (a – b). Maka dapat dikatakan bahwa terdapat bilangan
bulat k yang memenuhi km = a – b, sehingga a = b + km.
Untuk konversnya, jika terdapat bilangan bulat k yang memenuhi a = b + km, jelas
bahwa km = a – b. Maka m (a – b), sehingga a = b(mod m) .
| (a – b), sehingga a = b(mod m) .
Teorema
2.3.2 Sifat
modulo
Misalkan
n
adalah bilangan
bulat dengan
n
>
1
dan a,
b,
c,
d
adalah bilangan –
bilangan bulat sebarang. Maka berlakulah sifat – sifat:
(i)
a
=
a(mod n) .
(ii)
Jika a = b(mod n) , maka b =
a(mod n) .
(iii)
Jika a = b(mod n) dan b = c(mod n) , maka a =
c(mod n) .
(iv) Jika
a
=
b(mod n) dan
c
=
d
(mod n) , maka
a
+
c
=
b
+ d (mod n) dan
ac = bd (mod
n)
.
(v)
Jika a = b(mod n) , maka
a
+
c
=
b
+
©(mod n) dan ac = bc(mod n) .
(vi) Jika
a
=
b(mod n) ,
maka
a
k
=
b
k
(mod n) untuk
semua bilangan
bulat
nonnegatif k.
|
|
10
2.4
Teorema
Fundamental
Aritmetika
Teorema
2.4.1
Setiap bilangan bulat positif p yang
lebih besar dari 1 adalah bilangan prima atau
hasil
kali
dari
bilangan –
bilangan
prima
dengan
penyajian
atau
penulisan
yang
tunggal, terlepas dari urutan faktor – faktornya.
2.5
Teorema
Euclid
Terdapat beberapa versi pembuktian dari pernyataan bahwa terdapatlah tak
berhingga banyak bilangan –
bilangan prima. Euclid
secara elegan
membuktikan
peryataan tersebut yang ditampilkan pada bukti dari teorema ini.
Teorema
2.5.1
Terdapat tak berhingga banyak bilangan – bilangan prima.
Bukti
Kita urutkan bilangan – bilangan prima dari yang terkecil ke
yang
lebih besar dan
ditulis sebagai :
p
1
=
2, p
2
=
³, p
3
=
5, p
4
=
7,K .
Andaikan
terdapat
berhingga
banyak bilangan –
bilangan prima yang banyaknya
adalah
n
dan
bilangan
prima
yang terbesar
adalah
p
n
. Dibentuklah bilangan
bulat
positif :
P
=
p
1
p
2
L
p
n
+
1
.
Karena P
lebih besar dari 1, dengan Teorema Fundamental Aritmetika maka P
habis
dibagi
oleh
suatu
bilangan
prima
misalnya p
yang
merupakan
salah
satu
dari
n
bilangan prima di atas. Mengingat 1 = P - p
1
p
2
L
p
n
dengan p membagi sekaligus P
|
 11
dan
hasil
kali
p
1
p
2
L
p
n
maka
dapat disimpulkan
bahwa
p
juga
membagi
1
yang
jelas menimbulkan kontradiksi.
2.6
Metode
Eratosthenes
Uji primalitas
adalah suatu masalah yang sangat penting dalam konsep
bilangan. Metode
klasik
yang
cukup
dikenal
untuk
uji
primalitas
adalah
dari
Eratosthenes yang dikenal dengan nama Sieve of Eratosthenes yang digunakan untuk
mencari semua bilangan prima yang lebih kecil dari bilangan bulat positif n. Metode
tersebut berdasarkan pada proposisi berikut.
Proposisi
2.6.1
Bila bilangan bulat a > 1 tidak mempunyai pembagi prima p = a , maka a adalah
prima.
Bukti
Andaikan a bukan bilangan prima. Maka a dapat ditulis sebagai a = bc di mana 1 < b
<
a
dan 1 < c < a.
Misalkan b = c kita peroleh b² = bc = a sehingga
b
=
a .
Karena b > 1, berdasar pada Teorema Fundamental Aritmetika b mempunyai paling
sedikit satu pembagi prima p. Sehingga diperoleh p = b = a . Selanjutnya mengingat
p
|
b
dan b
|
a
maka p |
a
yang menimbulkan
suatu kontradiksi. Jadi yang benar
bahwa a adalah prima.
Untuk mencari semua bilangan prima dari 2 sampai dengan
n metode
Eratosthenes dapat dijelaskan sebagai berikut :
|
 12
•
Urutkan
semua
bilangan
bulat
positif
dari
2
sampai
dengan
n
dari
yang paling kecil ke yang paling besar.
•
Eliminir semua bilangan komposit
yang berbentuk 2p,3p,4p,5p,… di
mana p adalah bilangan prima yang memenuhi p = n .
•
Yang tersisa adalah semua bilangan prima dari 2 sampai dengan n. Untuk
n
=
100, metode Eratosthenes secara sistematis mengeleminir bilangan
-
bilangan
komposit
yang
merupakan
kelipatan
2,
kelipatan
3,
kelipatan
5,
atau
kelipatan 7 dari semua bilangan bulat positif dari 2 sampai dengan 100.
2.7
Fungsi
Euler
Phi
Definisi 2.7.1
Untuk bilangan bulat n = 1,
f
(n) menyatakan banyaknya semua bilangan bulat
positif yang lebih kecil atau sama dengan n, dan relatif prima terhadap n.
Bila n merupakan bilangan prima maka
f
(n) = n – 1.
Teorema
2.7.1
Fungsi
f
merupakan fungsi multiplikatif.
Teorema ini menunjukkan bahwa
f
(mn) =
f
(m)
f
(n) untuk semua bilangan –
bilangan bulat m = 1 dan n = 1.
Contoh
|
|
13
Sebagai contoh kita ambil
f
(mn)
=
f 30)
(30)
=
8 Dari seluruh bilangan bulat yang tidak
. Dari seluruh bilangan bulat yang tidak
lebih dari 30 hanya
terdapat 8 bilangan
yang
merupakan relatif prima terhadap 30,
yaitu 1, 7, 11, 13, 17, 19, 23, 29.
Sedangkan 30 = 5 · 6. Maka kita dapatkan pula
f 5) = 4 yaitu 1, 2, 3, 4 dan
(5) = 4 yaitu 1, 2, 3, 4 dan
f 6) = ²
(6) = ²
yaitu 1 dan 5. Sehingga
f
(30) =
f
(5 · 6) =
f
(5)
f
(6) = 4
·
2 = 8
.
Lemma
2.7.1
Misalkan n adalah bilangan bulat dengan n > 1 dan
gcd(a, n) = 1 Jika a
. Jika a
1
,
a
1
,K, a
f
(
n
)
merupakan bilangan – bilangan bulat positif yang lebih kecil dari n dan relatif prima
terhadap n, maka
aa
1
,
aa
2
,K, aa
f
(
n
)
kongruen modulo n terhadap
a
1
,
a
2
,K, a
f
(
n
)
dalam suatu urutan tertentu.
Teorema
2.7.2 Teorema
Euler
Jika n bilangan bulat dengan n = 1 dan
gcd(a, n) = 1 maka
, maka
a
f
(
n
)
=
1(mod n) .
Bukti
Misalkan n bilangan bulat dengan n > 1, dan
a
1
,
a
2
,K, a
f
(
n
)
adalah bilangan –
bilangan bulat positif yang lebih kecil daripada n dan relatif prima terhadap n. Oleh
karena
gcd(a, n) = 1 ,
dengan
Lemma
2.7.1
maka
aa
1
,
aa
2
,K, aa
f
(
n
)
kongruen
modulo n terhadap
a
1
,
a
2
,K, a
f
(
n
)
dalam suatu urutan tertentu. Sehingga dapat
ditulis
|
|
14
aa
1
=
a
1
'
(mod n)
aa
2
=
a
2
'
(mod n)
M
M
aa
f
(
n
)
=
a
f
'
(
n
)
(mod n)
di mana a
1
'
,
a
2
'
,K, a
f
'
(
n
)
adalah bilangan – bilangan bulat a
1
,
a
2
,K, a
f
(
n
)
dalam suatu
urutan tertentu. Hasil yang kita dapatkan dari kekongruensian
f
(n) adalah
(aa
1
)(aa
2
)L(aa
f
(
n
)
)
=
a
1
'
a
'
2
La
f
'
(
n
)
(mod n)
=
a
1
a
2
La
f
(
n
)
(mod n) .
Sehingga
a
f
(
n
)
(a
1
a
2
L
a
f
(
n
)
)
=
a
1
a
2
La
f
(
n
)
(mod n) .
Oleh
karena
gcd(a
i
,
n) = 1
untuk
setiap
i,
berdasarkan
Lemma
2.7.1
gcd(a
1
a
2
La
f
(
n
)
,
n) = 1
.
Sehingga
kita dapat
membagi
kedua
ruas
dari
kongruensi
sebelumnya dengan faktor persekutuan a
1
a
2
Ka
f
(
n
)
, dan kita dapatkan
a
f
(
n
)
=
1(mod n) .
2.8
Order dari
Bilangan
Bulat Modulo
n
Definisi 2.8.1
Misalkan n bilangan bulat dengan n > 1 dan
gcd(a, n) = 1 Order
. Order
dari
a
modulo n
(dalam
terminologi
lama:
eksponen
dari
modulo
n)
adalah
bilangan
bulat
positif
terkecil k sedemikian sehingga a
k
=
1(mod n) .
|
|
15
Dari
definisi
ini dapat
dikatakan
bahwa bilangan
bulat a
memiliki order k
modulo
n
jika memenuhi persamaan a
k
=
1(mod n) dengan k bilangan bulat positif
terkecil yang memenuhi persamaan tersebut.
Teorema
2.8.1
Misalkan bilangan bulat a
mempunyai order k modulo n. Maka a
h
=
1(mod n)
jika
hanya jika k | h; khususnya, k |
f
(n) .
Bukti
Misalkan
kita
mulai dengan
k
|
h,
sehingga
h
=
jk
untuk
suatu
bilangan bulat
j.
Karena
a
k
=
1(mod n) , dengan Teorema 2.2.2 diperoleh
(a
k
)
j
=
1 (mod n) atau
j (mod n) atau
a
h
=
1(mod n) .
Untuk konversnya, misalkan h adalah bilangan bulat sebarang yang memenuhi
a
h
=
1(mod n) . Dengan algoritma pembagian, terdapatlah bilangan – bilangan bulat
q dan r yang memenuhi h = qk + r , di mana 0 = r < k.
Sehingga,
a
h
=
a
qk
+r
=
(a
k
) a .
q a .
r .
Dengan
hipotesis,
a
k
=
1(mod n) dan
a
h
=
1(mod n) ,
yang
berakibat
a
r
=
1(mod n) .
Karena 0 = r
<
k, maka kita dapatkan r = 0, bila tidak demikian, pilihan k sebagai
bilangan bulat positif terkecil dengan a
k
=
1(mod n)
tidak dipenuhi. Jadi h = qk dan
k h.
| h.
|
 16
2.9
Teorema
Fermat
Teorema
2.9.1 Fermat
Little
Theorem
Jika p adalah prima dan
a
adalah bilangan bulat positif
yang tidak habis dibagi p,
maka
a
p ¹
-¹
=
1(mod p)
Bukti
Kita
misalkan p – 1 bilangan bulat yang pertama sebagai pengali – pengali dari
a,
sehingga bilangan – bilangan bulat tersebut adalah sebagai berikut
a,2a,3a,K, ( p - 1)a
Tidak satupun dari bilangan – bilangan bulat di atas yang kongruen terhadap modulo
p atau kongruen terhadap nol. Jika persyaratan tersebut dipenuhi, maka
ra = sa(mod p) 1
=
r = s = p – 1.
kemudian a dapat
dihilangkan sehingga
r
=
s(mod p) ,
di
mana
hal
ini
sangatlah
tidak mungkin. Oleh karena itu, bilangan – bilangan bulat yang sebelumnya haruslah
kongruen
modulo
a,2a,3a,K, ( p - 1)
terhadap
p, dalam suatu
urutan
tertentu.
Dengan
mengalikan semua
kongruensian
tersebut bersama –
sama, kita dapatkan
bahwa
a
·
2a · 3a L( p - 1)a = 1· 2 3L( p - 1)(mod p)
· 3L( p - 1)(mod p)
di mana
a
p ¹
-¹
(
p
-
1)!= ( p - 1)!(mod p)
Setelah (p – 1)! dihilangkan dari kedua sisi persamaan kekongruensian di atas (hal
ini dapat terjadi karena p relatif prima terhadap p, sehingga p | (p – 1)!, maka hasil
|
 17
akhir dari persamaan tersebut adalah a
p
-1
=
1(mod p) di mana persamaan ini adalah
, di mana persamaan ini adalah
Teorema Fermat.
Teorema
2.9.2 Teorema
Akibat
Jika p adalah bilangan prima, maka a
p
=
a(mod p) untuk suatu bilangan bulat a.
Bukti
Jika p | a, maka a
p
=
0
=
a
(mod p). Jika p | a, maka menurut Teorema Fermat, kita
dapatkan
a
p ¹
-¹
=
1(mod p) . Ketika
kekongruensian
ini kita kalikan
dengan a,
akan
kita dapatkan a
p
=
a(mod p) .
|