Senin, 03 Oktober 2011

Makalah Teori Bilangan "DEFENISI DAN SIFAT KEKONGRUENAN"


KATA PENGANTAR

Segala puja dan puji syukur kami ucapkan kehadirat Tuhan YME, karena atas limpahan rahmat dan karunia-Nyalah makalah ini dapat kami selesaikan.
Ucapan terima kasih yang tak terhingga, kami ucapkan kepada  Bapak Prof. Dr. I Made Arnawa, M.Si. selaku Dosen pembina mata kuliah Teori Bilangan pada kelas A, program studi Teknologi Pendidikan, Kosentrasi Pendidikan Matematika, Program Pasca Sarjana, Universitas Negeri padang, Semester Ganjil T.A. 2010/2011. Salam dan do’a dari kami, semoga Allah SWT senantiasa membalas semua amal dan kebaikan bapak, dengan balasan kebaikan yang dilipat gandakan, Amin yaa robbal ‘alamin.
Makalah ini diajukan untuk memenuhi tugas kelompok dan sebagai bahan Presentase Diskusi pada mata kuliah Teori Bilangan, pada kelas A, program studi Teknologi Pendidikan, Kosentrasi Pendidikan Matematika Program pasca sarjana, Universitas Negeri padang Semester Ganjil T.A. 2010/2011.
Jika dalam penyusunan, pembuatan, ataupun dalam penulisan makalah ini terdapat kesalahan atau kekeliruan, maka kami dari TIM Penyusun (kelompok IX) memohon maaf yang sebesar-besarnya, untuk itu kritik dan saran yang membangun dari semua pihak sangat kami perlukan demi kesempurnaan makalah ini. 


Padang, 15 Oktober 2010
Wassalam,
TIM Penyusun

KELOMPOK IX





KATA PENGANTAR

Alhamdulillahirobbil ‘alamin, segala puja dan puji syukur kami ucapkan kehadirat Allah SWT, karena atas limpahan rahmat dan karunia-Nyalah makalah ini dapat kami selesaikan. Dan shalawat beriring salam buat junjungan alam, nabi besar Muhammad SAW, karena atas perjuangan beliaulah yang telah mengenal dan menghantarkan kepada kita akan kebenaran hakiki lewat risalah ilaihi yang dibawanya, buat kemaslahatan hidup kita di dunia dan di akhirat nantinya, amin yaa robbal ‘alamin.
Ucapan terima kasih yang tak terhingga, kami ucapkan kepada  Bapak Prof. Dr. I Made Arnawa, M.Si. selaku Dosen pembina mata kuliah Teori Bilangan pada kelas A, program studi Teknologi Pendidikan, Kosentrasi Pendidikan Matematika, Program Pasca Sarjana, Universitas Negeri padang, Semester Ganjil T.A. 2010/2011. Salam dan do’a dari kami, semoga Allah SWT senantiasa membalas semua amal dan kebaikan bapak, dengan balasan kebaikan yang dilipat gandakan, Amin yaa robbal ‘alamin.
Makalah ini diajukan untuk memenuhi tugas kelompok dan sebagai bahan Presentase Diskusi pada mata kuliah Teori Bilangan, pada kelas A, program studi Teknologi Pendidikan, Kosentrasi Pendidikan Matematika Program pasca sarjana, Universitas Negeri padang Semester Ganjil T.A. 2010/2011.
Jika dalam penyusunan, pembuatan, ataupun dalam penulisan makalah ini terdapat kesalahan atau kekeliruan, maka kami dari TIM Penyusun (kelompok IX) memohon maaf yang sebesar-besarnya, untuk itu kritik dan saran yang membangun dari semua pihak sangat kami perlukan demi kesempurnaan makalah ini. 

Padang, 15 Oktober 2010
Wassalam,
TIM Penyusun

KELOMPOK IX
DAFTAR ISI


KATA PENGANTAR......................................i
DAFTAR ISI.......................................... ii

