BAB II TEORI DASAR. untuk setiap e G. 4. G mengandung balikan. Untuk setiap a G, terdapat b G sehingga a b =

BAB II TEORI DASAR

2.1.

Group Misalkan operasi biner ∗ didefinisikan untuk elemen-elemen dari himpunan G.

Maka G adalah grup dengan operasi * jika kondisi di bawah ini terpenuhi : 1. 𝐺 tertutup terhadap ∗. Yaitu, jika 𝑥 ∈ 𝐺 dan 𝑦 ∈ 𝐺 maka 𝑥 ∗ 𝑦 ∈ 𝐺 2. ∗ bersifat asosiatif. Untuk semua 𝑥, 𝑦, 𝑧 ∈ 𝐺, 𝑥 ∗ 𝑦 ∗ 𝑧 = 𝑥 ∗ 𝑦 ∗ 𝑧. 3. 𝐺 memiliki elemen identitas 𝑒. Terdapat 𝑒 di 𝐺 sehingga 𝑥 ∗ 𝑒 = 𝑒 ∗ 𝑥 = 𝑥 untuk setiap 𝑒 ∈ 𝐺. 4. 𝐺 mengandung balikan. Untuk setiap 𝑎 ∈ 𝐺, terdapat 𝑏 ∈ 𝐺 sehingga 𝑎 ∗ 𝑏 = 𝑏 ∗ 𝑎 = 𝑒.

2.1.1. Grup Abelian Misalkan 𝐺 grup dengan operasi ∗. Maka 𝐺 disebut grup komutatif atau grup abelian, jika ∗ komutatif. Oleh karena itu, 𝑥 ∗ 𝑦 = 𝑦 ∗ 𝑥 untuk semua 𝑥, 𝑦 ∈ 𝐺. Contoh : a. Himpunan semua bilangan kompleks adalah grup abelian dengan operasi penjumlahan b. Himpunan bilangan rasional tak nol adalah grup abelian dengan operasi perkalian

2.1.2. Grup siklis Misalkan 𝐺 adalah grup. Untuk sebarang 𝑎 ∈ 𝐺, subgroup 𝐻 = {𝑥 ∈ 𝐺|𝑥 = 𝑎𝑛 untuk 𝑛 ∈ ℤ} adalah subgrup yang dibangkitkan oleh a dan dinotasikan oleh 𝑎 . Subgrup 𝐾 dari grup G dikatakan subgroup siklis jika ada elemen 𝑏 di 𝐺 sehingga

4

𝐾 = 𝑏 = {𝑦 ∈ 𝐺|𝑦 = 𝑏𝑛 untuk beberapa 𝑛 ∈ ℤ}. Dalam kasus tertentu, G adalah grup siklis jika ada elemen 𝑎 ∈ 𝐺 sedemikian sehingga 𝐺= 𝑎. Contoh : a. Himpunan ℤ bilangan bulat adalah grup siklis atas operasi penjumlahan. Kita bias lihat bahwa ℤ = 1 dan ℤ = −1 . b. Subgrup 𝔼 ⊆ ℤ, himpunan semua bilangan genap adalah subgroup siklis terhadap operasi penjumlahan di ℤ, yang dibangun oleh 2, dengan demikian 𝔼= 2. c. Operasi multiplikatif didefinisikan di ℤ10 sebagai 𝑎 𝑏 = 𝑎𝑏 . Aturan ini menunjukkan bahwa operasi ini adalah operasi yang asosiatif, dan ℤ10 tertutup terhadap operasi ini. Juga bahwa 1 adalah elemen identitas. Akan tetapi, ℤ10 bukanlah grup dengan operasi perkalian karena beberapa elemen darinya tidak memiliki invers. Sebagai contoh, hasil perkalian

2 0 = 0

2 5 = 0

2 1 = 2

2 6 = 2

2 2 = 4

2 7 = 4

2 3 = 6

2 8 = 6

