UNIVERSITI PUTRA MALAYSIA

PENGANGGARAN KEKARDINALAN BAGI SET PENYELESAIAN SISTEM PERSAMAAN KONGRUEN MELALUI KAEDAH

TRANSFORMASI

SHARIFAH KARTINI BINTI SAID HUSAIN

FSAS 2000 3

PENGANGGARAN KEKARDINALAN BAGI SET PENYELESAIAN SISTEM PERSAMAAN KONGRUEN MELALUI KAEDAH

TRANSFORMASI

SHARIFAH KARTINI BINTI SAID IillSAIN

MASTER SAINS UNIVERSm PlITRA MALAYSIA

2000

PENGANGGARAN KEKARDINALAN BAGI SET PENYELESAIAN SISTEM PERSAMAAN KONGRUEN MELALUI KAEDAH

TRANSFORMASI

Oleh

SHARIFAH KARTINI DINTI SAID IIDSAIN

Tesls Yang Dikemukakan Sebagal Memenuhl Keperluan Untuk IJazah Master Sains

di FakulU Sains dan Pengajlan Alam Sekltar Universiti Putra Malaysia

September 2000

DEDlKASI

Teristimewa buat

Ibuku, Tuan Nong binti Syed Abdullah

abang-abang, kakak-kakak

dan anak -anak saudara

dan dihadiahkan kepada

Syed Ahmad Thani bin Tuan Hadi

dan Sharifah Maisara

ii

Abstrak tesis yang dikemukakan kepada Senat Universiti Putra Malaysia sebagai memenuhi keperluan \Ultuk ijazah Master Sains.

PENGANGGARAN KEKARDINALAN BAGI SET PENYELESAIAN SISTEM PERSAMAAN KONGRUEN MELALll KAEDAH

TRANSFORMASI

Oleh

SHARIFAH KARTINI BINTI SAID HUSAIN

SEPTEMBER 2000

Pengerusi: Dr. Hj. Ismail bin AbduUah

Fakulti: Sains dan Pengajlan Alam Sekltar

Penganggaran kekardinalan bagi set penyelesaian bagi persamaan kongruen

modulo suatu kuasa perdana p yang diselrutukan dengan suatu poJinomial lruartik

berbentuk

daJam Zp[x,y] ditentukan dengan menggunakan kaedah transfonnasi

.Kaedah ini digwtakan apabila berlalru beberapa kes atau keadaan polino�

iaitu:

1. Polinomial atau sepasang polinomial tak linear.

2. Polinomial atau sepasang polinomial berdatjah tinggi, biasanya lebih

darlpada 3.

3. Wujud pertindihan tembereng pada gambarajah petunjuk bagi sepasang

polinonrlal yang diselrutukwL

ill

Kaedah ini meliputi satu algoritma yang melibatkan penurunan polinomial

daripada dua pembolehubah kepada satu pembolehubah sahaja. Seterusnya

daripada polinomial barn yang diperolehi kita kembali kepada pemaharnan

poligon Newton untuk mendapatkan pensifar sepunya bagi polinomial-polinomial

tersebut. Kemudian faktor penentu 0 bagi anggaran di atas diperolehi

Maldumat ini kemudiannya digunakan untuk memperolehi anggaran kekardinalan

di atas.

iv

Abstract of thesis presented to the Senate ofUniversiti Putra Malaysia in fulfilment of the requirement for the degree of Master of Science.

ON THE ESTIMATE CARDINALI1Y OF TIlE SET OF SOLUTIONS TO CONGRUENCE EQUATION BY TRANSFORMATION METIIOD.

By

SHARIFAH KARTINI BINTI SAID HUSAIN

SEPTEMBER 2000

Chairman: Dr. Hj. Ismail bin AbduUah

Faculty: Science and Environmental Studies

The estimation of the cardinality of the set of solutions to congruence equation

modulo a prime power p which is associated with the quartic polynomial of the

