Teori Bilangan

Bilangan Prima Dan Komposit

Teori bilangan mempunyai banyak aplikasi, khususnya pada ilmu computer yang merupakan bagian dari matematik diskrit. Diasumsikan bilangan integer Z = {…,-3, -2, -1, 0, 1, 2, 3, …}.

Sifat 1.1

Diberikan a sebarang integer (positif, negative, atau nol). Deberikan X adalah himpunan semua integer x dengan x > a. maka setiap himpunan bagian tidak kosong S pada X mempunyai integer terkecil.

Definisi 1 .1 ( Prima di Z )

Sebuah integer p yaitu bukan {1, -1} dan hanya mempunyai faktorisasi trivial p = p.1 = (-p) (-1) disebut prime di Z

Berdasarkan definisi tersebut maka sebuah integer p disebut prime jika dan hanya p tidak mempunyai timbal balik di Z dan sebarang persamaan p = b c, dengan b dan c adalah integer, berimplikasi bahwa b dan c keduanya dalam himpunan { -p , -1, 1, p }.

Contoh 10 bilangan prime pertama dalam Z : 2, 3, 5, 7, 11, 13, 17, 19, 23 dan 29.

Definisi 1.2 ( Komposit pada Z )

Sebuah integer tidak nol yang mempunyai sebuah faktorisasi nontrivial disebut integer komposit

Contoh :

15 adalah komposit karena 15 = 0 dan 15 = 5 . 3 adalah sebuah faktorisasi nontrivial.

Integer komposit lainnya adalah +4, +6, +8, +9, +10, +12, +14. Sebagai catatan bahwa 0, 1, -1 adalah bukan prime dan juga bukan komposit.

Algoritma Pembagian

Perkalian pada integer positif adalah sebuah bentuk penjumlahan. Sebagai ilustrasi 4 . 5 mungkin dapat difikirkan sebagai : 5 + 5 + 5 + 5 atau 4 + 4 + 4 + 4 + 4.

Secara sama, pembagian pada integer positif dapat diselesaikan dengan pengulangan pengurangan. Jadi suatu pengujian apakah 8 adalah sebuah integer pembagi pada 48 atau bukan, dilakukan dengan berkali – kali mengurangi dengan 8 dan dilihat apakah 0 dihasilkan setelah beberapa langkah.

Dalam kasus ini, 0 dihasilkan setelah 6 kali pengurangan 8 dari 48, karena 48 = 6 . 8 atau 6 + 6 + 6 + 6 + 6 + 6 + 6 + 6 dan 8 | 48.

Jika dimulai dengan 53 dari 48, sebuah sisa positif yaitu kurang dari 8 dicapai setelah 6 kali pengurangan 8, dan diperoleh bahwa 53 = 6 . 8 + 5. Selanjutnya jika dikurangi lagi dengan 8 akan diperoleh hasil negative, bukan 0. Oleh karena itu 8 bukan pembagi 53 dalam Z.

Teorema 1 .1 ( Algoritma Pembagian )

Jika a dan d adalah bilangan integer dan b adalah bilangan positif, maka ada integer q dan r sedemikian sehingga :

a = q b + r, 0 < r < b.

Sehingga , b | a jika dan hanya jika r = 0. Maka, q adalah quotient dan r adalah sisa pembagian a dengan b.

Bukti :

Diberikan N himpunan { 0, 1, 2, …} dan integer non negative. Diberikan S himpunan bagian N dari semua integer non negative yang dapat diekspresikan dalam bentuk a – qb, dengan q integer.

Selanjutnya diperlihatkan bahwa himpunan S tidak kosong, karena b integer positif,

maka b > 1, dan | a | . b > | a | . 1 = | a | > -a,

yaitu | a | . b > -a.

Dengan mengikutinya maka: a + | a | . b > a – a = 0, dan karenanya : a – (- | a | ) b > 0.

Pertidaksamaan tersebut menggambarkan bahwa satu harga q, yang sama a – qb dalam S, yaitu q = - | a |; sehingga S tidak kosong. Kemudian berdasarkan sifat 1 himpunan tidak kosong S mempunyai paling sedikit sebuah integer r. Berhubungan dengan ini r adalah sebuah integer q sedemikian sehingga a – qb = r.

Dengan definisi S, paling sedikit integer r memenuhi 0 < r. Terlihat bahwa r juga memenuhi r < b dengan asumsi r > b dan menghasilkan suatu kontadiksi.

Diberikan r’ = r – b dan q^’ = q + 1.

Jika r > b, maka r’ > 0 dan

r’ = r – b = ( a – qb ) – b = a- ( q + 1 ) b = a – q^’ b. r^’ > 0