2 4 = 8

2 9 = 8

Menunjukkan bahwa 2 𝑥 = 1 tidak memiliki solusi di ℤ10 . Sekarang mari kita menjabarkan tabel perkalian dari subhimpunan 𝐻=

2 , 4 , 6 , 8 dari ℤ10

5

X

2

4

6

8

2

4

8

2

6

4

8

6

4

2

6

2

4

6

8

8

6

2

8

4

Tabel di atas menunjukkan bahwa 6 adalah elemen identitas dari 𝐻 dan 𝐻 adalah sebuah grup dengan operasi perkalian. Akan tetapi 𝐻 bukanlah subgroup dari ℤ10 karena ℤ10 bukanlah sebuah grup dengan operasi perkalian. 𝐻 juga merupakan grup komutatif atau grup abelian dengan operasi perkalian. Karena [2]2 = 4 , 2

3

= 8, 2

4

= 6

maka 𝐻= 2 .

2.1.3. Subgroup Misalkan 𝐺 adalah grup dengan operasi biner ∗. Sebuah sub himpunan 𝐻 dari 𝐺 dikatakan subgroup dari 𝐺 jika 𝐻 membentuk sebuah grup dengan operasi biner ∗ yang didefinisikan di 𝐺. Contoh : a. Himpunan ℤ dari semua integer adalah grup dengan operasi penjumlahan dan himpunan 𝔼 atas bilangan asil genap adalah sebuah subgrup di ℤ. b. Himpunan semua bilangan kompleks tak nol membentuk sebuah grup terhadap operasi perkalian, dan 𝐺 = {1, −1, 𝑖, −𝑖} adalah sebuah subgroup dari grup ini.

2.1.4. Orde Banyaknya elemen dari sebuah grup 𝐺 dinamakan orde dari 𝐺, dan dinotasikan sebagai 𝑜(𝐺) atau |𝐺|.

2.2.

Gelanggang Sistem matematika (𝑅, +,∗) dikatakan gelanggang jika memenuhi sifat berikut :

6

a. Terhadap operasi tambah, (𝑅, +) membentuk grup komutatif. b. Terhadap operasi kali, (𝑅,∗) memenuhi sifat asosiatif. Untuk setiap 𝑎, 𝑏, 𝑐 ∈ 𝑅 maka 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ (𝑏 ∗ 𝑐). c. Terhadap operasi tambah dan kali, memenuhi sifat distributif. Untuk setiap 𝑎, 𝑏, 𝑐 ∈ 𝑅 maka 𝑎 ∗ 𝑏 + 𝑐 = 𝑎 ∗ 𝑏 + (𝑎 ∗ 𝑐) dan 𝑎 + 𝑏 ∗ 𝑐 = 𝑎 ∗ 𝑐 + 𝑏∗𝑐 .

2.3.

Lapangan Lapangan adalah sebuah sistem matematika (𝐿, +,∙) yang memiliki axiom