I . PENDAHULUAN
1.1 Latar Belakang............................. 1
1.4 Tujuan Penulisan........................... 1
1.5 Manfaat Penulisan ........................... 2
II. TINJAUAN PUSTAKA
2.1 Relasi..................................... 3
2.2 Sifat-sifat relasi Biner....................3
2.3 Relasi ekuivalensi..........................4

III. PEMBAHASAN 
3.1. DEFENISI 5.1. .............................6
3.2. Teorema 5.1 .............................. 6
3.3. Teorema 5.2 .............................. 7
3.4. DEFENISI 5.2 ..............................7
3.5. Teorema 5.3 .............................. 8
3.6. DEFENISI 5.3 ..............................9
3.7. Teorema 5.4 .............................. 13
3.8. Teorema 5.5 .............................. 14
3.9. Teorema 5.6 .............................. 15
3.10. Teorema 5.7 .............................. 16
III. DAFTAR PUSTAKA ...............................18



“DEFENISI DAN SIFAT KEKONGRUENAN”


MAKALAH
MATA KULIAH TEORI BILANGAN

[Dosen pembina : Prof. Dr. I. Made Arnawa, M.Si.]




OLEH :

KELOMPOK IX – KELAS A
ANGGOTA :

DODY
KHAIRUZAL
NASRIADI







PROGRAM STUDI TEKNOLOGI PENDIDIKAN
KOSENTRASI PENDIDIKAN MATEMATIKA
PROGRAM PASCA SARJANA
UNIVERSITAS NEGERI PADANG
2010



I.      PENDAHULUAN

1.1 Latar Belakang
Pada perkuliah-perkuliahan sebelumnya, kita telah membahas tentang induksi matematik & teorema binomial, keterbagian, basis bilangan bulat, dan faktorisasi bilangan bulat, maka untuk kesempatan kali ini kami dari kelompok II akan melanjutkan pembahasan mengenai ” DEFENISI DAN SIFAT KEKONGRUENAN”
Menurut Sukirman (2005) konsep sifat-sifat keterbagian dapat dipelajari lebih mendalam lagi dengan menggunakan konsep kekongruenan. Memang kekongruenan merupakan cara lain untuk menelaah keterbagian dalam himpunan bilangan bulat.
 Demi memenuhi tugas kelompok, dan untuk kelancaran proses diskusi kelompok mata kuliah ini, maka kami dari kelompok IX menyiapkan bahan diskusi, berupa makalah yang kami persembahkan ini.

1.2 Tujuan Penulisan
1. Untuk mendeskripsikan uraian materi atau bahan diskusi kelompok pada mata Kuliah Teori Bilangan, Kelas A, program Studi Teknologi Pendidikan, Kosentrasi Pend. Matematika, PPs UNP.
2. Untuk Memenuhi Tugas selaku Kelompok IX pada mata Kuliah Teori Bilangan, Kelas A, program Studi Teknologi Pendidikan, Kosentrasi Pend. Matematika, PPs UNP.



1.3 Manfaat/Kontribusi Penulisan
1. Bagi mahasiswa pada umumnya, dan Tim penyusun (kelompok IX) pada khususnya, untuk menambah wawasan tentang konsep-konsep Teori Bilangan terutama pada materi yang akan dibahas.
2. Bagi peserta diskusi, Sebagai bahan Diskusi Kelompok pada mata Kuliah Teori Bilangan, Kelas A, program Studi Teknologi Pendidikan, Kosentrasi Pend. Matematika, PPs UNP.
3. Bagi Dosen Pengampu, kami persembahkan sebagai salah satu acuan penilaian unjuk kerja (fortofolio) dari kelompok Ix, Kelas A, program Studi Teknologi Pendidikan, Kosentrasi Pend. Matematika, PPs UNP.



















II.   TINJAUAN PUSTAKA

