PENGANTAR GALOIS FIELD KONSTRUKSI SUATU …

Ü @ 4 Ü T Notasi sigma, ... tersebut didapat oleh penulis dari soal ”Olimpiade Matematika untuk Mahasiswa 2006” dalam bidang Struktur Aljabar. Pertany...

0 downloads 31 Views 751KB Size
 

 

PENGANTAR GALOIS FIELD KONSTRUKSI SUATU LAPANGAN BERHINGGA BERORDE PRIME POWER Skripsi untuk memenuhi sebagian persyaratan mencapai derajat Sarjana S-1

Program Studi Matematika

diajukan oleh Mahmudi 06610006

Kepada

PROGRAM STUDI MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UIN SUNAN KALIJAGA YOGYAKARTA 2010

qffi

Kaliiaga Sunan lslamNegeri Universitas

FM-UrNSK-BM-05-{|3IRO

SURAT PERSETUJUAI\I SKRIPSI/IUGAS AKHIR Hal

:

Lam

:

Kepada Yth. DekanFakultasSainsdanTeknologi UIN SunanKaldagaYogyakarta Di Yogyakarta Assalamu'alaikumwr. wb. Setelahmembaca,meneliti, memberikanpetunjuk dan mengoreksiserta mengadakanperbaikanseperlunya,maka kami selakupembimbing berpendapat bahwaskripsi saudara: Nama

: Mahmudi

NIM

:06610006

Judulskripsi

: Pengantar Galois Fietd, Konstruksi suatu Lapangan Berhingga Berorde Primc Power

sudah dapat diajukan kembali kepada Fakultas Sains dan Teknologi Progrart , Studi MatematikaUIN SunanKalijaga Yogyakartasebagaisalahsatusyaratuntuk memperolehgetarSarjanastrataSatudalamSains(Matematika) Denganini kami mengharapagar skripsiltugasakhir Saudaratersebutdi atas dapat segeradimunaqosyahkan.Atas perhatianyakami ucapakanterima kasih.

ii

@un*.rsitqs lslomNegeriSunonKotijogo

FM-UINSK-BM-05-07/R0

PENGESAHAN SKRIPST/TUGAS AKHIR Nomor urN.02/D.sr/PP.01. 1/686/2010

judul Skipsiffugas Akhirdengan

Pengantar GaloisField,Konstruksi suatuLapangan Berhingga BerordePrimefuwer

Yangdipersiapkan dandisusun oleh Nama NIM pada Telahdimunaqasyahkan NilaiMunaqasyah

Mahmudi 06610006 1 Maret2010 A

Dandinyatakantelah diterimaoleh FakultasSainsdaplknologi UIN SunanKalijaga

Dra.Hj,Khurul

PengujiII

M.Si NIP.

9^S

."*/$r1* '' \* \L:t' i,,/

%\g#,W'9

SffiX.ioiloi,r'r.si :19550427 1984032 001

PERNYATAAN KEASLIAN Denganini sayamenyatakanbahwaskripsi ini tidak terdapatkarya yang pernah diajukan untuk memperolehgelar kesarjanaandi suatu perguruantinggi, dan sepaqjangpengetahuansayajuga tidak terdapatkarya ataupcndapatyang pemah ditulis atau diterbitkan oleh oranglain, kecuali secaratertulis diacu dalamnaskah ini dandisebutkandalamdaftarpustaka.

Yogyakarta22 Februari2010

Mahmudi_ NrM.06610006

iv

 

 

KATA PENGANTAR

Allāhumma lakal-hamdu kulluhu, wa lakasy-syukru kulluhu, wa ilaika yurja`ul-amru kulluhu, ’alā niyyatuhu wa sirruhu, inna rabbi lasamī’ud-du’ā`i. Puji dan syukur hanya pantas terucapkan kepada Dzat Maha Penyayang di antara para penyayang, yang kepadaNya kembali segala urusan, yang atas segala karunia, hidayah, perkenan dan kehendakNya penulis dapat menyelesaikan penulisan skripsi ini. Shalawat dan salam semoga senantiasa tercurahkan kepada Nabi Muhammad SAW beserta keluarga, para sahabat dan para pengikutnya, yang dengan kehadiran Beliau telah menjadi rahmat buat sekalian alam. Penyusunan

skripsi

ini

dimaksudkan

untuk

memenuhi

sebagian

persyaratan guna memperoleh gelar Sarjana Program Studi Matematika. Skripsi ini berisi mengenai pembahasan konsep lapangan berhingga berorde prime power. Terselesaikannya skripsi ini juga tak dapat lepas dari berbagai pihak, oleh karena itu pada kesempatan ini penulis ingin mengucapkan terima kasih kepada pihak-pihak yang tersebutkan dibawah ini, semoga Allah jua-lah yang akan memberikan balasan. Amien. 1. Ibu Dra. Maizer Said Nahdi, M.Si., selaku Dekan Fakultas Sains dan Teknologi UIN Sunan Kalijaga Yogyakarta. 2. Ibu Sri Utami Zuliana, S.Si., M.Sc., selaku Ketua Program Studi Matematika dan juga selaku Dosen Penasehat Akademik yang telah memberikan pengarahan, motivasi, dan bimbingan selama penulis belajar di Program Studi Matematika Fakultas Sains dan Teknologi UIN Sunan Kalijaga Yogyakarta

v

 

 

3. Ibu Dra. Khurul Wardati, M.Si., selaku Dosen Pembimbing Skripsi yang telah bersedia meluangkan banyak waktu untuk memberi motivasi, bimbingan, petunjuk, saran, dan kritik selama penyusunan skripsi. 4. Bapak/Ibu Dosen dan seluruh staf karyawan Fakultas Sains dan Teknologi atas ilmu yang telah diberikan serta bantuan selama perkuliahan. 5. Ayah, Mak, dan Adek dirumah, atas segala kasih sayang, dukungan, motivasi dan kesabaran dalam penantian. Segala apa yang telah kalian curahkan untuk penulis, tiadalah cukup kata-kata untuk dapat penulis wakili. 6. Buat Nun, atas waktu dan perhatian yang telah terabaikan. 7. Buat sahabat-sahabatku di Prodi Matematika dan Prodi Pend. Matematika atas segala dukungan, waktu yang terluangkan untuk diskusi. Khususnya untuk teman-teman Matematika 2006. Penulis menyadari bahwa dalam penyusunan skripsi ini masih jauh dari sempurna, oleh karena itu dengan kerendahan hati penulis mengharapkan kritik dan saran kepada para pembaca skripsi. Semoga skripsi ini dapat bermanfaat bagi semua pihak. Yogyakarta, Februari 2010 Penulis

Mahmudi

vi

 

 

PERSEMBAHAN        

 

Ayah, Mak, dan Adek Meutia yang kucintai dan selalu kusayangi Teman-teman Matematika UIN SUNAN KALIJAGA Angkatan 2006 Almamater Fakultas Sainteks UIN SUKA Yogyakarta

vii

 

 

MOTTO

  uθèδuρ 4 ⎯Íνω÷èt/ .⎯ÏΒ …çμs9 Ÿ≅Å™öãΒ Ÿξsù ô7Å¡ôϑム$tΒuρ ( $yγs9 y7Å¡ôϑãΒ Ÿξsù 7πuΗ÷q§‘ ⎯ÏΒ Ä¨$¨Ψ=Ï9 ª!$# ËxtGøtƒ $¨Β z⎯ÏiΒ Νä3è%ã—ötƒ «!$# çöxî @,Î=≈yz ô⎯ÏΒ ö≅yδ 4 ö/ä3ø‹n=tæ «!$# |Myϑ÷èÏΡ (#ρãä.øŒ$# â¨$¨Ζ9$# $pκš‰r'¯≈tƒ ∩⊄∪ ãΛ⎧Å3ptø:$# Ⓝ͕yèø9$# ∩⊂∪ šχθä3sù÷σè? 4†¯Τr'sù ( uθèδ ωÎ) tμ≈s9Î) Iω 4 ÇÚö‘F{$#uρ Ï™!$yϑ¡¡9$# (2.) Apa saja yang Allah anugerahkan kepada manusia berupa rahmat, maka tidak ada seorangpun  yang dapat menahannya; dan apa saja yang ditahan oleh Allah maka tidak seorangpun yang sanggup  melepaskannya sesudah itu. Dan Dialah yang Maha Perkasa lagi Maha Bijaksana.  (3.) Hai manusia, ingatlah akan nikmat Allah kepadamu. Adakah Pencipta selain Allah yang dapat  memberikan rezki kepada kamu dari langit dan bumi ? tidak ada Tuhan selain Dia; maka mengapakah kamu  berpaling (dari ketauhidan)?    (Surah 35, Fathir; ayat 2‐3)       

∩∇⊄∪ ãβθä3uŠsù ⎯ä. …çμs9 tΑθà)tƒ βr& $º↔ø‹x© yŠ#u‘r& !#sŒÎ) ÿ…çνãøΒr& !$yϑ¯ΡÎ) 82. Sesungguhnya keadaan‐Nya apabila Dia menghendaki sesuatu hanyalah berkata kepadanya:  "Jadilah!" Maka terjadilah ia. 

(Surah 36, Yasin; ayat 82)

viii

 

 

DAFTAR ISI HALAMAN JUDUL .............................................................................................. i SURAT PERSETUJUAN SKRIPSI ..................................................................... ii HALAMAN PENGESAHAN .............................................................................. iii HALAMAN PERNYATAAN KEASLIAN .......................................................... iv KATA PENGANTAR .......................................................................................... v HALAMAN PERSEMBAHAN ............................................................................ vii HALAMAN MOTTO .......................................................................................... viii DAFTAR ISI ........................................................................................................ ix ARTI LAMBANG DAN SINGKATAN .............................................................. x ABSTRAKSI ...................................................................................................... xii BAB I. PENDAHULUAN .................................................................................... 1 1.1

Latar Belakang Masalah ......................................................................... 1

1.2

Batasan Masalah ..................................................................................... 3

1.3

Rumusan Masalah .................................................................................. 3

1.4

Tujuan Penelitian .................................................................................... 4

1.5

Manfaat Penelitian .................................................................................. 4

1.6

Tinjauan Pustaka .................................................................................... 4

BAB II. DASAR TEORI ...................................................................................... 6 2.1

Relasi ...................................................................................................... 6

2.2

Bilangan Bulat ...................................................................................... 10

2.3

Kongruensi ........................................................................................... 19

2.4

Ring ...................................................................................................... 29

2.5

Polinomial Ring .................................................................................... 41

2.6

Keterbagian dan Faktor Persekutuan Terbesar ..................................... 56

BAB III. METODE PENELITIAN .................................................................... 69 BAB IV. PEMBAHASAN .................................................................................. 71 4.1

Faktorisasi Polinomial di

............................................................. 71

4.2

Kelas-kelas Ekuivalen Polinomial ........................................................ 80

4.3

Konstruksi Lapangan Berhingga

............................................ 86

BAB V. PENUTUP ........................................................................................... 105 5.1

Simpulan ............................................................................................. 105

5.2

Saran-saran ......................................................................................... 105

DAFTAR PUSTAKA ....................................................................................... 107 ix

 

 

”Berakibat,” 20 atau Bukti implikasi ke arah kanan, 22 Bukti implikasi ke arah kiri, 22 0 , 1 , …,

1

  mod 

Kelas ekuivalen modulo , 23 tidak kongruen modulo , 23 Invers dari , 30 Himpunan semua bilangan rasional, 31 Himpunan semua bilangan real, 31

:

suatu pemetaan dari ring

, 39

oleh , 39

Bayangan dari elemen Polinomial dalam

ke ring

atas , 41

Kuantor universal, 41 ∑

Notasi sigma, 43 , ,

Maks

Nilai terbesar dari m, n, dan k, 47 Kuantor eksistensial, 52 , 52

isomorfis dengan der 

, 53

Derajat polinomial

Polinomial ring atas lapangan , 56 |

,

membagi mod 

,

kongruen modulo Kelas ekuivalen dari



tidak membagi dengan modulo

, 56

, 80 , 82

Himpunan polinomial dari semua kelas ekuivalen modulo

, 86

xi

 

 

ARTI LAMBANG DAN SINGKATAN

Himpunan semua bilangan bulat, 1 Himpunan semua kelas ekuivalen modulo , 1 Galois Field berorde , 2 ,2

Polinomial ring atas ,

Pasangan berurutan dari , , 6 elemen himpunan , 6 bukan elemen himpunan , 6 Perkalian kartesius dari ,

,

berelasi

dan , 6

dengan , 7

Kelas ekuivalen yang memuat , 8 himpunan bagian dari himpunan , 9 berelasi ekuivalen dengan , 9 Himpunan kosong, 9 Himpunan

beririsan dengan himpunan

Himpunan

dan

,9

adalah himpunan yang sama, 9

Teorema atau Akibat telah selesai dibuktikan, 9 pembagi bilangan , 11

|

bukan pembagi , 11 Biimplikasi, 13 Himpunan semua bilangan bulat positif di , 14 ,

, FPB ,   mod 

Faktor persekutuan terbesar dari kongruen

modulo , 19 x

dan , 16

Pengantar Galois Field, Konstruksi suatu Lapangan Berhingga Berorde Prime Power Oleh : Mahmudi (06610006) ABSTRAKSI Kongruensi modulo pada daerah integral adalah suatu relasi ekuivalen, sehingga terbentuk suatu partisi dalam , yang tiap himpunan bagiannya disebut dengan kelas ekuivalen. Himpunan semua kelas ekuivalen tersebut dinotasikan dan merupakan ring. Lebih lanjut untuk suatu , dengan prima, maka adalah lapangan berhingga berorde prima. Analogi dengan kongruensi modulo pada daerah integral adalah kongruensi modulo pada daerah integral , polinomial ring atas lapangan . Jika terdapat suatu lapangan dan polinomial berderajat maka akan dapat dibentuk suatu himpunan semua kelas ekuivalen modulo , ditulis ⁄ , yang memiliki elemen sebanyak . Khususnya untuk suatu polinomial tak tereduksi atas , maka ⁄ merupakan suatu lapangan berhingga berorde prime power. Lapangan berhingga tersebut dinotasikan . Lapangan berhingga akan memuat lapangan dan akar polinomial .

Kata kunci : kongruensi modulo

, polinomial tak tereduksi, prime power.

xii

 

 

BAB I PENDAHULUAN

1.1

Latar Belakang Masalah Materi aljabar abstrak yang telah penulis dapatkan adalah mengenai

konsep ring, daerah integral, dan lapangan. Salah satu contoh ring yang menarik untuk dipelajari adalah ring bilangan bulat, yaitu himpunan semua bilangan bulat, dinotasikan , yang dilengkapi dengan operasi penjumlahan  · ; ditulis ,

,

, · . Lebih lanjut, karena

dan pergandaan

tidak memuat pembagi nol maka

, · merupakan daerah integral. Salah satu sifat dari daerah integral

adalah berlakunya Algoritma

Pembagian sedemikian sehingga terdapat suatu relasi kongruensi pada , disebut relasi kongruensi modulo . Relasi kongruensi merupakan suatu relasi ekuivalen, sehingga terbentuk suatu partisi dalam

. Himpunan bagian dari partisi yang

terbentuk disebut kelas ekuivalen modulo ekuivalen modulo Selanjutnya pergandaan modulo prima maka

. Himpunan dari semua kelas

.

dinotasikan dengan

yang dilengkapi dengan operasi penjumlahan dan akan membentuk ring. Khususnya, untuk

adalah lapangan, yang dinotasikan

suatu bilangan

. Lapangan berhingga

merupakan suatu struktur lapangan berhingga yang sudah umum diketahui, yaitu lapangan berhingga berorde prima. Lapangan berhingga berorde prima adalah lapangan yang memiliki elemen sebanyak suatu bilangan prima tertentu.

1



 

Suatu kasus yang dihadapi penulis adalah pertanyaan mengenai struktur . Kasus

lapangan yang terbentuk dari polinomial ring atas lapangan berhingga

tersebut didapat oleh penulis dari soal ”Olimpiade Matematika untuk Mahasiswa 2006” dalam bidang Struktur Aljabar. Pertanyaannya adalah sebagai berikut : ”Perhatikan ring polinom ideal

yang

dibangun



, notasi

dan jika oleh

.

menyatakan

Bilangan

sehingga

1 membentuk field adalah …”

Dalam penelitian mandiri yang telah dilakukan oleh penulis, jawaban yang didapatkan adalah suatu lapangan yang tidak berorde prima, akan tetapi lapangan berhingga berorde 27. Bilangan 27 bukanlah suatu bilangan prima tetapi prime power, yaitu pangkat suatu bilangan prima dan dalam kasus ini 27

3 . Dengan

demikian terdapat suatu lapangan berhingga berorde prime power. Lapangan berhingga seperti ini disebut Galois Field, dinotasikan bilangan prima dan

dengan

,

bilangan bulat positif.

Berdasarkan hasil tersebut, penulis tertarik untuk menjadikan tema Galois Field sebagai bahan penelitian tugas akhir penulis. Penelitian ini merupakan penelitian pengembangan dari materi-materi aljabar abstrak yang telah didapatkan oleh penulis, yaitu konsep lapangan berhingga ring , dinotasikan

dan konsep polinomial ring atas

.

Perpaduan kedua konsep tersebut menghasilkan suatu konsep daerah integral

, sehingga dapat dilakukan perbandingan pada sifat-sifat yang

dimiliki oleh daerah integral lapangan berhingga

, terutama yang berkaitan dengan terbentuknya

, dengan sifat-sifat yang dimiliki daerah integral

.



 

Dengan demikian berdasarkan analogi kedua konsep tersebut, diharapkan pada akhir penelitian ini penulis dapat mengkontruksikan beberapa lapangan berhingga berorde prime power dan dapat mengetahui sifat-sifatnya.

1.2

Batasan Masalah Pembatasan masalah diperlukan dalam suatu penelitian ilmiah karena

dapat membantu penulis untuk fokus pada suatu objek penelitian. Demikian juga dengan penelitian yang penulis lakukan. Dikarenakan bilangan yang merupakan hasil pangkat suatu bilangan prima tak berhingga banyaknya, maka diperlukan batasan orde dari lapangan berhingga yang akan dikonstruksi. Penelitian ini akan difokuskan pada konstruksi lapangan berhingga berorde prime power, 

dengan

10, serta dikaji juga beberapa sifat

yang terdapat dalam struktur lapangan berhingga tersebut.

1.3

Rumusan Masalah Berdasarkan latar belakang dan batasan masalah yang telah diuraikan,

maka dirumuskan permasalahan sebagai berikut: 1. Bagaimanakah konsep lapangan berhingga berorde prime power ? 2. Bagaimanakah terbentuknya suatu lapangan berhingga berorde prime power ? 3. Bagaimanakah sifat-sifat yang dimiliki oleh lapangan berhingga berorde prime power ?



 

1.4

Tujuan Penelitian Tujuan penelitian ini adalah : 1. Mengkaji tentang konsep lapangan berhingga berorde prime power 2. Mengkaji cara terbentuknya lapangan berhingga berorde prime power 3. Mengkaji sifat-sifat lapangan berhingga berorde prime power

1.5

Manfaat Penelitian Hasil penelitian ini diharapkan dapat memberikan beberapa manfaat, di

antaranya sebagai berikut : 1. Memberikan pengetahuan tentang struktur lapangan berhingga berorde prime power. 2. Memberikan pengetahuan cara mencari dan membentuk suatu struktur lapangan berhingga berorde prime power. 3. Memberikan

motivasi

kepada

peneliti-peneliti

selanjutnya

untuk

mengembangkan penelitian mengenai Galois Field.

1.6

Tinjauan Pustaka Sumber pokok dalam penulisan skripsi ini adalah buku yang ditulis oleh

Thomas W Hungerford, yang berjudul Abstract Algebra : An Introduction. Penulis mengacu pada Chapter 4: Arithmetic in in

dan Chapter 5: Congruence

and Congruence-Class Arithmetic. Selain itu, dalam penulisan tugas akhir ini penulis juga menggunakan

suatu tinjauan pustaka sebuah tesis berjudul ”Galois Field”, yang ditulis oleh



 

mahasiswa pasca sarjana UGM, Bambang Irawanto. Dalam tesis tersebut, Bambang Irawanto membahas mengenai syarat perlu dan cukup suatu lapangan berhingga dengan

elemen,

prima dan bilangan bulat

1. Tesis tersebut

juga berisikan pembahasan mengenai hubungan antara lapangan pemisah dengan Galois Field serta penggunaan elemen-elemen Galois Field untuk mengkonstruksi sistem geometri dan pembentukan bujur sangkar latin yang saling orthogonal. Pembahasan tesis tersebut memberikan suatu gambaran terdapatnya suatu lapangan berhingga berorde prime power. Hal ini penulis jadikan sebagai landasan untuk mengkaji suatu metode yang berbeda dalam pembentukan struktur lapangan berhingga berorde prime power. Metode yang penulis pilih adalah dengan menggunakan konsep kongruensi pada struktur daerah integral

. Sedangkan

dalam tesis tersebut, Bambang Irawanto menggunakan konsep ideal maksimal pada daerah integral

.

 

 

BAB V PENUTUP 5.1

Simpulan Berdasarkan hasil studi literatur yang telah penulis lakukakan mengenai

konsep lapangan berhingga berorde prime power, maka dapat diambil simpulan sebagai berikut: 1. Terdapat suatu ring berhingga berorde kelas ekuivalen modulo ⁄

, yaitu himpunan dari semua , dinotasikan

atas suatu lapangan

, yang berbentuk ⁄

, .

dengan operasi penjumlahan dan pergandaan modulo 2. Jika

polinomial tak tereduksi di

, maka himpunan



merupakan lapangan, yaitu lapangan berhingga berorde prime power, dinotasikan

, dengan

3. Lapangan berhingga memuat lapangan

5.2

bilangan prima dan

1.

merupakan suatu lapangan perluasan yang dan akar polinomial tak tereduksi

.

Saran-saran Berdasarkan pada proses penelitian yang telah penulis lakukan, maka

dapat disampaikan beberapa saran berikut: 1. Penelitian ini hanya dibatasi pada salah satu cara untuk mengkontruksi lapangan berhingga berorde prime power, yaitu dengan menggunakan sifat kongruensi pada daerah integral

105

, diharapkan ada penelitian lebih

106 

 

lanjut mengenai metode-metode yang lain yang memungkinkan untuk membentuk struktur lapangan berhingga berorde prime power. 2. Penelitian ini juga hanya mencakup pembahasan mengenai polinomial tak tereduksi berorde 2 dan 3, sehingga dimungkinkan dilakukan penelitian pengembangan mengenai struktur lapangan berhingga dengan polinomial tak tereduksi berorde lebih besar dari tiga. Demikian saran-saran yang dapat disampaikan oleh penulis. Semoga skripsi ini dapat menjadi inspirasi bagi pembaca untuk mengembangkan lebih lanjut tentang konsep lapangan berhingga berorde prime power khususnya, dan konsep aljabar abstrak pada umumnya.

 

 

DAFTAR PUSTAKA Arifin, Ahmad. 2000. Aljabar. Bandung : Penerbit ITB. Bhattacharya, P. B., S.K. Jain, dan S.R. Nagpaul. 1994. Basic Abstract Algebra. Second Edition. Cambridge : Cambridge University Press. Cherowitzo, William E. ”Introduction to Finite Fields.” [html document]. Di Akses dari Catatan Kuliah Online : http://www-math.cudenver.edu/ ~wcherowi /courses/finflds.html. Fraleigh, John B. 2002. A First Course in Abstract Algebra. Seventh Edition. Addison Wesley. Gilbert, Jimmie dan Linda Gilbert. 2000. The Elements Of Abstract Algebra. Fifth Edition. USA : Brook/Cole. Gallian, Joseph A. 1990. Contemporary Abstract Algebra. Second Edition. Toronto : D. C. Heath Company. Herstein, I.N. 1996. Abstract Algebra. Third Edition. USA : Prentice – Hall, Inc. Hungerford, Thomas W. 1990. Abstract algebra: an introduction. First Edition. Philadelphia : Saunders College. Irawanto, Bambang. 2001. “Galois Field.” Tesis Pasca Sarjana, Universitas Gadjah Mada.

107