Algoritma Pembagian Di Gaussian Integer [PDF]

Citation preview

Algoritma Pembagian di Gaussian Integer (versi Praktikum Komputasi Aljabar)



Wihikanwijna alias Mawi Wijna © 2008



Katakunci: Ring Komutatif, Daerah Euclid, Gaussian Integer, Algoritma Pembagian, Matlab



A. Latar Belakang Sebelumnya mohon maaf apabila kata-kata dan kalimat-kalimat yang saya pergunakan di artikel ini sepenuhnya tidak mengikuti kaidah Bahasa Indonesia yang baik dan benar sesuai EYD (Ejaan Yang Disempurnakan). Toh, ini juga bukan sebuah karya ilmiah kan? Ceritanya berawal dari saat aku mengikuti kuliah Peng. Struktur Aljabar II pada hari Rabu, 10 Desember 2008 yang diajar oleh Bu Indah Emilia Wijayanti. Suatu saat, ketika mengajar di kelas Bu Indah bertanya kepadaku,



[]



“Wijna, apa ada program yang bisa digunakan untuk menghitung gcd di ] i ? ” Terus terang waktu itu aku sedang tidak memperhatikan penjelasan Bu Indah, jadi aku jawab simpel saja, “Belum tahu ya Bu !” Sepertinya Bu Indah kurang puas dengan jawabanku. Aku juga jadi kepikiran, apaan sih itu gcd di



] [i ] . Kalau gcd sih aku ngerti, tapi kalau ] [i ] wah itu aku kurang begitu paham. Aku juga merasa bersalah, ikut kuliah Peng. Struktur Aljabar II tapi di kelas malah maen-maen dan nggak memperhatikan. Karena kata orang aku (masih) sedikit baik hati, aku membuka-buka lagi buku Aljabar



[]



(punya Andreas sih :p) buat mencari informasi tentang ] i . Ternyata setelah dipahami, cara mencari



[]



gcd di ] i nggak susah-susah amat. Tapi, ada modal awal yang harus dimiliki untuk menghitung gcd



[]



di ] i , yaitu Algoritma Pembagian. Dari contoh yang diberikan Bu Indah di papan tulis yang dikerjakan anak-anak Math ’07, aku mendapat inspirasi untuk membuat program Algoritma Pembagian



[]



di ] i . Yah...muncul lagi deh sifat kurang-kerjaanku, jadi dari pulang kuliah sampai di rumah aku terus mikir bagaimana caranya membuat itu program. Hmmm...



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 1



Ya, demi harga diri seorang Wijna yang pernah dibimbing tugas-akhirnya oleh Bu Indah, masak sih ngerjain yang kayak gini aja nggak bisa? Tapi maaf ya Bu, kalau saya bisanya hanya segini. Kalau dapet inspirasi lagi, nanti saya utak-atik lagi deh. Hehehe.



B. Dasar Teori Berikut diberikan beberapa definisi dan sifat mengenai Gaussian Integer. Definisi 1 (Pembagi Nol Sejati) Diketahui R ring. Jika terdapat a, b ∈ R dengan a ≠ 0 dan b ≠ 0 serta berlaku ab = 0 , maka a dan b disebut pembagi nol sejati pada R . Contoh: Pada ] 6 , elemen 2,3∈ ] 6 merupakan pembagi nol sejati karena 2 ≠ 0 , 3 ≠ 0 , dan 2.3 = 0 . Definisi 2 (Daerah Integral) Diketahui R ring komutatif dengan elemen satuan. Ring R disebut dengan daerah integral jika dan hanya jika R tidak memuat pembagi nol sejati. Contoh: a.) Ring ] 6 bukan daerah integral karena memuat pembagi nol sejati yaitu 2,3∈ ] 6 . b.) Ring ] 2 merupakan daerah integral karena tidak memuat pembagi nol sejati. Definisi 3 (Gaussian Integer)



[]



{



Himpunan ] i = a + bi a, b ∈ ] dan i = Contoh:



}



−1 , disebut dengan Gaussian Integer.



[]



[]



Elemen 2 + i, i, 5 ∈ ] i akan tetapi 1 + (1 2 ) i ∉ ] i karena 1 2 ∉ ] .



Berikut beberapa sifat dari Gaussian Integer: a.) Gaussian Integer merupakan himpunan bagian dari himpunan bilangan kompleks, yaitu



] [i ] ⊂ ^ .