2.1    RELASI
Perkalian katesian dari himpunan A dan B adalah himpunan yang elemennya semua pasangan terurut yang mungkin terbentuk dari komponen pertama dari himpunan A, dan komponen kedua dari himpunan B. Dinotasikan dengan :
A X B ={(a,b)|aεA dan bεB}
Selanjutnya:
Relasi Biner antara A dan B adalah himpunan bagian dari A X B. Dinotasikan dengan :
R (AXB)

2.2    SIFAT-SIFAT RELASI BINER
1. Reflektif
untuk setiap x Є A berlaku (x,x) Є R, maka R reflektif.
Contoh :
Misalkan A = {1,2,3} dan relasi R pada A didefinisikan sebagai berikut:
R={(1,1),(1,2),(1,3),(2,2),(2,3), (3,2),(3,3)}
Apakaah A bersifat reflektif?
Penyelesaian
Karena untuk setiap x Є A berlaku (x,x) Є R, yaitu (1,1),(2,2), dan (3,3)Є R, maka R reflektif.

2. Simetris
untuk setiap x,y Є A dengan xRy berlaku yRx, maka R simetris.

Contoh  :
Misalkan A ={1,2,3,4}  dan relasi R pada A didefenisikan sebagai : R={(1,1),(1,2),(2,1),(2,2),(2,4),(4,2),(4,4)}
Apakah R bersifat simetris?
Penyelesaian :
Karena untuk setiap (a,b) Є R, berlaku (b,a) Є R, maka R bersifat simetris.