dan r^’ = a – q^’ b termasuk bahwa r’ dalam S. Karena r’ = r – b < r, kontradiksi ini menyatakan bahwa r adalah integer terkecil dalam S, karena itu r < b yaitu 0 < r < b.

Selanjutnya dibuktikan bahwa r dan q adalah tunggal. Dimulai dengan mengasumsikan nahwa a = qb + r = q₁ b + r₁ , 0 < r < b, 0 < r₁ < b.

Diasumsikan bahwa r > r_1. Maka :

0 < r - r₁ < b.

r - r₁ = (q₁ – q ) b.

karena tidak ada perkalian pada b antara 0 dan b., maka didapatkan r - r₁ = 0.

Sehingga r = r₁

qb = q₁b dan akhirnya q = q₁, karena b = 0. jadi r dan q secara tunggal ditentukan dengan a dan b.

Jika r = 0, maka a = qb + r = qb, dan dipunyai b|a. Sebaliknya, jika b|a, maka ada integer m sedemikian sehingga a = mb, dan karena itu q dan r adalah berturut – turut m dan 0. Terlihat bahwa b|a jika dan hanya r = 0.

Terbukti.

Akibat Teorima 1.1 (Extended Division Algoritma/perluasan algoritma pembagian)

Jika a dan c dalam Z dan c = 0, maka ada q dan r dalam Z sedemikian hingga :

A = qc + r dan 0 < r < | c |.

Akibat ini dibuktikan dengan mengambil b = | c | dan kemudian pemakaian teorema. Diberikan m sebuah integer positif tetap. Maka teorema 1.1 (teorema pembagian) menyatakan bahwa setiap integer a adalah satu bentuk pada

qm, qm + 1, qm + 2,…, qm + ( m – 1 ), dengan q integer, yaitu setiap integer tepat satu pada himpunan – himpunan

mZ, 1 + mZ, 2 + mZ,…, ( m – 1 ) + mZ.

Jika m = 2, statemen ini menjadi pernyataan yang sudah lazim bahwa setiap integer dalam himpunan 2Z = {…, -4, -2, 0, 2, 4,…} pada integer genap atau dalam himpunan 1 + 2Z = {…, -3, -1, 1, 3, 5, …} pada integer ganjil, tetapi tidak dalam keduanya. Dengan m = 3, diperoleh pertanyaan bahwa setiap integer secara tepat terdapat dalam satu dari himpunan – himpunan 3Z, 1 + 3Z, 2 + 3Z.

Definisi 1.3 ( Kesamaan integer )

Diberikan a dan c interger. Maka a dan c mempunyai kesamaan jika keduanya genap atau keduanya ganjil. Jika satu dari integer ini genap dan lainnya ganjil, maka dikatakan mempunyai kesamaan yang berlawanan (opposite parity).

Jadi 15 dan 17 mempunyai kesamaan karena keduanya ganjil. Demikian juga -4 dan 6 mempunyai kesamaan karena keduanya genap. Tetapi 6 dan 15 mempunyai kesamaan yang berlawanan.

Notasi 1 .1 ( Congruence Module M )

Diberikan a, c dan m integer dengan m positif. Maka notasi a º c ( mod m) mempunyai arti bahwa a dan c mempunyai sisa yang sama jika dibagi dengan m. “ a º c ( mod m) “ dibaca sebagai a kongruen dengan c modulo m. hubungan ini disebut kongruen dan m disebut modulus pada kongruen.

Contoh :

Persamaan 28 = 5. 5 + 3 dan 73 = 14 . 5 + 3, terlihat bahwa 28 dan 73 mempunyai sisa yang sama jika dibagi dengan 5, sehingga 28 º 73 ( mod 5 ). Setiap 28 dan 73 dalam 3 + 5Z.

Teorema 1.2 (Two ways of showing equal remainders)

Diberikan a, c dan m integer dengan m positif. Maka a º c ( mod m ) jika dan hanya jika m | ( a – c ).

Bukti :

Dibuktikan dalam bentuk dibawah ini :

(i) jika a º c ( mod m ), maka m | ( a – c )

(ii) jika m | ( a – c ), maka a º c ( mod m )

untuk kedua bagian ini, dengan algoritma pembagian bahwa a = qm + r dan c = q’ m + r’ dengan q, r, q^’ dan r’ dalam Z, 0 < r < m dan 0 < r^’ < m.

(i)

Diberikan a º c ( mod m ). Berdasarkan definisi kongruen, mempunyai arti bahwa r = r^’, sehingga diperoleh :