fonn

/(x,y)= ax4 + bx1y+ cxZyZ +dxyl +ey4 + mx+ �+k

in Zp[x,y] is detennined by means oftransfonnation method.

This method is utilized in certain cases or in any polynomial circumstances, that is:

1. Polynomial or a pair of non-linear polynomials.

2. Polynomial or a pair of high degree polynomials, nonnaUy exceeding 3.

3. The existence of intersection of coinciding segments in the indicator diagram

of a pair of associated polynomials.

v

This method covers an algorithm, which involves polynomial reduction from two

variables to a single variable. Consequently, from the new polynomial obtained,

we return to Newton polygon in order to set common zeros for the polynomials

stated. Then, the estimation of determinant factor 8 is obtained. This

information is later used to obtain the estimate of this cardinality.

PENGHARGAAN

Dengan nama Allah yang Maha Pemurah lagi Maha Penyayang!

Kesyukuran yang tidak tedUngga dirafakkan ke hadrat Dahi kerana

memberi peluang masa, usia dan ilmu untuk menyiapkan tesis ini.

Pertama sekali jutaan terima kasih diucapkan kepada Pengerusi

Jawatankuasa Penyeliaan iaitu Dr. Hj. Ismail bin Abdullah alas segala

kesabaran, bantuan, dorongan dan bimbingan beliau selama dua tahun

yang amat bennakna.

Ribuan terima kasih juga disampaikan kepada Timbalan Naib

Canselor (Akademik), Profesor Dr. Kamel Ariffm bin Mohd. Alan dan

kepada Dr. Mohamad Rushdan bin Md. Said kerana dorongan dan

nmjukajar yang telah mereka curahkan.

Penghargaan yang sungguh berarti buat mereka sebagai pendidik

yang sentiasa bersedia mencurahkan ilmu kepada insan-insan yang

dahagakan pengetahuan. Saya abadikan jasa baik mereka dalam ungkapan

<Ii bawah:

Dia tempat berdiri tiang negara dari keringat titisan ilmunya mencurah menjadi benih dalam diri boo.

vii

Akhir sekali saya ingin mengucapkan ribuan terima kasih kepada

keJuarga, terutama suami yang memahami, dan rakan-rakan yang tidak

jemu memberi galakan dan semangat sebingga penulisan ini dapat

disempwnakan.

viii

Saya mengesahkan bahawa Lembaga Pemeriksa telah mengadakan peperiksaan akhir pada 30 September 2000 bagi Sharifah Kartini binti Said Husain mengenai tesis Master Sains yang bertajuk "Penganggaran Ke1cardinalan Bagi Set Penyelesaian Sistem Persamaan Kongruen melalui K.aedah Transfonnasi" mengikut Akta Universiti Pertanian Malaysia (ljazah Lanjutan) 1980 dan Peraturan-Peraturan Universiti Pertanian Malaysia (Ijazah Lanjutan) 1981. Lembaga Pemeriksa memperakukan bahawa calon ini dianugerahkan ijazah tersebut. Abli-ahli Lembaga Pemeriksa ca10n adalah seperti berikut:

IU. HARUN BIN BUDIN, Ph.D, Profesor Madya, Fakulti Sains dan Pengajian Alam Sekitar, Universiti Putta Malaysia. (Pengerusi)

HJ. ISMAIL BIN ABDlJ:aAH, Ph.D, Pensyarah, Fakulti Sains Komputer dan Teknologi Maklwnat, Universiti Putta Malaysia. (pemeriksa)

KAMEL ARIFF1N BIN MOlID. ATAN, Ph.D, Profesor, F akulti Sains dan Pengajian Alam Sekitar, Universiti Putra Malaysia. (Pemeriksa)

MOHAMAD RUSlIDAN BIN MD. SAID, Ph.D, Pensyarah, Fakulti Sains dan Pengajian Alam Sekitar, Universiti Putra Malaysia. (pemeriksa)