3. Transitif
untuk setiap x,y,z Є A dengan xRy dan yRz berlaku xRz, maka R bersifat transitif.
Contoh :
Misalkan A ={1,2,3,4}  dan relasi R pada A didefenisikan sebagai : R={((2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}
Apakah R bersifat simetris?
Penyelesaian :
untuk setiap x,y,z Є A dengan xRy dan yRz berlaku xRz, maka R bersifat transitif.

3.1    RELASI EKUIVALENSI
Relasi R: ekuivalensi jhj R sekaligus memiliki sifat sifat reflektif, simetris, dan transitif.
 
Contoh 1.
Misalkan A = {1,2,3,4} dan relasi R
pada A didefinisikan sebagai berikut :
R = {(1,1),(1,4),(4,1),(4,4),(2,2),(2,3), (3,2),(3,3) }
Periksa, apakah R ekuivalen atau tidak?
Penyelesaian
     Untuk memeriksa apakah R ekuivalen atau tidak, akan diperiksa 3 sifat sbb:
           1.     Sifat reflektif
Karena untuk setiap x Є A berlaku (x,x) Є R, maka R reflektif.
           2.     Sifat Simetris
Karena untuk setiap x,y Є A dengan xRy berlaku yRx, maka R simetris.
           3.     Sifat transitif
karena untuk setiap x,y,z Є A dengan xRy dan yRz berlaku xRz, maka R bersifat transitif.

Karena ketiga sifat di atas yaitu reflektif, simetris, dan transitif dipenuhi, Maka dapat disimpulkan bahwa R adalah relasi ekuivalen.

Teorema : Jika a ≡ b (mod m), maka b ≡ r (mod m), dimana  0 ≤ r < m. 


Bukti:
Jika a ≡ b (mod m),  akan ditunjukkan bahwa :
b ≡ r (mod m), dimana  0 ≤ r < m.
Karena   a ≡ b (mod m), maka  menurut teorema 5.1  ada bilangan bulat k, sehingga a = mk + b.
Karena a = mk + b, maka b = a – mk.
Karena a, m, dan k adalah bilangan bulat, maka a – mk adalah bilangan bulat.
Karena a – mk adalah bilangan bulat, dan b = a – mk, maka b adalah bilangan bulat.
Karena b bilangan bulat, maka menurut teorema 5.2 diperoleh bahwa :
          b ≡ r (mod m).         (Terbukti)!
III. PEMBAHASAN
“DEFENISI DAN SIFAT KEKONGRUENAN”

DEFENISI 5.1:
Jika m suatu bilangan bulat positif, maka a kongruen dengan b modulo m [ditulis a ≡ b(mod m)], bila m membagi (a-b).
Jika m tidak membagi (a-b) maka dikatakan bahwa a tidak kongruen dengan b modulo m [ditulis a b (mod m)].


Contoh :
25 ≡ 1 mod 4
sebab (a-b) terbagi oleh m, (25-1)= 24 terbagi oleh 4.

Contoh :
30 ≡ 2 mod 7
sebab (a-b) terbagi oleh m, (30-2)= 28 terbagi oleh 7.

Teorema 5.1.
a ≡ b (mod m)bila dan hanya bila ada bilangan bulat k sehingga a = mk + b.


Bukti:
a ≡ b (mod m)
akan ditunjukkan bahwa a = mk + b
Dari defenisi 1 diatas didapat bahwa :
a ≡ b (mod m), bila dan hanya bila m|(a-b).
Karena m|(a-b), maka m > 0
karena m|(a-b), maka ada bilangan bulat k, sehingga (a-b) = mk (lihat teorema 2.1 hal.33)*

Contoh :
Jika 25 ≡ 4 (mod 7) maka ada bilangan bulat k = 3.
yaitu 25-4 = 7k
   21 = 7.3

Jadi a ≡ b (mod m), bila dan hanya bila a-b = mk, untuk setiap bilangan bulat k.
Karena a-b = mk sama artinya dengan a = mk + b,
Atau dengan kata lain:
a ≡ b (mod m) bila dan hanya bila a = mk + b.
Contoh :
25 ≡ 4 (mod 7), sama artinya dengan 25 = 7.3 + 4, dimana k = 3

Contoh :
20 ≡ 2 (mod 9), sama artinya dengan 20 = 9.2 + 2, dimana k = 2


Teorema 5.2.
Setiap bilangan bulat kongruen modulo m dengan tepat satu diantara 0,1,2,3,...,(m-1).


Bukti :
Kita telah mempelajari bahwa jika a dan m bilangan- bilangan bulat, dan m > 0, menurut algoritma pembagian, maka a dapat dinyatakan sebagai :

a = mq + r, dengan 0 ≤ r < m

Ini berarti bahwa a-r = mq, yaitu a ≡ r (mod m).
Karena 0 ≤ r < m, maka ada m buah pilihan untuk r, yaitu : 0,1,2,3,...,(m-1).
Jadi setiap bilangan bulat akan kongruen dengan m dengan tepat satu diantara 0,1,2,3,...,(m-1).

Contoh :
27 ≡ r (mod 6), tentukan r, jika 0 ≤ r < 6.
Jawab
Karena 0 ≤ r < 6, maka pilihan untuk r tepat satu diantara 0,1,2,3,4,5,6. Yaitu 3.


DEFENISI 5.2:
Jika a ≡ r (mod m) dengan 0 ≤ r < m, maka r disebut residu terkecil dari a modulo m. Untuk kekongruenan residu terkecil ini, {0,1,2,3,...,(m-1)} disebut himpunan residu terkecil modulo m.


Contoh :
Residu terkecil dari 71 modulo 2 adalah 1, sebab sisa dari 71:2 adalah 1.

Contoh :
Residu terkecil dari 71 modulo 3 adalah 2, sebab sisa dari 71:3 adalah 2.

Contoh :
Residu terkecil dari (-53) modulo 10 adalah 7, sebab sisa dari (-53):10 adalah 7 (ingat residu terkecil dari suatu bilangan adalah bilangan bulat positif).

Contoh
Residu terkecil dari 34 modulo 5 adalah 4, sebab sisa dari 34:5 adalah 4.
Walaupun 34 ≡ 9 (mod 5), tetapi 9 bukan residu terkecil dari 34 (mod 5), sebab 9 bukan sisa dari 34:5.

Contoh :
Himpunan residu terkecil dari modulo 5 adalah {0.1,2,3,4}.
Himpunan residu terkecil dari modulo 9 adalah {0.1,2,3,...,9}.
Himpunan residu terkecil dari modulo 24 adalah {0.1,2,3,...,23}.

Kita dapat melihat relasi kekongruenan itu dengan cara yang lain, seperti teorema berikut ini:

Teorema 5.3
a ≡ b (mod m) bila dan hanya bila a dan b memiliki sisa yang sama jika dibagi m.


Bukti :
Akan dibuktikan dari dua sisi,
Pertama,
jika a ≡ b (mod m), maka akan ditunjukkan bahwa a dan b memiliki sisa yang sama jika dibagi m.

Karena a ≡ b (mod m), maka a ≡ r (mod m) dan b ≡ r (mod m), dengan r adalah residu terkecil modulo m atau 0 ≤ r < m. Selanjutnya,
a ≡ r (mod m), berarti a = mq + r, dan
b ≡ r (mod m), berarti b = mt + r, untuk suatu bilangan bulat q dan t, sehingga menurut teorema 2.2 hal. 34*
dapat disimpulkan bahwa a dan b memiliki sisa yang sama jika dibagi m. (Terbukti!)

Kedua,
jika a dan b memiliki sisa yang sama, maka akan dirunjukkan a ≡ b (mod m).

Misalkan:
a memiliki sisa r jika dibagi m, berarti a ≡ mq + r, dan
b memiliki sisa r jika dibagi m, berarti b ≡ mt + r, untuk suatu bilangan bulat q dan t,
dari kedua persamaan ini diperoleh :
(a-b) = (mq – mt) + (r-r)
(a-b) = m(q – t)
Karena q dan t adalah suatu bilangan bulat, maka (q-t) adalah suatu bilangan bulat,
menurut teorema 2.1 hal.33* berarti bahwa :
m|(a-b) atau a ≡ b (mod m). (Terbukti!)

Menurut teorema-teorema terdahulu, ungkapan-ungkapan berikut mempunyai arti yang sama, yaitu :
1. n ≡ 7(mod 8)
2. n = 7 + 8k
3. n dibagi 8 bersisa 7.


DEFENISI 5.3
Himpunan bilangan bulat {r1, r2, r3,..., rm} disebut sistim residu lengkap modulo m, bila setiap elemennya kongruen modulo m, dengan satu dan hanya satu dari 0,1,2,...,(m-1).

Contoh :
Himpunan {45,-9,12,-22,24} adalah sistim residu lengkap dari modulo 5, dapat diperiksa bahwa :
45 ≡ 0(mod 5)
-9 ≡ 1(mod 5)
12 ≡ 2(mod 5)
23 ≡ 3(mod 5)
24 ≡ 4(mod 5)

Contoh :
Himpunan {0,1,2,3,4} merupakan sistim residu lengkap modulo 5, sekaligus sebagai himpunan residu terkecil modulo 5.

Contoh :
Himpunan {4,3,2,1,0} merupakan suatu sistim residu lengkap modulo 5.

Contoh :
Himpunan {5,11,6,1,8,15} bukan merupan sistim tersidu lengkap modulo 6,sebab 5 ≡ 11 (mod 6) yang dua-duanya berada dalam himpunan tersebut.


“RELASI EKUIVALENSI”

Apakah relasi Kekongruenan Modulo suatu bilangan bulat merupakan relasi ekuivalensi atau tidak ?
Untuk menjawab pertanyaan diatas, simaklah uraian-uraian berikut!

Kekongruenan modulo suatu bilangan bulat positif adalah relasi antara bilangan-bilangan bulat. suatu relasi disebut relasi ekuivalensi jika relasi itu memiliki sifat reflektif, simetris, dan transitif.
Sekarang akan ditunjukkan bahwa relasi kekongruenan itu merupakan relasi ekuivalensi.

Perhatikan !
Jika m, a, b, dan c adalah bilangan-bilangan bulat dengan m positif, maka :

a. a ≡ a (mod m), sifat reflektif
b. Jika a ≡ b (mod m), maka b ≡ a (mod m), sifat simetris.
c. Jika a ≡ b (mod m) dan b ≡ c (mod m), maka a ≡ c (mod m), sifat transitif.
Bukti :
a. Karena a-a = 0.m, maka a ≡ a (mod m).
b. Jika a ≡ b (mod m), maka a-b = k.m, sehingga b-a = (-k).m, yang berarti bahwa b ≡ a (mod m).
c. a ≡ b (mod m), berarti a-b = p.m
b ≡ c (mod m), berarti b-c = q.m
untuk suatu bilangan bulat p dan q, jika kedua persamaan tersebut kita jumlahkan, maka diperoleh:
a-c = (p+q).m
karena p dan q adalah bilangan-bilangan bulat, maka (p + q) bilangan bulat, sehingga
a ≡ c (mod m).

Karena relasi “≡” (kekongruenan) pada himpunan bilangan bulat memenuhi ketiga sifat tersebut, yaitu reflekti, simetris, dan transitif, maka relasi “≡” (kekongruenan) pada himpunan bilangan bulat merupakan relasi ekuivalensi.
(terbukti!).

Karena relasi kekongruenan pada bilangan bulat merupakan relasi ekuivalensi, maka akibatnya himpunan bilangan bulat pada kongruen modulo m ini terpartisi menjadi himpunan-himpunan bagian yang setiap himpunan bagian disebut kelas.
Contoh :
Misalnya kita memperhatikan himpunan bilangan bulat dengan relasi kekongruenan modulo 5, maka dengan relasi ini himpunan bagian bilangan bulat terpatisi (terbagi menjadi himpunan-himpunan bagian yang saling asing, dan gabungannya sama dengan himpunan bilangan bulat) menjadi 5 kelas, yaitu :
[0] = {...,-10,-5,0,5,10,...}
[1] = {...,-9,-4,1,6,11,....}
[2] = {...,-8,-3,2,7,12,....}
[3] = {...,-7,-2,3,8,13,....}
[4] = {...,-6,-1,4,9,14,....}

Keterangan :
Pemberian nama untuk suatu kelas menggunakan nama salah satu anggota kelas tersebut, yang dibubuhi tanda “garis diatasnya”, atau dengan menggunakan tanda “kurung persegi”, seperti contoh diatas.

Relasi kekongruenan mempunyai kemiripan sifat dengan persamaan, sebab relasi kekongruenan dapat dinyatakan sebagai persamaan, yaitu a ≡ b (mod m) sama artinya dengan a = b + km, untuk suatu bilangan bulat k.
Misalnya :
1. Jika a ≡ b (mod m), maka (a + c) ≡ (b + c) (mod m), untuk setiap bilangan bulat c.
2. Jika a ≡ b (mod m), maka ac ≡ bc (mod m), untuk setiap bilangan bulat c.

Bukti :
1. Jika a ≡ b (mod m), berarti a-b = p.m, atau
a = pm + b, untuk setiap bilangan bulat p, selanjutnya,
jika masing-masing ruas ditambahkan dengan bilangan bulat c, maka diperoleh :
a + c = pm + b + c
atau,
(a + c) - (b + c)= p.m 
Yang berarti bahwa:
(a + c) ≡ (b + c) (mod m).......(Terbukti !)

Contoh :
Jika 15 ≡ 3 (mod 4), maka :
v  17 ≡ 5 (mod 4),
sebab 15 + 2 = 17, dan 3 + 2 = 5
v  21 ≡ 9 (mod 4),
sebab 15 + 6 = 21, dan 3 + 6 = 9
v  116 ≡ 104 (mod 4),
sebab 15 + 101 = 116, dan 3 + 101 = 104.
v  Dan seterusnya.

2. Jika a ≡ b (mod m), berarti a-b = p.m untuk setiap bilangan bulat p selanjutnya,
jika masing-masing ruas dikalikan dengan bilangan bulat c, maka diperoleh :
c(a - b) = c.p.m
atau,
ac – bc = cp.m
karena c dan p masing-masing adalah bilangan bulat, maka c.p juga merupakan suatu bilangan bulat, sehingga diperoleh bahwa :
ac ≡ bc (mod m)....(Terbukti !)

contoh :
Jika 10 ≡ 2 (mod 4), Maka :
v  50 ≡ 10 (mod 4),
Sebab 10.5 = 50, dan 2.5 = 10
v  120 ≡ 24 (mod 4),
Sebab 10.12 =120, dam 2.12 = 24
v  Dan seterusnya.


Teorema 5.4:
Jika a ≡ b (mod m), dan c ≡ d (mod m), maka ( a + c) ≡ (b + d) (mod m).


Bukti :
Jika a ≡ b (mod m), dan c ≡ d (mod m), akan dibuktikan bahwa ( a + c) ≡ (b + d) (mod m).
Kareana a ≡ b (mod m), berarti a = s.m + b, untuk suatu bilangan bulat s.
Karena c ≡ d (mod m), berarti c = t.m + d, untuk suatu bilangan bulat s.
Jika kedua persamaan tersebut dijumlahkan, maka diperoleh bahwa :
(a + c) = (sm + tm) + (b + d)
(a + c) = m(s + t) + (b + d)
(a + c) - (b + d) = m.(s + t)
Hal ini berarti bahwa :
a + c) ≡ (b + d) (mod m)
(Terbukti!)

Contoh :
Jika 20 ≡ 2 (mod 6), dan 25 ≡ 1 (mod 6), maka 45 ≡ 3 (mod 6), sebab 20 + 25 = 45, dan 2 + 1 = 3.





Teorema 5.5
Jika a ≡ b (mod m), dan c ≡ d (mod m), maka ax + cy ≡ bx + dy (mod m), untuk setiap bilangan bulat x dan y.


Bukti :
a ≡ b (mod m), berarti a = m.s + b,untuk suatu bilangan bulat s.
c ≡ d (mod m), berarti c = m.t + d, untuk suatu bilagan bulat t.
Jika kedua ruas persamaan pertama dikalikan dengan x, dan kedua ruas persamaan kedua dikalikan dengan y, maka diperoleh :
ax = msx + bx
cy = mty + dy

Dengan menjumlahkan kedua persamaan ini, maka diperoleh bahwa :
ax + cy = (msx + mty) + (bx + dy)
ax + cy = m(sx + ty) + (bx + dy)
(ax + cy) -  (bx + dy) = m(sx + ty)

persamaan terakhir ini berarti bahwa :
m | (ax + cy) -  (bx + dy)
sehingga :
(ax + cy) ≡ (bx + dy) (mod m).
(Terbukti !)

Contoh :
Jika 21 ≡ 1 (mod 4), dan 16 ≡ 2 (mod 7), maka
(21.3 + 16.4) ≡ (1.3 + 2.4) (mod 7)
(63 + 63) ≡ (3 + 8) (mod 7)
126 ≡ 11 (mod 7).










“SIFAT KANSELASI (PENGHAPUSAN)”

Pada persamaan / kesamaan bilangan bulat berlaku sifat kaselasi (penghapusan), yaitu :
Misalkan a,b,dan c bilangan bulat, jika ab = ac, dengan a ≠ 0, maka b = c.

Contoh :
Jika 3.x = 3.6, maka x = 6

Apakakah pada kekongruenan berlaku sifat yang mirip dengan sifat kaselasi (penghapusan) tersebut ?

Misalkan :
jika ab ≡ ac (mod m), dengan a ≠ 0
apakah b ≡ c (mod m) ?

ambil sebuah contoh :
24 ≡ 12 (mod 4)
3.8 ≡ 3.4 (mod 4)
8 ≡ 4 (mod 4)

Akan tetepi, bagaimana dengan contoh berikut :
24 ≡ 12 (mod 4)
2.12 ≡ 2.6 (mod 4)
Apakah 12 ≡ 6 (mod 4)? Jelas tidak, karena 4 tidak membagi (12 – 6)

Dari kedua contoh diatas, dapat disimpulkan bahwa walaupun sifat kaselasi (penghapusan) tidak berlaku sepenuhnya pada relasi kekongruenan, tetapi akan berlaku jika memenuhi syarat seperti yang dinyatakan dalam teorema berikut :

Teorema 5.6:
Jika ac ≡ bc (mod m), dengan (c,m) = 1, , maka a ≡ b (mod m).


Bukti :
Jika ac ≡ bc (mod m), dengan (c,m) = 1, , akan dibuktikan bahwa a ≡ b (mod m).
Jika ac ≡ bc (mod m), berarti m | (ac – bc),
atau m | c(a – b).
Karena m | c(a – b), dengan (c,m) = 1, maka m | (a – b)
Hal ini berarti bahwa a ≡ b (mod m).
(Terbukti !)

Contoh :
Jika 28.1 ≡ 4.1 (mod 1), maka 28 ≡ 4 (mod 1)

Contoh :
Tentukan bilangan-bilangan bulat y yang memenuhi perkongruenan 3y ≡ 1 (mod 7)?
Jawab :
Karena 1 ≡ 15 (mod 7), maka kita dapat mengganti 1 pada pengkongruenan tersebut dengan 15, sehigga diperoleh :
3y ≡ 15 (mod 7)
Selanjutnya karena (3,7) = 1, maka kita dapat membagi 3 pada ruas-ruas perkongruenan tersebut, Sehingga diperoleh :
y ≡ 5 (mod 7)
berarti:
y ≡ 5 + 7k untuk setiap bilangan bulat k,
atau dapat dikatakan bahwa himpunan penyelesaian dari pengkongruenan tersebut adalah {5 + 7k |k bilangan bulat k}.

Kita dapat menghapus (melenyapkan) suatu faktor dari suatu kekongruenan, jika faktor tersebut dan bilangan modulonya saling prima, sebaliknya jika faktor dan bilangan modulonya tidak saling prima, maka kita harus mengganti bilangan modulonya seperti tampak dalam teorema berikut :

Teorema 5.7:
Jika ac ≡ bc (mod m) dengan (c,m) = d,maka a ≡ b (mod m/d).


Bukti :
ac ≡ bc (mod m) berarti m | (ac – bc) atau m| c(a – b), maka m/d | c/d (a-b).
Karena d FPB dari c dan m, maka m/d dan c/d adalah bilangan-bilangan bulat.
Karena (c,m) = d, maka (c/d , m/d) = 1.
Karena (c/d , m/d) = 1, dan m/d | c/d (a-b),maka :
m/d |(a-b)
berarti a ≡ b (mod m/d)
(Terbukti !)
Contoh :
Tentukan x yang memenuhi 2x ≡ 4 (mod 6)

Jawab
2x ≡ 2.2 (mod 6), karena (2,6) = 2, maka :
x ≡ 2 (mod 3)
atau,
x = 3k + 2, untuk setiap bilangan bulat k.

jadi nilai-nilai x adalah {3k + 2}, atau dapat dikatakan bahwa himpunan penyelesaian dari pengkongruenan itu adalah {3k + 2 | k bilangan bulat}.




















DAFTAR PUSTAKA

Sukirman.2006. Pengantar Teori Bilangan.Hanggar Keraton;Yogyakarta.
Limbong,A. Dan Prijono,A.2006.Matematika Diskrit.CV.Budi Utomo;Bandung.
Setiawan,T,B.Stuktur Aljabar.totobara@fkip.unej.ac.id)



























1 komentar:

  1. mau tanya, untuk pembuktian "Jika a ≡ b (mod m), dan c ≡ d (mod m), maka ac ≡ bd (mod m)" itu gimana ya? sekalian contohnya, terima kasih :)

    BalasHapus