TUGAS KAPITA SELEKTA KELOMPOK ALJABAR
FIELD BERHINGGA
DOSEN PEMBINA: DR. AGUNG LUKITO, M.S.
OLEH: MOH. HAFIYUSHOLEH (117936019)
PROGRAM STUDI S3 PENDIDIKAN MATEMATIKA UNIVERSITAS NEGERI SURABAYA 2012 0
4. FIELD BERHINGGA
Suatu pesan dalam dunia digital biasanya dibuat dalam bentuk kode atau sandi. Kode adalah daftar kata atau simbol yang mengganti secara khusus kata lain. Dalam proses pengiriman pesan yang telah diubah ke dalam bentuk kode sering mengalami gangguan (noise) sehingga menyebabkan pesan yang dikirim keliru. Untuk mengatasi kesalahan (error) dalam sistem komunikasi, maka diperlukan suatu sistem yang dapat mengoreksi error tersebut. Sistem yang dimaksud adalah sistem pengkodean. Kode yang biasa digunakan dalam proses koreksi error antara lain kode Hamming yang mampu mengoreksi satu kesalahan (single error), kode BCH yang mampu mengoreksi dua kesalahan (double error), kode Golay yang mampu mengoreksi tiga kesalahan (triple error), dan juga terdapat kode Reed Solomon yang mampu mengoreksi multiple error. Field berhingga merupakan konsep yang sangat penting untuk mengkonstruksi multiple-error-correcting codes. Pengetahuan mengenai field berhingga
dipergunakan
agar memahami kelas terpenting dari pengkodean siklis. Pertama-tama kita akan mendiskusikan group secara singkat, karena konsep menegnai group diperlukan dalam teori field berhingga.
4.1 Grup Grup G adalah himpunan elemen-elemen dan sebuah operasi, sebut *, yang memenuhi sifat-sifat sebagai berikut: i. G tertutup terhadap operasi *, yaitu, jika g , h G , maka berlaku g * h G ii. Operasi * adalah asosiatif iii.G mempunyai sebuah identitas e sedemikian sehingga g * e e * g g , g G iv. Untuk setiap unsure g di G mempunyai sebuah invers, yang dilambangkan dengan g 1 sedemikian sehingga berlaku g * g 1 g 1 * g e Dapat ditunjukkan bahwa pada suatu grup, elemen identitasnya adalah tunggal dan invers dari setiap elemen juga tunggal. Grup G disebut abelian jika berlaku g*h = h*g untuk setiap g,h di G. Pada kajian ini kita hanya akan memperhatikan grup abelian. Contoh: Kode C adalah grup abelian 1
terhadap operasi +. Elemen identitasnya adalah vektor nol. Jika C adalah suatu kode biner, maka setiap vektor adalah inversnya sendiri. Definisi suatu field dapat dinyatakan dalam pengertian grup. Suatu field F adalah himpunan elemen-elemen dengan dua operasi, yaitu
operasi + (penjumlahan) dan *
(perkalian) sedemikian hingga F adalah grup abelian dibawah operasi +, dan elemen tak nol dalam F merupakan grup abelian dibawah operasi * dan memenuhi sifat distributif. Untuk selanjutnya lambang operasi grup ”*” akan diganti dengan lambang ”.”. Dalam notasi (g*g*g*……*g) dengan g sebanyak r ditulis gr. Untuk operasi +, hasil dari g + g +….+ g, dengan g sebanyak r, ditulis rg dan g-1 ditulis –g. Order suatu grup G adalah banyaknya elemen-elemen didalam grup itu dan kita nyatakan hanya di grup berhingga. Order suatu elemen g dalam grup G adalah bilangan bulat positip terkecil r sedemikian hingga gr = e. Perhatikan bahwa elemen order r mempunyai r perpangkatan yang berbeda Subgrup H dari G adalah subset dari G yang merupakan suatu grup dengan operasi yang sama seperti di G.
Teorema 23 (Lagrange): Order subgrup H dari G membagi order G. Bukti: Misal G grup berorder n ditulis o(G) = n. Misalkan pula o(H) = r dan ℎଵ, ℎଶ, … , ℎ
adalah elemen-elemen yang berbeda di H,. Jika H = G, jelas pernyataan bernilai benar. Misalkan ܩ ≠ ܪ, maka terdapat ܽ ∈ ܩ, ܽ ∉ ܪ.
Daftar semua elemen-elemen sepanjang 2 baris sebagai berikut ℎଵ, ℎଶ, … , ℎ
ℎଵܽ, ℎଶܽ, … , ℎܽ
Kita klaim bahwa semua entri-entri di baris kedua adalah berbeda satu dengan yang lain dan juga berbeda dengan baris pertama. Karena jika untuk setiap dua di baris kedua adalah sama, maka diperoleh ℎܽ = ℎܽ dengan ݅≠ ݆. Dengan hukum penghapusan diperoleh ℎ = ℎ, kontradiksi.
Jika entri di baris kedua sama dengan entri-entri di baris pertama, maka ℎܽ =
ℎ sehingga diperoleh ܽ = ℎିଵℎ ∈ ܪ. Hal ini kontradiksi dengan ܽ ∉ ܪ.
Jadi, kita mempunyai 2 )ܪ(elemen. Jika elemen-elemen tersebut sebanyak G,
maka kita selesai. Jika tidak, maka terdapat ܾ ∈ ܩyang tidak terdapat dalam kedua baris. 2
Perhatikan daftar baru ℎଵ, ℎଶ, … , ℎ
ℎଵܽ, ℎଶܽ, … , ℎܽ ℎଵܾ, ℎଶܾ, … , ℎܾ
Dengan jalan yang sama, kita asumsikan dua entri di baris ketiga tidak sama dengan setiap entri yang lain, sehingga kita mempunyai 3 )ܪ(elemen.
Dengan melanjutkan langkah di atas, karena G adalah grup berhingga, maka kita
peroleh ݇ ) ܪ(elemen yang berbeda sehingga Jadi order H membagi order G.
݇ )ܩ( = ) ܪ(
(terbukti). Contoh: Misalkan { = ܩ1, −1, ݅, −݅} adalah grup terhadap operasi perkalian, = )ܩ(4 dengan subgrup { = ܪ1, −1} yang berorder 2. Untuk ݅∈ ܩdiperoleh Dengan demikian
ܪଵ = {݅, −݅}, ܪ(ଶ) = 2
4 = ܪ ∪ ܪ( = )ܩ(ଵ) = ) ܪ(+ ܪ(ଵ) = 2 + 2 = 2(2) = 4 Corrolary: Order sebarang elemen g di G membagi order G Bukti: Misal r adalah order dari g. Buat himpunan H =
g
i
|i r
dan klaim H
membentuk suatu subgrup dari G. Klaim juga o(g) = r adalah banyaknya elemen-elemen dalam subgrup siklis yang dibangkitkan oleh g. Karena ݃ = ݁, subgrup tersebut mempunyai paling banyak r elemen. Jika
banyaknya elemen kurang dari r, maka ݃ = ݃ untuk suatu bilangan bulat 0 ≤ ݅< ݆< ݎ. Oleh karena itu, ݃ି = ݁, sedangkan 0 < ݆− ݅< ݎ. Kontradiksi dengan ݃ = ݁.
Jadi subgrup siklis yang dibangkitkan oleh g mempunyai r elemen. Berdasarkan
Teorema Lagrange, )ܩ(|)݃(. (terbukti)
3
Jika C adalah kode biner (n,k) dalam ruang V n-tupel maka V adalah grup abelian terhadap + dan C adalah subgrup. Order dari V adalah 2n dan order C adalah 2k, yang membagi 2n. C mempunyai 2n-k koset. Suatu grup G disebut siklik jika G memuat sebuah elemen g dengan perpangkatannya. Elemen g disebut generator dari G. Suatu grup siklik dapat mempunyai lebih dari satu generator. Suatu elemen g di G membangkitkan subgrup siklik H dari G dengan perpangkatan dari g. Teorema 24: Jika sebuah elemen g mempunyai order r, maka gs = e jika dan hanya jika s adalah kelipatan dari r.
Bukti: () Andaikan s tidak kelipatan r, maka berdasar algoritma pembagian, s = ar + b dengan 0 < b < r. Sehingga gs = gar+b = (gr)agb = ea gb = gb = e yang kontradiksi dengan kenyataan bahwa r adalah order dari g. Jadi s kelipatan r. () Karena s adalah kelipatan r, maka gs = gra (gr)a = ea = e.
Teorema 25: Jika g adalah sebuah elemen berorder r, maka gs mempunyai order r/FPB (s,r)
Perhatikan ilustrasi berikut: Pada ଼ܼ = {0,1,2,3,4,5,6,7} membentuk grup terhadap operasi penjumlahan Misal g = 2, maka 2ସ = 0 sehingga o(2) = 4 = r
Selanjutnya misalkan s = 3, maka (2ଷ )ସ = 0 sehingga (2ଷ) = (6) = 4
Karena FPB(s,r) = FPB(3,4) = 1, diperoleh (2ଷ) = 4 = 4/1 = 4/(ܤܲܨ3,4) Misal g = 3, maka 3଼ = 0 sehingga o(3) = 8 = r
Misalkan pula s = 2, maka (3ଶ )ସ = 0 sehingga (3ଶ ) = 4
Karena FPB(s,r) = FPB(4,8) =2, maka diperoleh (3ଶ) = 4 = 8/2 = 8/(ܤܲܨ4,8) Bukti: Diketahui ݃ = ݁. Misalkan ܾ = ݃௦ pembangkit sebuah grup siklis H dari G. Akan
ditunjukkan bahwa order dari ݃௦ adalah ݎ/ݏ(ܤܲܨ, )ݎatau H mempunyai ݎ/ݏ(ܤܲܨ, )ݎ elemen.
4
Perhatikan bahwa H mempunyai beberapa elemen sebagai pangkat terkecil b yang memberikan identitas. Pandang bahwa ܾ = ݃௦ dan ܾ = ݁ jika dan hanya jika (݃௦) = ݃ ௦ = ݁ atau
jika dan hanya jika r membagi ms. Pertanyaannya adalah apa nilai terkecil m sehingga r membagi ms? Jika d adalah bilangan terbesar yang membagi r dan s, maka dalam ekspresi
݀ = ݎቀௗቁ, faktor d dari r akan membagi faktor s dari ms. Tidak ada faktor prima dari r/d yang dapat dicakup oleh s dan d, karena kita telah memilih d sebagai bilangan bulat terbesar yang membagi r dan s. Jadi semua r/d harus dicakup di dalam m, sehingga bilangan terkecil m adalah ݎ ݉ = = ݎ/ݏ(ܤܲܨ, )ݎ ݀ (terbukti)
Teorema 26: Jika g dan h adalah elemen dari grup abelian, g mempunyai order r dan h berorder s dan FPB (r,s) = 1, maka gh berorder rs.
Bukti: Misalkan G subgrup yang dibangkitkan (generated) oleh g dan H adalah subgrup yang dibangkitkan oleh h. Karena ݎ = )ܩ(dan ݏ = ) ܪ(serta (r,s) = 1, maka = ܪ ∩ ܩ
(݁). Berdasarkan teorema Lagrange, ݎ|) ܪ ∩ ܩ(dan ݏ|) ܪ ∩ ܩ(. Misal (݃ℎ) = ݁, ݅>
0. Karena gh = hg, maka ݁ = (݃ℎ) = ݃ℎ, sehingga ݃ = ℎି ∈ )݁( = ܪ ∩ ܩ. Jadi ݃ = ݁, dimana ݅|ݎdan ℎ = ݁, dimana s|݅. Karena (r,s)=1 dan r dan s keduanya membagi
i, maka rs membagi i. Jadi ݅≥ ݏݎ. Karena (݃ℎ)௦ = ݃௦ℎ௦ = ݁, kita lihat bahwa rs
adalah bilangan bulat positif terkecil i, sedemikian sehingga (݃ℎ) = ݁. Ini berarti rs adalah order dari gh. (terbukti)
Misal kita mempunyai field berhingga F, maka F mempunyai elemen identitas perkalian yaitu 1. Menurut penjumlahan, grup siklik dibangkitkan oleh 1. Karena elemenelemen dari F membentuk suatu grup terhadap operasi +, ini adalah subgrup dari F dan 1 mempunyai suatu order finit n. Ini adalah bilangan terkecil yaitu :
1 1 .......... 1 0 n kali
5
Jelaslah n harus bilangan prima p, karena jika n = ab = 0, maka a atau b adalah 0. Seperti yang kita tahu dalam field biner 1+1 = 0 dalam field 3 elemen 1+1+1 = 0. Misal GF(p) menyatakan himpunan bilangan bulat modulo p. GF(p) terdiri dari bilangan 0,1,2,....... p 1 dengan operasi biasa pada modulo p. Contoh, jika p = 7, GF(7) =
0,1,2,3,4,5,6 dan 3.4 = 12
5 (modulo7).
Teorema 27: Jika p bilangan prima, maka bilangan bulat modulo p, GF(p) merupakan suatu field. Setiap field berhingga F memuat suatu subfield yaitu GF(p), untuk suatu bilangan prima p dan p. = 0,untuk setiap di F
Bukti: Sebagaimana yang kita ketahui, Untuk setiap field berhingga F, memuat bilangan bulat modulo p untuk suatu p. Kita hanya akan menunjukkan bahwa elemen-elemen tersebut merupakan field. Jelasnya, elemen-elemen di GF(p) membentuk grup abel terhadap operasi (+). Untuk melihat bahwa himpunan tersebut membentuk grup abelian dibawah operasi perkalian (.), kita hanya perlu menunjukkan bahwa setiap elemen tak nol di GF(p) memiliki invers perkalian.. Karena p prima, untuk a < p, FPB(a,p) = 1. Jika FPB(a,p) = 1, maka terdapat b dan c sedemikian hingga ab + pc = 1, yang berarti ab (mod p). dan terdapat bilangan bulat b’ antara 1 dan p – 1 sedemikian hingga b’ p) dan ab’
1
b (mod
1 (mod p). Dengan demikian b’ adalah invers a. Jadi terbukti bahwa setiap
elemen tak nol mempunyai invers. Perhatikan bahwa p. = (p.1) = 0. = 0 . (terbukti).
Jika F memuat field prima GF(p), maka p disebut karakteristik dari F.
Teorema 28: Pada field F berkarakteristik p.
x y p
x p y p , untuk sebarang x dan y di F.
Bukti: Perluasan x y p berdasarkan teorema binomial adalah: p p ( x y) p x p x p 1 y x p 2 y 2 ...... y p . 1 2
6
p
Setiap suku, kecuali yang pertama dan terakhir, dikalikan dengan koefisien binomial , i untuk 1 ≤ i ≤ − 1. Jika dijabarkan,
(− 1)( − 2) ⋯ ( − ݅+ 1) ቀ ቁ= ݅ ݅(݅− 1)(݅− 2) ⋯ 3 ∙ 2 ∙ 1
sehingga masing masing suku mempunyai koefisien p. Karena p adalah karakterisik F, maka semua suku (kecuali pertama dan terakhir) adalah 0. Untuk ( x y) p kita ganti y dengan –y pada perluasannya. Sehingga didapat x y p x p y p (terbukti) Contoh: Dalam Ζଷ berlaku, ( ݔ+ 1)ଷ = ݔଷ + 3ݔଶ + 3 ݔ+ 1 = ݔଷ + 1ଷ Corrolary : x y p x p y p m
m
m
Bukti: Misal pm = t. dengan menggunakan teorema 28, didapat :
x y p
m
x y t x t y t x p y p m
m
(terbukti)
Order dari field berhingga adalah banyaknya elemen didalamnya. Setiap field berhingga F dinyatakan dengan GF(n) dengan n adalah order dari F. Huruf GF mengacu pada Field Galois yaitu nama grup yang ditemukan oleh Evarisk Galois (1811 – 1832), yang meninggal pada umur 20 tahun. Kita sering melihat field Galois GF(16) dengan 16 elemen, yang mempunyai karakteristik 2. Seperti yang kita lihat, setiap field berhingga mempunyai pr elemen untuk beberapa bilangan prima p dan kita dapat secara tepat menyebutnya GF(pr) karena ada hanya satu field dengan pr elemen.
4.2 Struktur Field Berhingga Jika F adalah field, F[x] adalah himpunan semua polinomial dalam x dengan koefisien dalam F dengan penjumlahan, pembagian dan perkalian polinomial secara biasa. Jelas bahwa F[x] adalah ring. Untuk suatu polinomial monik f(x) dengan derajat tidak nol (catatan:݂(]ݔ[݂ ∈ )ݔ
disebut polinomial monik jika koefisien tak nol dari pangkat tertinggi x adalah 1) , kita 7
misalkan F[x]/f(x) adalah himpunan kelas-kelas kongruen polinomial dalam F[x] modulo f(x). Ini disebut ring polinomial modulo f(x). Pada ring ini adalah ring yang memuat semua polinomial berderajat lebih kecil dari derajat f(x) dengan penjumlahan, pembagian dan perkalian polinomial modulo f(x). Definisi: Polinomial ݂( ]ݔ[ܨ ∈ )ݔdisebut taktereduksi (irreducible) jika f(x)
berderajat positif dan f(x) tidak dapat dinyatakan sebagai perkalian antara dua polinomial berderajat positif. Dengan kata lain, jika f(x) = g(x)h(x), maka g(x) konstan atau h(x) konstan. Contoh: ݂(ݔ = )ݔଶ + 1 merupakan polinomial tak tereduksi di R[x], akan tetapi
tereduksi di C[x], karena f(x) dapat dinyatakan sebagai perkalian ൫ ݔ+ √−1൯( ݔ− √−1). Teorema 29: F[x]/f(x) adalah field jika dan hanya jika f(x) tak tereduksi.
Misal f(x) adalah polinomial tak tereduksi berderjat m atas GF(p), maka F’ = GF(p)[x]/f(x) adalah field dengan pm elemen. Kita juga dapat menyatakan F’ sebagai himpunan polinomial dalam dengan operasi yang biasa, untuk adalah akar dari f(x). Bukti: () Andaikan f(x) adalah polinomial tereduksi, maka f(x) dapat dinyatakan sebagai ݂( ∙ )ݔ(݃ = )ݔℎ( )ݔdengan 1 ≤ deg(݃) , deg(ℎ) < deg (݂). Karena masing-masing derajat ݃ dan h merepresentasikan masing-masing kelas di ]ݔ[ܨ/݂()ݔ, maka kita mempunyai ݃ ∙ ℎ = ݂ ≡ 0 ݉ ݂ ݀, dengan demikian ݃ ∙ ℎ = 0 di ]ݔ[ܨ/݂()ݔ. Hal ini kontradiksi dengan ]ݔ[ܨ/݂( )ݔsebagai field yang tidak mempunyai pembagi nol.
() Kita klaim ]ݔ[ܨ/݂( )ݔsebagai ring komutatif dengen elemen identitas, akan
ditunjukkan setiap elemen tak nolnya mempunyai invers. Ambil [݃(]ݔ[ܨ ∈ ])ݔ/݂()ݔ
dengan [݃( ≠ )ݔ0]. Karena [1] merupakan elemen identitas terhadap operasi perkalian, akan ditunjukkan terdapat [ℎ(]ݔ[ܨ ∈ ])ݔ/݂( )ݔsedemikian hingga [݃(])ݔ. [ℎ([ = ])ݔ1] atau ݃( ∙ )ݔℎ( ≡ )ݔ1(݉ ))ݔ(݂ ݀. Karena ݂( )ݔmerupakan polinomial tak tereduksi dan ݂( )ݔtidak membagi ݃()ݔ, maka )ݔ(݃(ܤܲܨ, ݂( = ))ݔ1. Akibatnya terdapat polinomial
)ݔ(ݏdan )ݔ(ݐsehingga )ݔ(݃ ∙ )ݔ(ݏ+ = )ݔ(݂ ∙ )ݔ(ݐ1 atau ≡ )ݔ(݃ ∙ )ݔ(ݏ1(݉ ))ݔ(݂ ݀. Lebih lanjut diperoleh [[ = ])ݔ(݃[ ∙ ])ݔ(ݏ1], sehingga [݃(ି])ݔଵ = [])ݔ(ݏ. (terbukti)
8
Contoh 1: Misalkan diketahui polinomial tak tereduksi ݂(ݔ = )ݔଶ + ݔ+ 1 atas field ܼଶ.
Elemen-elemen dalam ܼଶ[]ݔ/݂({ = )ݔ0, 1, ݔ, ݔ+ 1}, yaitu himpunan dalam ܼଶ[ ]ݔyang berderajad kurang dari dua. Operasi penjumlahan sama dengan operasi penjumlahan
polinomial biasa pada ܼଶ[]ݔ. Sebagai contoh: [ ݔ+ 1] + [[ = ]ݔ2 ݔ+ 1] = [1]. Sedangkan untuk operasi perkaliannya sama dengan operasi perkalian polinomial biasa pada ܼଶ[]ݔ
kemudian mereduksikan hasilnya dengan menghitung sisanya setelah dibagi dengan ݂()ݔ. Untuk mereduksinya dapat dikerjakan menggunakan pembagian biasa atau menggunakan
hubungan ݔଶ ≡ ݔ+ 1 yang digunakan untuk mereduksi hasil perkalian yang berderajad 2. Sebagai
contoh:
[ ݔ+ 1][ ݔ+ 1] = [ݔଶ + 2 ݔ+ 1] = [( ݔ+ 1) + 1] = []ݔ.
Tabel
penjumlahan dan perkalian dapat disajikan sebagai berikut: +
0
1
x
x+1
0
0
1
x
x +1
1
1
0
x +1
x
x
x
x +1
0
1
x +1
x+1
x
1
0
.
0
1
x
x+1
0
0
0
0
0
1
0
1
x
x+1
x
0
x
x+1
1
x +1
0
x+1
1
x
Contoh 2: Misalkan polinomial tereduksi ݂(ݔ = )ݔଶ + 1 atas field ܼଶ. Elemen-elemen dalam ܼଶ[]ݔ/݂({ = )ݔ0, 1, ݔ, ݔ+ 1}. Tabel operasi penjumlahan +
0
1
x
x+1
0
0
1
x
x +1
1
1
0
x +1
x
x
x
x +1
0
1
x +1
x+1
x
1
0
9
Untuk membuat tabel operasi perkalian dalam ܼଶ[]ݔ/݂()ݔ, dengan memperhatikan kenyataan ݔଶ ≡ 1 sehingga diperoleh tabel sebagai berikut: .
0
1
x
x+1
0
0
0
0
0
1
0
1
x
x+1
x
0
x
1
x+1
x +1
0
x+1
x+1
0
Karena (x + 1)(x + 10 = 0, maka himpunan tersebut bukan field tetapi hanya ring komutatif dengan unsur satuan.
Teorema 29 sangat berguna untuk mengkonstruksi field berhingga F. Kita katakan bahwa adalah elemen-elemen primitif dari F jika untuk setiap elemen tak nol dalam F adalah pangkat dari . Order dari suatu elemen field berhingga adalah order multiplikatifnya. Sebuah elemen primitif dalam field dengan q elemen mempunyai order q1. Ini tidak selalu menjadi kasus bahwa akar dari suatu polinomial yang tidak tereduksi adalah elemen primitif. Suatu polinomial yang tak tereduksi mempunyai elemen primitif, sebagai sebuah akar yang disebut polinomial primitif. Suatu polinomial primitif atas GF(p) diperoleh dari derajat m, tabel untuk F dapat disusun sebagaimana GF(16). Sayangnya untuk menyatakan apakah untuk setiap diberikan polinomial tidak tereduksi adalah primitif tidaklah mudah. Untuk keperluan tersebut, diberikan teorema sebagai berikut:
Teorema 30: Setiap field berhingga memiliki sebuah elemen primitif. Bukti: Misal F memiliki q elemen dan misal adalah elemen di F dengan order paling besar, yang dinyatakan dengan r. Maka r q 1 , sebab pangkat , 2, 3,……..,
r
harus berbeda dan tidak nol. Misal adalah suatu elemen lain di F yang berorder s. Kita tunjukkan s harus membagi r. Misal r bilangan prima r dan s. Misal a
p
ai i
p
ai i
dan s
p
bi i
adalah dekomposisi pangkat
jika ai bi dan misalkan b
p
bi i
jika bi ai .
Maka FPB (r/a, s/b) = 1 dan rs/ab = KPK (r,s). Berdasarkan teorema 25, a mempunyai order r/a dan b mempunyai order s/b. Sehingga berdasarkan teorema 26, a b 10
mempunyai order rs/ab = KPK (r,s) dan r . Tetapi dengan pemilihan ini harus sama dengan r sehingga s membagi r. Oleh karena itu setiap elemen adalah akar dari persamaan xr – 1 = 0. Seperti polinomial ini mempunyai paling banyak r akar berbeda. Menurut teorema 22, r = q-1. (terbukti) Corollary: Setiap elemen di field F berorder q memenuhi persamaan xq = x. q-1
elemen tak nol di F memenuhi persamaan x
Setiap
= 1.
Bukti: Ambil sebarang ܨ ∈ ݔ. Jelas bahwa ݔ = ݔdipenuhi oleh x = 0. Selanjutnya
elemen tak nol membentuk suatu grup yang berorder q-1 di bawah operasi perkalian.
Dengan menggunakan fakta bahwa = |ீ|ݔ1ீ untuk sebarang elemen ݔdari grup
berhingga G, kita peroleh untuk semua 0 ≠ ܨ ∈ ݔmemenuhi ݔିଵ = 1 yang berarti ݔ = ݔ.
(terbukti)
Teorema 30 menyatakan bahwa grup multiplikatif dari suatu field berhingga adalah siklik. Corrolary berikut untuk bilangan bulat sangat berguna berikutnya.
Corrolary: Setiap bilangan bulat x sedemikian hingga FPB (x, p) = 1, memenuhi persamaan xp-1
1 (mod p).
Bukti: FPB (x, p) = 1 berarti terdapat bilangan bulat m, n sedemikian sehingga ݉ݔ+
= ݊1, lebih lanjut diperoleh ≡ ݉ݔ1 (݉ ) ݀, yaitu ݉ݔ|− 1. Berdasarkan teorema
sebelumnya, untuk setiap elemen tak nol memenuhi xp-1 = 1, maka diperoleh ݉ݔ+ = ݊ ݔିଵ, sehingga ݔ ≡ ݉ݔିଵ (݉ ) ݀, atau ݉ݔ|− ݔିଵ.
Karena ݉ݔ|− 1 dan ݉ݔ|− ݔିଵ, maka ݉ݔ|− 1 − ݉ݔ+ ݔିଵ dengan
demikian ݔ|ିଵ − 1 yang berarti xp-1
1 (mod p).
(terbukti)
11
Teorema 31: Setiap field berhingga F memiliki pm elemen untuk suatu bilangan prima p. Bukti: Setiap F memuat subfield prima yaitu GF(p). Elemen-elemen di F membentuk ruang vektor atas GF(p). Karena F field berhingga, maka dimensi F berhingga. Misalkan dimensi F adalah m, maka terdapat m vektor yang bebas linear dan membangun F. Misalkan {ݔଵ, ݔଶ, … , ݔ } basis dari F, akibatnya setiap anggota dari F dapat disajikan secara tunggal sebagai kombinasi linear dari vektor-vektor basis yaitu ߙ{ = ܨଵݔଵ + ߙଶݔଶ + ⋯ + ߙ ݔ : ߙ ∈ })(ܨܩ
Jadi banyaknya elemen dari F adalah (terbukti).
Sebuah field berhingga F disebut isomorfik ke field berhingga F’ jika order dari F sama dengan order dari F’, dan ada suatu pemetaan dari F ke F’ sedemikian sehingga : 1. mengawetkan penjumlahan, ( ) ( ) ( ) 2. mengawetkan perkalian, ( . ) ( ). ( ) 3. onto yaitu untuk sebarang di F’ sama dengan ( ) untuk suatu dalam F. Karena field kita adalah berhingga, maka onto jika dan hanya jika satu-satu, yaitu
( ) 0 mengakibatkan = 0. Selanjutnya disebut isomorphisme. Suatu isomorphisme mempunyai arti yang sama untuk pelabelan ulang dari lemen-elemen dari field yang mengawetkan + dan •. Ini berimplikasi bahwa (0) 0 dan (1) 1 .Suatu isomorfisme yang membawa suatu field F onto dirinya sendiri disebut automorfisme. Teorema 32: Jika F field berhingga dengan karakteristik p, maka pemetaan yang didefinisikan oleh ( ) p adalah suatu automorfisme dari F. Bukti: Misalkan automorfisme.
߮: ܨ → ܨdengan ߮(ߙ) = ߙ , ∀ߙ ∈ ܨ. Akan ditunjukkan
Jelas order dari domain dan kodomain sama. Ambil ߙ, ߚ ∈ ܨdengan ߮(ߙ) = ߙ dan ߮(ߚ) = ߚ, akan ditunjukkan ߮ mengawetkan penjumlahan, perkalian dan memenuhi pemetaan onto dan satu-satu.
12
߮(ߙ + ߚ) = (ߙ + ߚ). Dengan memperhatikan teorema 28, diperoleh ߮(ߙ + ߚ) = (ߙ + ߚ) = ߙ + ߚ = ߮(ߙ) + ߮(ߚ), sehingga ߮ mengawetkan penjumlahan ߮(ߙߚ) = (ߙߚ) = ߙ ߚ = ߮(ߙ)߮(ߚ). dengan demikian perkalian
߮
mengawetkan
Untuk menunjukkan ߮ onto dan satu-satu, cukup ditunjukkan jika ߮(ߙ) = 0 maka ߙ = 0.
Karena ߮(ߙ) = 0, maka ߙ = 0, dengan kata lain ߙ ∙ ߙିଵ = 0. Karena ߙିଵ ≠ 0, maka ߙ = 0.
Jadi adalah automorfisme
13
Daftar Pustaka Pless, Vera. 1989. Introduction to the theory of error-correcting codes. 2nd ed. Canada: John Wiley & Sons. Inc. Fraleigh, John B. 1982. A First Course In Abstract Algebra, Third Edition.Philippines: Addison-Wesley Publishing Company, Inc. Ball, Richard W.1963. Principles of Abstract Algebra, USA: Holt, Rinehardt & Winson. Inc. Herstein, I.N, Topics In Algebra. 2nd ed. Chicago: John Wiley & Sons. Inc.
14