sebagai berikut : a. Tertutup terhadap operasi penjumlahan dan perkalian. Untuk setiap 𝑎, 𝑏 ∈ 𝐿, 𝑎 + 𝑏 ∈ 𝐿 dan 𝑎 ∙ 𝑏 ∈ 𝐿 b. Sifat asosiatif perkalian dan penjumlahan Untuk setiap 𝑎, 𝑏 dan 𝑐 ∈ 𝐿 berlaku 𝑎 + 𝑏 + 𝑐 = 𝑎 + 𝑏 + 𝑐 dan 𝑎 ∙ 𝑏 ∙ 𝑐 = (𝑎 ∙ 𝑏) ∙ 𝑐. c. Komutatif terhadap oerasi penjumlahan dan perkalian Untuk setiap 𝑎 dan 𝑏 ∈ 𝐿, berlaku 𝑎 + 𝑏 = 𝑏 + 𝑎 dan 𝑎 ∙ 𝑏 = 𝑏 ∙ 𝑎. d. Identitas penjumlahan dan identitas perkalian Terdapat sebuah elemen di 𝐿, kita sebut sebagai identitas penjumlahan dan dinotasikan sebagai 0, sehingga untuk semua 𝑎 ∈ 𝐿, 𝑎 + 0 = 0 + 𝑎 = 𝑎. Demikian juga, terdapat sebuah elemen di 𝐿, kita sebut sebagai identitas perkalian, dinotasikan sebagai 1, sehingga untuk setiap 𝑎 ∈ 𝐿, 𝑎 ∙ 1 = 1 ∙ 𝑎 = 𝑎. Untuk alasan teknis, identitas penjumlahan dan identitas perkalian disarankan berbeda. e. Balikan penjumlahan dan balikan perkalian Untuk setiap 𝑎 di 𝐿, terdapat – 𝑎 ∈ 𝐿, sehingga 𝑎 + (−𝑎) = 0. Demikian juga halnya untuk setiap 𝑎 ∈ 𝐿 bukan 0, terdapat sebuah elemen 𝑎−1 ∈ 𝐿, sehingga 𝑎 ∙ 𝑎−1 = 1 (penulisan 𝑎 + (−𝑏) dan 𝑎 ∙ 𝑏 biasa ditulis 𝑎 − 𝑏 dan 𝑎/𝑏). dengan kata lain, 𝐿 memiliki operasi pengurangan dan pembagian f. Distributif terhadap penjumlahan atas perkalian Untuk setiap 𝑎, 𝑏 dan 𝑐 ∈ 𝐿, berlaku 𝑎 ∙ (𝑏 + 𝑐) = (𝑎 ∙ 𝑏) + (𝑎 ∙ 𝑐).

7

2.3.1. Lapangan Hingga Lapangan hingga adalah lapangan yang jumlah elemennya terbatas, biasa dinamakan Lapangan Galois. Orde dari lapangan hingga selalu prima atau hasil pemangkatan bilangan prima. Misalkan 𝑝 adalah bilangan prima. Definisikan ℤ𝑝[𝑥] sebagai himpunan semua polinom dengan variable bebas 𝑥 dan koefisien-koefisiennya adalah anggota dari ℤ𝑝 , yaitu himpunan bilangan bulat modulo 𝑝. Dengan mendefinisikan penambahan dan perkalian pada polinom dengan cara yang biasa (dan mereduksi koefisien dengan modulo 𝑝), kita sudah membuat sebuah gelanggang. Untuk 𝑓(𝑥), 𝑔(𝑥) ∈ ℤ𝑝 [𝑥], kita katakan 𝑓(𝑥) membagi 𝑔(𝑥) (notasinya 𝑓 𝑥 |𝑔(𝑥)) jika terdapat 𝑞(𝑥) ∈ ℤ𝑝 [𝑥] sehingga 𝑔(𝑥) = 𝑞(𝑥)𝑓(𝑥).

Untuk 𝑓(𝑥) ∈ ℤ𝑝 [𝑥], definisikan 𝑑𝑒𝑔(𝑓), derajat 𝑓, sebagai pangkat tertinggi dari 𝑥 di 𝑓. Misalkan 𝑓(𝑥), 𝑔(𝑥), 𝑕(𝑥) ∈ ℤ𝑝 [𝑥], dan 𝑑𝑒𝑔(𝑓) = 𝑛 ≥ 1. Kita definisikan 𝑔(𝑥) ≡ 𝑕(𝑥)(𝑚𝑜𝑑𝑓(𝑥)) Jika 𝑓(𝑥)|(𝑔(𝑥) − 𝑕(𝑥)).

