Dunia Hitung



DEFENISI DAN SIFAT KEKONGRUENAN


DEFENISI 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 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 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 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 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 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 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
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 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 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}.

Tidak ada komentar:

Poskan Komentar