G ALI MOlIA YIDIN, Ph.D, ffimbalan Dekan Pusat Pengajian Siswazah,

Universiti Putra Malaysia.

Tarikh: 0 4 0 [C 2000

ix

Tesis ini telah diserahkan kepada Senat Universiti Putra Malaysia dan telah diterima sebagai memenuhi syarat keperluan untuk ijazah Master Sains.

. �L� KAMIS AW ANG, Ph.D, Profesor Madya, Dekan Pusat Pengajian Siswazah, Universiti Putra Malaysia.

Tarikh: 1 1 JAN ZOOl

x

PENGAKUAN

Saya dengan ini mengakui bahawa tesis ini adalah berdasarkan kerja saya yang asli kecuali petikan yang telah dinyatakan sumbemya. Saya juga mengakui bahawa ia tidak pernah dihantar kepada mana-mana institusi di UPM atau di tempat lain.

SHARIFAH BINTI SAID lIDSAIN

Tarikh: 25 Mei 2000

xi

KANDUNGAN

MUKASURAT

DEDIKASI ii iii ABSTRAK

ABSTRACT PENGHARGAAN LEMBARAN PENGESAHAN PENYATAAN KEASLIAN SENARAI JADUAL SENARAI RAJAH

v vii ix xi xiv xv xix SENARAI SIMBOL DAN SINGKATAN

BAB

I PENGENALAN 1 Tatatanda dan Takrifan 1 Latar Belakang 4 Ringkasan Keputusan 12

II POLINOMIAL, MEDAN p-ADIC DAN POLIGON NEWfON 21 PolinonUal 21

Gelanggang Polinomial 21 Pensifar Polinornial 26 Pembezalayan 30

Medan p-adic 31 Poligon Newton 37

III POLllIEDRON NEWfON, GAMBARAJAH PETUNJUK DAN PERSILANGAN GAMBARAJAH PETUNJUK 45 Polihedron Newton 45

Nonnal kepada Poliliedron Newton 55 Uqjuran Polihedron Newton 57

Gambarajah Petunjuk 59 Persilangan Gambarajah Petunjuk 66 Jenis Persilangan Gambarajah Pettmjuk 67

Persilangan Mudah 67

xii

IV

V

Persilangan Pada Bucu 70 Persilangan Tembereng Selati 73 PersiJangan Sepenuh 76

PERINGKAT p-ADIC BAGI PENSIFAR SEPUNYA 79 Pensifar Sepunya 79 Peringkat p-adic bagi Pensifar Suatu Polinomial 81 Pensifar Sepunya dan Persilangan Gambarajah Petunjuk 84

mANSFORMASI 94 Pengenalan 94 Transfonnasi 96

I.angkah-langkah Transformasi 1 13

VI PENYELESAIAN SISTEM PERSAMAAN

KONGRUEN 147 Hasil Tambah Eksponen 147 Penganggaran bagi NVx,f"pa) 151 Penganggaran bagi Hasil Tambah Eksponen Berganda 155

VII KESIMPULAN DAN CADANGAN 161 Penemuan Utama 161 Kesimpulan 164 Cadangan 165

BmLIOGRAFI 167

LAMPIRAN 170

VITA 206

xiii

Jadual

1.

SENARAI JADUAL

Jumlah permukaan tertinggi yang terbentuk daripada sesuatu polinomial.

XlV

MukaSurat

51

SENARAI RAJAH

Rajah Mub Surat

1. Poligon Newton bagi

f(x)= 2X2 - 7x- 30 dengan p == 2. 39

2. Poligon Newton bagi

f{x) = 2x3 - x2 - X - 36 dengan p == 2. 40

3. Poligon Newton bagi

f{x) = X4 - 4/3r - 26/3x2 + 12x - 9 dengan p == 3. 40

4. Gambarajah Newton bagi

f{x,y)= 2x2 + 3.l)' - yZ + 8 dengan P == 2. 46