b.) Gaussian Integer merupakan grup terhadap operasi penjumlahan bilangan kompleks. c.) Gaussian Integer merupakan ring terhadap operasi penjumlahan bilangan kompleks dan perkalian bilang kompleks.



[]



d.) Gaussian Integer merupakan ring dengan elemen satuan, karena 1 ∈ ] i . e.) Gaussian Integer merupakan ring komutatif. f.) Gussian Integer tidak memuat pembagi nol sejati. g.) Dari poin c.) , d.) , e.) dan f.) dapat disimpulkan bahwa Gaussian Integer merupakan daerah integral.



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 2



Lebih lanjut:



1, −1, i dan −i . i.) Gaussian Integer bukan lapangan, karena 2 ∈ ] [i ] tidak memiliki invers terhadap h.) Unit pada Gaussian Integer hanyalah



[]



perkalian di ] i .



[]



[]



j.) Untuk setiap a ∈ ] i dan a ≠ 0 , selalu terdapat b ∈ _ i sehingga ab = 1 .



Pada kuliah Peng. Struktur Aljabar II ditunjukkan bahwa Gaussian Integer merupakan Daerah Euclid.



( []



)



Yaitu terdapat fungsi v : ] i − {0} → ` 0 = {0,1, 2,3,...} yang memenuhi dua sifat berikut: (i).



v ( x ) ≤ v ( xy ) , untuk setiap x, y ∈ ] [i ] , x ≠ 0 dan y ≠ 0 .



(ii).



Untuk setiap x, y ∈ ] i , selalu terdapat p, r ∈ ] i sehingga berlaku



[]



[]



x = yp + r , dengan r = 0 atau v ( r ) < v ( y ) . Sifat (ii) disebut juga bahwa Algoritma Pembagian berlaku di Gaussian Integer. Fungsi v disebut fungsi evaluasi , dan fungsi evaluasi pada Gaussian Integer dinyatakan sebagai



v ( a + bi ) = a 2 + b 2 , untuk setiap a + bi ∈ ] [i ] .



C. Algoritma Pembagian Secara Aljabar



[]



Permasalahan yang muncul di Algoritma Pembagian adalah menentukan elemen p, r ∈ ] i



[]



sehingga berlaku x = yp + r , dengan r = 0 atau v ( r ) < v ( y ) untuk suatu x, y ∈ ] i yang telah ditentukan sebelumnya. Cara yang akan kupaparkan berikut ini merupakan generalisasi dari contoh yang diajarkan Bu Indah di kuliah Peng. Struktur Aljabar II.



[]



Menurut sifat Gaussian Integer di poin j.), untuk sebarang y ∈ ] i ditemukan y



−1



suatu a1 , a2 , b1 , b2 ∈ ] . Diperhatikan bahwa:



y −1



dan y ≠ 0 selalu dapat



∈ _ [i ] sehingga berlaku yy = 1 . Misalkan x = a1 + a2i dan y = b1 + b2i , untuk −1



=



1 y



=



1 b1 + b2i



=



⎛b −b i ⎞ 1 ⋅⎜ 1 2 ⎟ b1 + b2i ⎝ b1 − b2i ⎠



⎛ 1 ⎞ =⎜ 2 ⋅ b − b2i ) 2 ⎟ ( 1 ⎝ b1 + b2 ⎠ Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 3



dan



⎫⎪ ⎪⎧⎛ 1 ⎞ xy −1 = ( a1 + a2i ) ⎨⎜ 2 ⋅ b − b2i ) ⎬ 2 ⎟ ( 1 ⎪⎩⎝ b1 + b2 ⎠ ⎪⎭ ⎛ 1 ⎞ =⎜ 2 ⋅ a b + a2b2 ] + [ a2b1 − a1b2 ] i 2 ⎟ [ 1 1 ⎝ b1 + b2 ⎠ = dengan (i).



1 ( c1 + c2i ) d



d = b12 + b22 , c1 = a1b1 + a2b2 , dan c2 = a2b1 − a1b2 . Selanjutnya diperhatikan pula bahwa: Karena



a1 , a2 , b1 , b2 ∈ ] , akibatnya d , c1 , c2 ∈ ]



d = b12 + b22 dan b12 ≥ 0 serta b22 ≥ 0 (iii). Nilai d = 0 , jika dan hanya jika b1 = b2 = 0 , dengan kata lain y = 0 . Ini tidak mungkin terjadi karena diawal telah diasumsikan bahwa y ≠ 0 .



(ii).



Nilai d ≥ 0 , karena



q ∈ _ , terdapat m ∈ ] dan q ' ∈ _ sehingga 1 c e e 1 q = m + q ' dan q ' ≤ . Dengan demikian terdapat e1 , e2 ∈ ] , sehingga 1 = e1 + 2 dan 2 ≤ . 2 d d d 2 e c e 1 Dengan cara yang serupa 2 = e3 + 4 untuk suatu e3 , e4 ∈ ] dan 4 ≤ . d 2 d d Menurut sifat bilangan rasional, untuk setiap



Jadi



1 ( c1 + c2i ) dapat disajikan sebagai: d c c 1 ( c1 + c2i ) = 1 + 2 i d d d ⎛ e ⎞ ⎛ e ⎞ = ⎜ e1 + 2 ⎟ + ⎜ e3 + 4 ⎟ i d⎠ ⎝ d⎠ ⎝ ⎛e e ⎞ = ( e1 + e3 i ) + ⎜ 2 + 4 i ⎟ ⎝d d ⎠



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 4



dan karena



x = y ⋅ ( xy −1 ) , akibatnya:



⎛1 ⎞ = y ⋅ ⎜ ( c1 + c2i ) ⎟ ⎝d ⎠ ⎧⎪ ⎛ e e ⎞ ⎫⎪ = y ⎨( e1 + e3 i ) + ⎜ 2 + 4 i ⎟ ⎬ ⎪⎩ ⎝ d d ⎠ ⎪⎭ ⎛e e ⎞ = y ⋅ ( e1 + e3 i ) + y ⋅ ⎜ 2 + 4 i ⎟ . ⎝d d ⎠



x



(



[]



)



⎛ e2 e4 ⎞ + i ⎟ ∈ ] [i ] yang juga berakibat ⎝d d ⎠



Diperhatikan karena x ∈ ] i , akibatnya y ⋅ e1 + e3 i + y ⋅ ⎜



⎛ e' e' ⎞ y ⋅ ⎜ 2 + 4 i ⎟ ∈ ] [i ] . ⎝d d ⎠



D. Membuktikan v(r) < v(y) Masih tersisa satu tugas lagi, yaitu membuktikan



⎛ ⎛e e v ⎜ y ⋅⎜ 2 + 4 ⎝ ⎝d d



⎞⎞ i ⎟ ⎟ < v ( y ) . Diperhatikan ⎠⎠



bahwa:



⎛ ⎛ e e ⎞⎞ ⎛1 ⎞ v ⎜ y ⋅ ⎜ 2 + 4 i ⎟ ⎟ = v ⎜ ⋅ ( b1 + b2i ) ⋅ ( e2 + e4i ) ⎟ ⎝d ⎠ ⎝ ⎝ d d ⎠⎠ 1 2 2 = 2 ⋅ ⎡( b1e2 − b2 e4 ) + ( b1e4 − b2 e2 ) ⎤ ⎦ d ⎣ e22 + e42 . = d ⎛



⎞⎞ e2 + e2 i ⎟ ⎟ < v ( y ) , yaitu dengan menunjukkan 2 4 < d d ⎠⎠ ⎝ e22 + e42 e2 1 e4 1 ≤ , akibatnya lain < 1 . Karena ≤ dan 2 d d d 2 2 ⎛ e2 e4 + ⎝d d



Untuk menunjukkan bahwa v ⎜ y ⋅ ⎜ atau



dengan 2



kata



2



e2 e2 1 1 1 e e 1 1 1 ⎛ e2 ⎞ ⎛e ⎞ ⋅ ≤ ⋅ = dan ⎜ 4 ⎟ = 4 ⋅ 4 ≤ ⋅ = . Dengan demikian ⎜ ⎟ = d d 2 2 4 d d 2 2 4 ⎝d⎠ ⎝d⎠ e22 + e42 e22 e42 1 1 1 = 2 + 2 ≤ + = < 1. d2 d d 4 4 2



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 5



⎛e e ⎞ p = ( e1 + e3 i ) dan r = y ⋅ ⎜ 2 + 4 i ⎟ , sehingga berlaku: ⎝d d ⎠ x = yp + r , dengan r = 0 atau v ( r ) < v ( y ) .



Jadi, dapat dipilih



E. Algoritma Pembagian di Program Matlab Pada Matlab dibentuk empat m-file sebagai berikut:



evalgint.m function y=evalgint(A) y = A(1)^2 + A(2)^2; %dengan A : matriks ukuran 1 x 2



multgint.m function [a,b]=multgint(A,B) a1 = A(1)+A(2)*i; a2 = B(1)+B(2)*i; a = real(a1*a2); b = imag(a1*a2); %dengan A dan B : matriks ukuran 1 x 2



subrat.m function [x1,x2]=subrat(a,b) c = ceil(abs(a)/b); if ((c*b-abs(a))/b > evalgint([3 -1]) ans = 10 Artinya, mencari nilai



v ( 3 − i ) = 32 + ( −1) = 9 + 1 = 10 . 2



>> [m1,m2]=multgint([-4 2],[3 -1]) m1 = -10



m2 = 10



Artinya, menghitung perkalian ( −4 + 2i ) dengan ( 3 − i ) , yaitu ( −4 + 2i )( 3 − i ) = m1 + m2i = −10 + 10i .



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 9



>> [a,b]=subrat(3,4) a = 1



b = -1



Artinya,



−1 1 1 3 ⎛ −1 ⎞ = < . = 1 + ⎜ ⎟ dan 4 4 2 4 ⎝ 4 ⎠



>> [P, R] = divalggint([-5 -1],[3 -1]) P = -2



-1



2



0



R =



Artinya, ( −5 + i ) = ( 3 − i )( −2 − i ) + 2 .



G. Keterbatasan, Diskusi, dan Penutup Program yang aku buat jelas masih jauh dari kata sempurna. Ada banyak perulangan sintaks yang sepertinya bisa diringkas dan juga aku tidak memberikan algoritma yang meneliti input fungsi terlebih dahulu. Seperti bagaimana jika ada pengguna yang menjalankan evalgint([i -i])? Selain itu selama pengerjaan program ini, sempat muncul beberapa pertanyaan di benakku: a.) Jika R daerah Euclid terhadap fungsi evaluasi v , apakah ada fungsi evaluasi lain sebut saja v ' sehingga R juga merupakan daerah Euclid terhadap fungsi evaluasi v ' ?



[ ] tersebut adakah p ', r ' ∈ ] [i ] dengan tetap berlaku v ( r ' ) < v ( y ) .



b.) Apakah p, r ∈ ] i



yang memenuhi x = yp + r tunggal? Dengan kata lain



x = yp '+ r ' akan tetapi p ≠ p ' dan r ≠ r ' ? Dan juga



[]



a = xy untuk suatu x, y ∈ ] [i ] , apakah ada x ', y ' ∈ ] [i ] sehingga a = x ' y ' dan x ≠ x ' serta y ≠ y ' ?



c.) Misalkan a ∈ ] i dengan



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 10



d.) Program yang aku buat terbatas hanya pada Gaussian Integer. Hmm...bisakah juga dibuat program Algoritma Pembagian di ] ⎡



⎤ ⎣ p ⎦ misalnya, dengan p merupakan



bilangan prima? e.) Oh iya, program buat menghitung gcd-nya belum dibuat ya? Hehehe. Sekian dulu deh, artikelku ini. Semoga artikel ini bisa bermanfaat bagi orang banyak dan terutama melatih pemahaman mengenai pemrograman dengan Matlab. Mulai dari perumusan teori aljabar sampai membuat algoritmanya. Phew, benar-benar melelahkan! Jangan lupa, bagi yang mengambil Praktikum Komputasi Aljabar, harap artikel ini dipelajari karena mungkin aja keluar pas ujian akhir, hehehe. Kalau ada pertanyaan layangkan aja surat elektronik ke alamat e-mail di footer artikel ini atau sekalian saja kunjungi websitenya (promosi nih!). Akhir kata, terima kasih!



H. Referensi Inspriasi dari Sang Khalik yang muncul tiba-tiba di waktu dan tempat yang tak terduga. (God works in mysterious way...) Kuliah Peng. Struktur Aljabar II yang diterangkan oleh Bu Indah hari Rabu, 10-Desember-2008. Coret-coretan dan pekerjaannya Andreas, yang dengan terpaksa kusuruh dia menjadi buruh hitung bilangan kompleks. Dubinsky Ed, Learning Abstract Algebra with ISETL, Springer-Verlag, New York, 1994. Fraleigh J.B., A First Course In Abstract Algebra, Addison-Wesley, New York, 1994. The Mathworks Inc, (www.mathworks.com).



Algoritma Pembagian di Gaussian Integer (Versi Prak. Komputasi Aljabar) Mawi Wijna © 2008, (http://wijna.web.ugm.ac.id & [email protected]) 11