Kita bisa melihat kemiripan definisi kongruen pada polinom dengan definisi kongruen pada bilangan asli. Sekarang kita akan mendefinisikan sebuah gelanggang polinom “modulo 𝑓(𝑥)” yang dinotasikan dengan ℤ𝑝 𝑥 /𝑓(𝑥). Konstruksi dari ℤ𝑝 𝑥 /𝑓 𝑥 dari ℤ𝑝 𝑥 dibuat atas ide kongruen modulo 𝑓(𝑥) dan sejalan dengan konstruksi ℤ𝑚 dari ℤ. Misalkan 𝑑𝑒𝑔(𝑓) = 𝑛. Jika kita membagi 𝑔(𝑥) dengan 𝑓(𝑥), kita mendapatkan hasil bagi 𝑞(𝑥) dan sisa 𝑟(𝑥), dimana 𝑔(𝑥) = 𝑞(𝑥)𝑓(𝑥) + 𝑟(𝑥)

8

dan 𝑑𝑒𝑔(𝑟) < 𝑛

Ini bisa diselesaikan dengan menggunakan cara pembagian polinom biasa. Dengan demikian setiap polinom di ℤ𝑝 𝑥 kongruen modulo 𝑓 𝑥 terhadap tepat satu polinom dengan derajat paling besar 𝑛 − 1. Semua polinom di ℤ𝑝 𝑥 /𝑓 𝑥 berderajat maksimal 𝑛 − 1. Operasi tambah dan kali di ℤ𝑝 𝑥 /𝑓 𝑥 sama dengan operasi tambah dan kali di ℤ𝑝 𝑥 yang diikuti dengan reduksi modulo 𝑓 𝑥 . Dengan operasi-operasi di atas maka ℤ𝑝 𝑥 /𝑓 𝑥 adalah sebuah gelanggang. Dengan mengingat ℤ𝑚 adalah lapangan jika dan hanya jika 𝑚 adalah bilangan prima, dan balikan terhadap perkalian dapat ditemukan dengan menggunakan algoritma Euclidean. Situasi yang sama berlaku di ℤ𝑝 𝑥 /𝑓 𝑥 . Analogi dari sifat prima bilangan asli pada polinom adalah sifat tidak tereduksi.

Polinom yang Tidak Tereduksi Sebuah polinom 𝑓(𝑥) ∈ ℤ𝑝 [𝑥] disebut tidak tereduksi jika tidak terdapat polinom polinom 𝑓1 (𝑥), 𝑓2 (𝑥) ∈ ℤ𝑝 [𝑥] sehingga 𝑓 𝑥 = 𝑓1 (𝑥)𝑓2 (𝑥) dimana 𝑑𝑒𝑔(𝑓1 ) > 0 dan 𝑑𝑒𝑔(𝑓2 ) > 0. Fakta yang sangat penting adalah ℤ𝑝 𝑥 /𝑓 𝑥 adalah sebuah lapangan jika dan hanya jika f(x) tak tereduksi. Lebih jauh, balikan perkalian di ℤ𝑝 𝑥 /𝑓 𝑥

dapat

dihitung dengan menggunakan modifikasi dari algoritma Euclidean. Contoh : Mari kita coba mengkonstruksi sebuah lapangan dengan delapan elemen. Ini dapan diselesaikan dengan sebuah polinom tak tereduksi berderajat tiga di ℤ2 𝑥 . Polinom yang seperti itu haruslah memiliki suku konstanta 1, karena semua polinom yang memiliki suku 0 dapat dibagi oleh x oleh karena itu dpat direduksi. Ada empat polinom seperti yang diinginkan : 9

𝑓1 (𝑥) = 𝑥 3 + 1 𝑓2 𝑥 = 𝑥 3 + 𝑥 + 1 𝑓3 (𝑥) = 𝑥 3 + 𝑥 2 + 1 𝑓4 (𝑥) = 𝑥 3 + 𝑥 2 + 𝑥 + 1. Sekarang, 𝑓1 (𝑥) dapat direduksi, karena 𝑥 3 + 1 = (𝑥 + 1)(𝑥 2 + 𝑥 + 1)