5. Gambarajah Newton bagi

f{x,y) = 9x2 + 2.l)' + 9.l)'2 + 27 deogan p == 3. 46

6. Gatnbarajah Newton bagi f{x,y)= lOOx3 + 45x2y + 20.l)'2 + 75y3 + 125 dengan p == 5. 47

7. Polihedron Newton bagi f(x,y) = 12+5x+7.l)' dengan p==3. 48

8. Polihedron Newton bagi f(x,y)= 4x2 + 4.l)'2 + y2 - 9 dengan p = 3. 49

9. Polihedron Newton bagi.

f(x,y) = 9x2 +.l)' + 3y2 + 27 dengan p = 3. 49

10. Polihedron Newton bagi

/(x,y) = l00x3 + 45x2y + 20.l)'2 + 75yl + 125 dengan p == 5. SO

11. Polihedron Newton bagi

f(x, y) = 2X2 + 6.l)' + 12y2 + 6 dengan P = 2. 50

12. Unjuran Lf yang bersekutu dengan Nf bagi

f(x,y)= 12+ 5x + 7.l)' dengan p = 2 58

xv

13. UJ\juran Lf yang bersekutu dengan Nf bagi

/(x, y ) =:: 4x2 + 4xi'-+ y2 - 9 dengan p = 3. 58

14. Unjuran Lf yang bersekutu dengan N f bagi

/(x,y)= l00x3 + 45x2y+ 2009'2 + 75yl +125 dengan p = 5. 59