A – c = ( qm + r 0 – ( q’ m + r’ ) = ( q – q^’ ) m

Oleh karena itu, m | ( a – c ). Terbukti.

(ii)

Diberikan m º ( a – c ), yaitu a – c tm dengan t dalam Z, maka

Tm = a – c = ( qm + r ) – ( q’ m + r^’ ) = ( q – q’ ) m + ( r + r’ ), sehingga r + r’ = ( t – q + q’ ) m, artinya bahwa r + r’ adalah sebuah perkalian integer pada m.

Tetapi r dan r’ dalam { -(m – 1), -(m – 2), …, 0, …, m -2, m -1}. Karena perkalian bilangan bulat hanya pada m dalam himpunan ini adalah 0, terlihat bahwa r – r’=0

Akhirnya r = r’ yang berimplikasi bahwa a º c ( mod m ). Terbukti.

Teorema 1.3 ( Closure under substraction )

Diberikan S sebuah himpunan integer tertutup dibawah pengurangan, maka :

(a) jika S tidak kosong, 0 dalam S

(b) jika a dalam S, -a juga dalam S

(c) jika a dan b dalam S dan q adalah sebuah integer, a – qb dalam S

(d) S terdiri atas semua perkalian bilangan bulat pada beberapa t dalam Z atau s adalah kosong

(e) Jika pada integer positif terkecil dalam S, yaitu S = tZ.

Bukti :

Jika S tidak kosong, ada sebuah integer a dalam S, dan a – a = 0 dalam S dengan closure under substraction. Maka 0 – a = - a dalam S. sehingga (a) dan (b) terbukti.

Diberika a dan b dalam S. maka a-qb adalah hasil pengurangan qb dari a (jika q positif) atau pengurangan –b pada –q kali ( jika q negatif). Dalam tiap kasus, a – qb dalam S dengan closure under substraction . terbukti

Jika s adalah himpunan dengan elemen tunggal { 0 }, S atas semua perkalian bilangan bulat pada 0. Karena itu dianggap ada elemen c tidak nol dalam S, maka satu pada c atau –c adalah positif dalam S. Himpunan bagian T pada integer positif dalam S adalah sebuah himpunan non negative, dan berdasarkan sifat 1 maka T mempunyai sebuah integer terkecil t.

Diberikan a sebarang integer dalam S. Algoritma pembagian memberikan integer q dan r sedemikian sehingga :

a = qt + r , 0 < r < t.

Maka r = a – qt dalam S berdasarkan (c). karena r lebih kecil dari integer positif terkecil t dalam S, maka r bukan positif, karena 0 < r maka r = 0. karena itu a = qt, yaitu setiap a dalam S adalah sebuah perkalian bilangan bulat qt pada integer positif terkecil t dalam S, maka a = 0 = 0 – (-q)t dalam S berdasarkan (a) dan (c), karena itu S adalah himpunan tZ pada semua perkalian bilangan bulat pada t. Terbukti.

Pembagi bersama

Diberikan a dan b integer nonnegative. Sebuah pembagi bilangan bulat bersama t pada a dan b, yaitu sebuah integer t sedemikian bahwa t|a dan t|b memenuhi ketidaksamaan :

-| a| < t < | a |

-| b| < t < | b |

Karena itu himpunan T pada pembagi bilangan bulat bersama adalah finite. Karena 1 dalam T, ada satu integer positif terkecil dalam T. Dengan mengikuti dari dua pernyataan terakhir bahwa ada integer positif terbesar dalam T, jika c adalah sebuah integer tidak nol, integer positif terbesar d sedemikian sehingga d|c dan d|0 adalah d = | c |

Definisi 1.4 ( pembagi bersama terbesar)

Diberikan a dan b integer, keduanya tidak nol. Sedemikian sehingga d|a dan d|b disebut pembagi bersama terbesar (ged) pada a dan b dan dinotasikan dengan ged(a,b). Maka ged(0,0) = 0.

Himpunan pembagi bilangan bulat positif 10 adalah A = {1, 2, 5, 10} dan himpunan pembagi bilangan bulat positif 12 adalah B = {1, 2, 3, 4, 6, 12}. Himpunan pembagi bilangan bulat positif bersama 10 dan 12 adalah :

C = A Ç B = { 1, 2 }

Dan karena itu ged(10,12) = 2.

Contoh lain adalah : ged(15, 6) = 3 dan ged(26, -10) = 2

Definisi 1.5 ( Integer relative prime )

Jika ged( r, s ) = 1, integer r dan s adalah relative prime atau coprime

Contoh:

22 dan -15 adalah relatif prime, karena ged ( 22, -15 ) = 1, demikian juga 7 dan 24 adalah relative prime meskipun satu atau setiap r dan s adalah komposit.

Contoh ged ( 17, 51 ) = 17 dan ged( 19, -19 ) = 19 memperlihatkan bahwa r dan s tidak perlu relative prime walaupun satu atau setiap r dan s adalah prime.

Linier Congruential Generators

Sebagian besar pembangkitan bilangan random yang digunakan adalah linier Congruential Generators (LCGs). Sebuah barisan integer Z₁, Z₂.

Didefinisikan dengan formula rekursif :

Z_i = (aZ_i-1 + c ) (mod m) .................................(2-1)

Dimana m adalah modulus, a pengali, c pertambahan dan Z₀ benih atau nilai awal. Maka persamaan (2-1) dikatakan menghasilkan Z_i, pembagian a Z_i-1 + c dengan m dan diberikan Z_i adalah sisa dari pembagian. Oleh karena itu, 0 < Z_i < m – 1, dan menghasilkan bilangan random yang dikehendaki U_i untuk i = 1, 2, … pada [ 0, 1], dan diberikan U_i = Z_i | m.

Pada penjumlahan nonnegative, integer m, a, c dan Z₀ seharusnya memenuhi 0 < m, a < m, c < m dan Z₀ < m. Banyak Simulasi komputer membutuhkan pembangkitan bilangan pseudorandom antara 0 dan 1. Sebagai ilustrasi, barisan bilangan pseudorandom dibangkitkan dengan memilih m = 9, a = 7, c = 4 dan Z₀ = 3, dapat ditemukan :

Z₁ = 7 Z₀ + 4 = 7 . 3 + 4 = 25 mod 9 = 7 ,

Z₂ = 7 Z₁ + 4 = 7 . 7 + 4 = 53 mod 9 = 8 ,

Z₃ = 7 Z₂ + 4 = 7 . 8 + 4 = 60 mod 9 = 6 ,

Z₄ = 7 Z₃ + 4 = 7 . 6 + 4 = 46 mod 9 = 1 ,

Z₅ = 7 Z₄ + 4 = 7 . 1 + 4 = 11 mod 9 = 2 ,

Z₆ = 7 Z₅ + 4 = 7 . 2 + 4 = 18 mod 9 = 0 ,

Z₇ = 7 Z₆ + 4 = 7 . 0 + 4 = 4 mod 9 = 4,

Z₈ = 7 Z₇ + 4 = 7 . 4 + 4 = 32 mod 9 = 5 ,

Z₉ = 7 Z₈ + 4 = 7 . 5 + 4 = 39 mod 9 = 3 ,

Karena Z₉ = Z₀ , dan karena setiap bagian tergantung hanya pada bagian sebelumnya, maka barisan yang dibangkitkan adalah :

3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, …....

Barisan ini mempunyai 9 bilangan berbeda sebelum diulang kembali. Kenyataannya banyak komputer menggunakan linier Congruential Generators untuk membangkitkan bilangan pseudorandom. Seringkali, sebuah linier Congruential Generators dengan pertambahan c = 0 digunakan. Generator ini di sebut pure multiplicative generators. Sebagai gambaran, pure multiplicative generators dengan modulus 2³¹ – 1 dan pengali 75 = 16.807 secara luas digunakan. Disamping itu, metode pembangkitan bilangan random lain yang digunakan adalah prime modulus multiplicative linier congruential generators, dan digunakan m = 2^b, dan pada kasus diambil b = 21 sehingga m adalah bilangan prime terbesar yang lebih kecil dari 2³¹ adalah 2³¹ – 1 = 2.147.483.647. Untuk m prime mempunyai periode m – 1 jika a adalah sebuah element primitive modulo m, dan lebih kecil dari pada integer 1 dimana a^’ – 1.

Dengan memilih a dan m melalui metode tersebut dihasilkan setiap integer 1, 2, 3, …, m – 1 tepat satu kali dalam setiap periode, sehingga Z₀ dapat sebarang integer gelombang – gelombang dari 1 sampai m – 1 dengan periode m – 1 akan dihasilkan.

Sebagai gambaran kasus implementasi Algoritma Monte Carlo di implementasikan Prime Modulus Multiplicative Linier Congruential Generators yang telah disusun oleh Marse dan Roberts, yang dirumuskan m = 2^b – q untuk sebarang integer positif q menghasilkan Z_i = ( a Z_i-1 ) ( mod 2^b ­), dimana dihasilkan overflow tanpa pembagian. Jika k adalah integer terbesar dan lebih kecil atau sama dengan a Z_i-1 / mod 2^b , maka :

Z_i ^/ + kq jika Z_i ^/ + kq < 2^b - q

Z_i = Z_i ^/ + kq – ( 2^b – q ) jika Z_i ^/ + kq < 2^b – q

(diambil dari buku Analisa algoritma karya fajar junaedi ep)