(kita ingat koefisien polinom haruslah modulo2). Demikian juga dengan 𝑓4 (𝑥) dapat direduksi, karena 𝑥 3 + 𝑥 2 + 𝑥 + 1 = (𝑥 + 1)(𝑥 2 + 1). Akan tetapi 𝑓2 (𝑥) dan 𝑓3 (𝑥), keduanya dapat direduksi, dan salah satu dapat digunakan untuk mengkonstruksi sebuah lapangan dengan delapan elemen. Mari kita menggunakan 𝑓2 (𝑥), maka delapan elemen dari ℤ2 𝑥 / 𝑥 3 + 𝑥 + 1 adalah: 0, 1, 𝑥, 𝑥 + 1, 𝑥 2 , 𝑥 2 + 1, 𝑥 2 + 𝑥 dan 𝑥 2 + 𝑥 + 1. Untuk menghitung hasil kali dari dua elemen lapangan, kita mengalikan keduanya dan kemudian reduksi modulo 𝑥 3 + 𝑥 + 1 dan menemukan sisanya sebagai hasil kali. Karena kita membagi polinom dengan sebuah polinom berderajat tiga, maka sisanya akan memiliki derajat paling besar dua. Dengan demikian hasil tersebut adalah elemen dari lapangan. Sebagai contoh, untuk menghitung (𝑥 2 + 1)(𝑥 2 + 𝑥 + 1) di ℤ2 𝑥 / 𝑥 3 + 𝑥 + 1 , pertama kita menghitung hasil kali di ℤ𝑝 𝑥

yaitu 𝑥 4 + 𝑥 3 + 𝑥 + 1, Lalu

membaginya dengan 𝑥 3 + 𝑥 + 1, kita dapatkan ekspresi 𝑥 4 + 𝑥 3 + 𝑥 + 1 = 𝑥 + 1 𝑥3 + 𝑥 + 1 + 𝑥 2 + 𝑥 Dengan demikian di ℤ2 𝑥 / 𝑥 3 + 𝑥 + 1 , kita memperoleh bahwa

10

𝑥 + 1 𝑥 2 + 𝑥 + 1 = 𝑥 2 + 𝑥.

Di bawah ini adalah table perkalian dari sebuah elemen tak nol. Untuk menghemat tempat kita tuliskan polinom 𝑎2 𝑥 2 + 𝑎1 𝑥 + 𝑎0 sebagai tiga terurut 𝑎2 𝑎1 𝑎0 001 010 011 100 101 110 111 001 001 010 011 100 101 110 111 010 010 100 110 011 001 111 101 011 011 110 101 111 100 001 010 100 100 011 111 110 010 101 001 101 101 001 100 010 111 011 110 110 110 111 001 101 011 010 100 111 111 101 010 001 110 100 011

Menghitung balikan perkalian dapat

mengadaptasi langsung algoritma

Euclidean. Grup perkalian dari elemen-elemen tak nol dalam lapangan ini berorde tujuh. Karena 7 adalah bilangan prima, oleh karena itu setiap anggota tak nol dari lapangan ℤ2 𝑥 / 𝑥 3 + 𝑥 + 1 adalah generator dari grup ini. Sebagai contoh, jika kita menghitung hasil pangkat dari x, kita akan mendapatkan : 𝑥1 = 𝑥 𝑥2 = 𝑥2 𝑥3 = 𝑥 + 1 𝑥4 = 𝑥2 + 𝑥 𝑥5 = 𝑥2 + 𝑥 + 1 𝑥6 = 𝑥2 + 1 𝑥 7 = 1,

Yang mengandung semua unsur tak nol dari lapangan tersebut.

11

Untuk selanjutnya penulisan ℤ2 𝑥 /𝑓 𝑥 akan ditulis menjadi 𝐺𝐹(2𝑚 ), dan elemen elemennya ditulis dalam pasangan terurut koefisien-koefisienya, dengan 𝑚 adalah pangkat tertinggi dari 𝑓(𝑥).

12