15. Gambarajah petunjuk yan) bersekutu dengan polinomial /(x,y = 12+ Sx+ 7xy dengan p = 3. 62

16. Gambarajah petunjuk yang bersekutu dengan polinomial /(x,y) = 4x2 + 4xy2 + y2 - 9 dengan p = 3. 62

17. Gambarajab petlu\juk yang bersekutu dengan polinomial /(x,y) = 9x2 + xy + 3y2 + 27 dengan p=3. 63

18. Gambarajah petunjuk yang bersekutu dengan polinomial /(x,y)= l00x1 + 45x2y+ 20xy2 + 75y3 + 125 dengan p = 5. 63

19. Gambarajah petunjuk yang bersekutu dengan polinomial /(x,y) = 2x2 + 6xy+ 12y2 + 6 dengan p= 2 64

20. Gambarajah petunjuk bagi /(x,y)= 4x +3y +l dan g(x,y)= x+14y+6 dengan p =3. 68

21. Gambarajah petunjuk bagi /(x,y) = 3x2 + 4xy + 5 dan

g(x,y)= 2x2 +3y2 +3 dengan P = 3. 69

22. Gambarajah petmjuk bagi /(x,y)= 3x+ 2y+ 5 dan g(x, y) = 409' + 2 dengan p = 2. 71

xvi

23. Gambarajah petUl\iuk bagi f(x.y)= 3x+2y+5 dan g(x,y)= x+ 4xy+ 2 dengan p = 2. 72

24. Gambarajah petunjuk bagi f(x,y) = 15x2 + 4xy+ 3 dan

g(x,y) = 2X2 + 3y2 + 4 dengan p = 5. 72

25. Gambarajah petunjuk bagi f(x,y)= 3x+ y+ 15 dan g(x,y) = 2x+ 3y+ 1 dengan p = 3. 73

26. Gambarajah petunjuk bagi f(x,y)= 3x+9y2 - l dan

g(x,y)= x+9y+ 3 dengan p = 3. 14

21. Gambarajah petunjuk bagi f(x,y)= 4x2+ y+8 dan

g(x,y) = 4x2 + 3y - 2 dengan p = 2. 75

28. Gambarajah petunjuk bagi f(x,y)= 20x3 +9x2y+ 4xy2 + 15y3 + 25 dan g(x,y)= 3x3 + 4x2y + 45xy2 + 4y3 + 50 dengan p= 5. 16

29. Gambarajah petunjuk bagi f(x,y)= 12+5x+1xy dan

g(x,y) = 9 + 2x2 + 5x2y2 dengan p = 3. 77

30. Gambarajah petunjuk bagi f(x,y)= 3x+ 2y+ 5 dan g(x,y)= 3x+ 5y+l dengan p = 3. 78

31. Gambarajah petunjuk bagi f(x,y)= 1+ 2x+ 5y dan g(x,y) = 2+ 5x+ 3y dengan p = 5. 85

32. Gambarajah petunjuk bagi f(x,y)= 3x+ y-15 dan g(x,y) = x+ y-9 dengan p =3. 86

xvii

33. Gambarajah petunjuk bagi /(x,y)= 5x+ 5y- 4 dan

g(x,y)= 3x+ 3y-8 dengan p = 3. 88

34. Gambarajah petwljuk bagi f(x,y)=7x+ 49y z-6 dan g(x,y)= 5x + 7y+ 6 dengan p = 7. 91

35. Gambarajah petwljuk bagi /(x,y)=x+ 2y+ 2 dan g(x,y)=2x+ 4y + 3 dengan p= 2. 92

36. Gambarajah petunjuk bagi /(x,y)= 2+ 4x+ 6y dan

g(x,y)=5+2x+ 3y dengan p = 3. 93

37. Perubahan gambarajah petunjuk bagi g dan h. 98

38. Gambarajah petunjuk bagi F(U,V) dan a(u,v). 104

39. Gambarajah petunjuk bagi F(U,V) dan a(u,v) . 112

40. Gambarajah petunjuk bagi F(U, V) = 3U1 + 2uoU + Fo dan G{u ,v) = 3V1 + 2voV + Go denganp = 2. 117

41. Polihedron Newton bagi /(x,y)= 12xz + 4xy + yZ + 27 dengan p = 3. 120

42. Polihedron Newton bagi g(x,y) == 2xz + 2xy + 9 dengan p = 3. 120

43. Gambarajah petunjuk bagi /(x,y)= 12xz + 4xy + yZ + 27 dan

g(x,y) = 2xz + 2xy + 9 dengan p = 3. 121

44. Gambarajah petunjuk bagi F(U,V)=Ul+ 2�U+ Fo dan

G{U, V) == Vl + 2voV + Go dengan p = 3. 126

xviii

p

a

[a]

(a,b)

x

SENARAI SIMBOL DAN SINGKATAN

Nombor Perdana

Eksponen Nombor Perdana

Gelanggang futeger

Medan Nombor Nisbah

Medan Nombor Nyata

Medan Nombor Kompleks

Gelanggang Integer p-adic

Medan Nombor Nisbah p-adic

Tutupan Aljabar bagi Qp

Pelengkap bagi Qp

Integer Telbesar yang lebih kecil atau sarna dengan a

Pembahagi SepWlya Terbesar bagi a dan b

n-Rangkap Pembolebubah (�, ... ,xn)

Gelanggang atau Medan

Gelanggang Polinomial dengan Pekali dalam F

m-Rangkap Polinomial (It, . .. , 11ft)' m > 1

DaJjab bagi Polinomial I

Matriks Jacobian bagi I

Kuasa Tertinggi bagi p yang membabagi a

xix

VI Kecerunan bagi f

D Pembezalayan

D([) Pembezalayan bagi f

Nf Polihedron Newton bagif

V Bucupada Nf

E Sisi pada Nf

Lf Unjuran sisi bagi Nf

11 Pembezalayan

maks Maksimum

mm Minimum

mod Modulo

eksp Eksponen

lip Penilaian terhadap p

L Hasil Tambah

IT HasilDarab

S{f;q) Hasil Tambah Eksponen

V([;pa) Set { � mod pa : f == Qmod pa }

N([;pa) Kekardinalan bagi V([;pa )

xx

BABI

PENDAHULUAN

Tatatanda dan Takrifan

Lazirnnya, kita tandakan Z sebagai gelanggang integer, Q sebagai medan

nombor nisbah, m.anakala R dan C masing-masing sebagai medan nombor nyata

dan medan nombor kompleks. Dengan p sentiasa menandakan nombor perdana,

Qp pula mewakili medan nombor p-adic dan Z p gelanggang integer p-adic

sementara Op ialah suatu perluasan medan aljabar bagi Qp.

Huruf kecil Roman mewakili Wlsur-Wlsur dalam Z atau Z p ' Huruf Greek

a adalah sentiasa eksponen bagi suatu nombor perdana p. Simbol [ ]

menandakan fungsi integer terbesar. flk.a aE R, maka [a] alcan bennakna

integer terbesar yang lebih kecil atau sarna dengan a. Tatatanda (a,b)

menandakan pembahagi sepunya terbesar bagi a dan b, kecuali pada masa-masa

tertentu yang penggunaannya jelas merujuk kepada pasangan tertib.

Tatatanda � menyatakan n-rangkap pembolehubah (Xi, ... ,XJ , dengan

n � 1 dan F mewakili gelanggang atau medan, F�] bennakna gelanggang

2

polinomial dengan pekaJi dalam F. Datam penyeJidikan ini F akan merujuk sarna

ada kepada Z atau Qp atau peluasan medan bagi Qp'

Andaikan f = L O'i .. • Oi.X.it ••• x: suatu polinomial dalamF�]. Darjah

bagi / ditakrifkan sebagai

cbjb /= ��(�+ ... + i,.). It 000'"

Simbol f bennakna m-rangkap polinomial (It, . . . ,/",), dengan m � 1 di

dalam Fl!l dan J £ iaIah matriks Jacobian [� J. 1,,; i ,,; m, 1 ,,; j ,,; n bagi

poJinomial /. Aodaikan f:::: (I., . .. /.) ialah m-rangkap polinomial linear di

lou J, dengan julat yang sarna bagi i dan j sebagai matriks yang mewakili

polinomial f.

Misalkan p sebarang nombor perdana. Bagi sebarang nombor integer talc

8ifar a, ordp ° menyatakan Jruasa tertinggi bagi p yang membahagi a, iaitu a

yang terbesar sedemikian hingga a:; o{mod p a ).

Ttka x = alb ialah sebarang nombor nisbah, maka ordp x ditakrltkan

sebagai ordp x = ordp a - ordp b (Suatu sifat Logaritma).

3

Kita mentakrif'kan suatu pemetaan yang ditandakan dengan lip pads Q

sebagai berikut :

I x I == p o jikax=O

Boleh diperlihatkan bahawa pemetaan lip seperti yang ditakrifkan di atas adalah

penilaian tak-arkhimedes pada Q (KobHtz 1977).

Suatu jujukan �} yang terdiri dari nombor nisbah disebut sebagai

jujukan Cauchy jika untuk suatu nombor � > 0, terdapat suatu N sedemildan

hingga I al - a; Ip < � untuk i, i > N. Dua jujukan Cauchy {al} dan {bl}

dikatakan setara jika

had I QI - blip == O. I�'"

Kita takrifkan medan Qp sebagai set kelas kesetaraan jujukan Cauchy

daIam Q, iaitu Qp ialah pelengkap bagi Q terlladap peni1aian lip . Kita tandakan

dengan Qp sebagai tutupan bagi Qp dan Op sebagai pelengkap bagi Qp terhadap

Dengan menggunakan takrifan di atas, kita dapat menyatakan takrif bagi

poligon Newton bagi suatu polinomial dengan pekali dalam medan p-adic seperti

yang diberikan oleh Koblitz pada tahun 1977 sebagai berikut :