3 TEORI KONGRUENSI Pada bab ini dipelajari aritmatika modular yaitu aritmatika tentang kelas-kelas ekuivalensi, dimana permasalahan dalam teori bilangan disederhanakan dengan cara mengganti setiap bilangan bulat dengan sisanya bila dibagi oleh suatu bilangan bulat tertentu
n.
Ini berdampak pada penggantian himpunan bilangan bulat
bilangan oleh
Zn
Zn
yang hanya memuat
n
Zn
dengan suatu sistem
elemen. Banyak sifat yang berlaku pada
seperti operasi penjumlahan dan perkalian.
yang terdapat di dalam
Z
Z
diwarisi
Karena hanya berhingga elemen
maka lebih mudah ditangani. Sebelum masuk ke aritmatika
modular diperhatikan dulu masalah sederhana berikut.
Contoh 3.1.
Misalkan hari ini adalah Sabtu, hari apa setelah 100 hari dari sekarang?
Penyelesaian.
Cara 'konyol' menjawab pertanyaan ini adalah menghitung langsung
satu per satu hari-hari pada kalender sampai dengan hari ke 100. Tetapi dengan mengingat terjadi pengulangan secara periodik setiap 7 hari maka permasalahan ini mudah diselesaikan dengan menghitung sisanya jika 100 dibagi 7, yaitu
100 = 14 × 7 + 2. Jadi 100 hari mendatang adalah hari ke 2 dari sekarang, yaitu Senin.
Contoh 3.2.
Apakah 22051946 bilangan kuadrat sempurna?
Penyelesaian. √
Cara umum untuk menjawab pertanyaan ini adalah dengan menghitung
22051946,
jika hasilnya bulat maka ia kuadrat sempurna. Cara lain adalah den-
gan cara mengkuadratkan bilangan-bilangan bulat, apakah hasilnya ada yang sama dengan bilangan yang dimaksud. Cara yang paling sederhana adalah dengan menggunakan sifat bilangan kuadrat sempurna, yaitu jika bilangan kuadrat sempurna dibagi 4 maka sisanya 0 atau 1.
Artinya, jika sisanya selain dari 0 dan 1 maka
dipastikan ia bukan kuadrat sempurna. Diperoleh
22051946 = 220519 × 100 + 46 = 220519 × (25 × 4) + (11 × 4) + 2 = (220519 + 25 + 11) × 4 + 2, ternyata memberikan sisa 2 sehingga disimpulkan bukan kuadrat sempurna.
39
3 TEORI KONGRUENSI Kedua contoh ini merupakan masalah sederhana pada aritmatika modular, masih banyak masalah rumit pada teori bilangan yang hanya dapat diselesaikan dengan mudah melalui artimatika modular.
3.1 Aritmatika Modular
De nisi 3.1. dan
b
Misalkan
n
sebuah bilangan bulat positif tertentu. Dua bilangan bulat
dikatakan kongruen modulo
n,
ditulis
a≡b jika
n
mod(n)
a − b, atau jika a − b = kn untuk suatu bilangan bulat k . dengan b modulo n, atau a kongruen modulo n dengan b.
membagi selisih
juga, a kongruen
a
Dibaca
Untuk lebih memahami de nisi ini kita amati contoh berikut.
Contoh 3.3.
n = 7 maka diperoleh beberapa fakta berikut 3 ≡ 24 mod(7) sebab 3 − 24 = 21 terbagi oleh 7, −31 ≡ 11 mod(7)sebab −31 − 11 = −42 terbagi oleh 7, −15 ≡ −64 mod(7)sebab −15 + 64 = 49 habis dibagi 7. Tetapi 25 12 mod(7)sebab 25 − 12 = 13 tidak habis dibagi 7, yaitu 25 tidak kongruen dengan 12 modulo 7. Ambil
Pada bagian lainnya relasi kongruensi ini juga terkadang menggunakan notasi
b(mod n),
atau
a ≡n b.
Bila bilangan modulo
cukup ditulis sederhana dengan
a
sudah dipahami dengan baik maka
a ≡ b.
Bila pada algoritma pembagian, diambil bulat
n
a ≡
selalu terdapat hasil bagi
q
n
dan sisa
sebagai pembagi maka sebarang bilangan
r
sehingga
a = qn + r, 0 ≤ r < n. Berdasarkan de nisi kongruensi, relasi ini dapat ditulis sebagai ada
n
pilihan untuk
r
a≡r
mod(n).Karena
maka disimpulkan bahwa setiap bilangan bulat pasti kongruen
0, 1, · · · , n − 1. Khusunya n|a bila hanya bila a ≡ 0 mod(n). Himpunan bilangan {0, 1, · · · , n−1} disebut residu taknegatif terkecil modulo n. Secara umum, kumpulan bilangan bulat a1 , a2 , · · · , an dikatakan membangun himpunan lengkap residu modulo n jika setiap bilangan bulat kongruen dengan salah satu bilangan ak . Dengan kata lain jika a1 , a2 , · · · , an kongruen modulo n dengan 0, 1, · · · , n − 1 dengan urutan yang tidak beraturan. modulo
n
dengan salah satu bilangan
40
3 TEORI KONGRUENSI
Contoh 3.4. modulo
7
Bilangan
−12, −4, 11, 13, 22, 82, 91
membentuk himpunan lengkap residu
sebab
−12 ≡ 2, −4 ≡ 3, 11 ≡ 4, 13 ≡ 5, 22 ≡ 1, 82 ≡ 5, 91 ≡ 0. Jadi prinsipnya dalam suatu himpunan residu lengkap tidak ada dua bilangan yang saling modulo, misalnya
a2 ≡ a5 .
Berikut sifat dua bilangan bulat sebarang jika mereka
saling modulo.
Teorema 3.1. Untuk sebarang bilangan bulat a dan b, a ≡n b bila hanya bila mereka
memberikan sisa yang sama bila dibagi oleh n. Bukti.
a ≡n b maka berdasarkan de nisi a = b + kn untuk suatu k bulat. Misalkan b memberikan sisa r jika dibagi n, yaitu b = qn + r , dengan 0 ≤ r < n. Selanjutnya sisa a jika dibagi n dapat ditemukan sebagai berikut Karena
a = (qn + r) + kn = (q + k)n + r, ternyata juga memberikan sisa yang sama jika dibagi oleh
n,
r.
Sebaliknya, misalkan keduanya memberikan sisa
katakan
a = q1 n + r, b = q2 n + r maka
a − b = (q1 − q2 )n,
yakni
a ≡ n b.
Kongruensi dapat dipandang sebagai generalisasi dari relasi sama dengan. Bila dua bilangan sama maka mereka kongruen terhadap sebarang modulo. Namun dua bilangan yang tidak sama boleh jadi mereka kongruen terhadap modulo tertentu. Sebaliknya dua bilangan yang kongruen modulo tertentu belum tentu sama.
Teorema berikut mem-
berikan sifat-sifat dasar kongruensi.
Teorema 3.2. Misalkan n > 1 sebagai bilangan modulo dan a, b, c, d adalah bilangan
bulat sebarang. Maka pernyataan berikut berlaku : 1. a ≡ a (sifat re eksif) 2. a ≡ b bila hanya bila b ≡ a (simetris) 3. bila a ≡ b dan b ≡ c maka a ≡ c (transitif)
4. bila a ≡ b dan c ≡ d maka a + c ≡ b + d (aditif) dan ac ≡ bd (multiplikatif)
41
3 TEORI KONGRUENSI
5. bila a ≡ b dan k bulat positif sebarang maka ak ≡ bk . Bukti.
a − a = 0 · n maka disimpulkan a ≡ a. Untuk pernyataan 2, gunakan de nisi yaitu a ≡ b↔ a − b = q · n ↔ b − a = (−q) · n ↔ b ≡ a. Pada pernyataan 3, diketahui a ≡ b dan b ≡ c yaitu a − b = q1 · n dan b − c = q2 · n. Diperoleh Karena
a − b + b − c = (q1 + q2 ) · n ↔ a − c = q · n, | {z } q
a − b = q1 · n dan c − d = q2 · n. Bila kedua ruas dijumlahkan diperoleh (a+c)−(b+d) = (q1 +q2 )·n, yaitu a+c ≡ b+d. yakni
a ≡ c.
Untuk pernyataan 4, diketahui
Untuk sifat multiplikatif dicoba sendiri. Pernyataan terakhir dibuktikan dengan
k = 1 maka jelas dipenuhi sebab k k k+1 diketahui a ≡ b. Misalkan berlaku untuk k : a ≡ b maka a = ak a ≡ bk b = bk+1 , yaitu berlaku untuk k + 1. menggunakan prinsip induksi matematika. Untuk
Contoh 3.5. Bukti.
Buktikan
41
membagi habis
220 − 1.
Disini kita berhadapan dengan bilangan yang cukup besar sehingga sangat sulit
ditangani langsung.
Dengan menggunakan kongruensi, permasalahan ini dapat
diselesaikan dengan mudah. Ambil bilangan modulo gan kongruensinya adalah dalam modulo
4
41.
220 .
41,
arahkan salah satu bilan-
25 ≡ −9
Berangkat dari fakta sederhana
tentunya
Dengan Torema (3.2)(5) maka dengan mempangkatkan dengan
diperoleh
25 sehingga diperoleh
Contoh 3.6.
4
≡ (−9)4 = (81)(81) ≡ (−1)(−1) = 1
220 ≡ 1,
yakni
Tentukan sisanya jika
Penyelesaian.
220 − 1
merupakan kelipatan
1! + 2! + 3! + · · · + 100!
41.
dibagi oleh
12.
Tanpa teori kongruensi masalah ini mungkin tidak dapat diselesaikan.
Mulailah dari suku pada deret tersebut yang habis dibagi mempunyai
4! = 24 ≡ 0 modulo 12.
12.
Dalam hal ini kita
Karena suku selanjutnya pasti memuat faktor
4! maka suku-suku tersebut juga habis dibagi oleh 12. Jadi, sisanya 1! + 2! + 3! = 9. Karena bilangan ini tidak dapat dibagi 12 maka inilah dimaksud, yaitu 9. Pada Teorema (3.2) telah dnyatakan bahwa jika
a≡b
maka
ac ≡ bc
hanyalah sisa yang
terhadap modulo
yang sama. Sebaliknya, belum ada sifat kanselasi atau pembagian yang membawa
bc
menjadi
a ≡ b.
ac ≡
Ternyata sifat ini tidak berlaku otomatis, seperti diberikan pada
teorema berikut.
42
3 TEORI KONGRUENSI
Teorema 3.3. Jika ac ≡ bc(mod n)maka a ≡ b(mod nd )dimana d = gcd(c, n). Bukti.
Berdasarkan hipotesis dapat ditulis
(a − b)c = ac − bc = k · n untuk suatu
s :=
k
bulat. Karena
n adalah prima relatif. d
d = gcd(c, n) maka kedua bilangan bulat r := dc dan Substitusi c = dr dan n = ds ke dalam persamaan
sebelumnya diperoleh
(a − b)dr = k(ds) → (a − b)r = k · s s|(a−b)r. a ≡ c(mod nd ).
Jadi,
Karena
gcd(r, s) = 1 maka s|(a−b) yang berarti a ≡ b(mod s)atau
Akibat 3.1. Jika ac ≡ bc(mod n)dan gcd(c, n) = 1 maka a ≡ b(mod n). c pada ac ≡ bc p - c maka gcd(p, c) = 1.
Akibat ini menyatakan bahwa kita dapat melakukan kanselasi dan
n
prima relatif. Amati bahwa jika
p
prima dan
asalkan
c
Fakta ini
menghasilkan akibat berikut.
Akibat 3.2. Jika p prima, p - c dan ac ≡ bc(mod p)maka a ≡ b(mod p). Contoh 3.7.
Sederhanakan kongruensi berikut:
Penyelesaian.
33 ≡ 15(mod 9)dan −35 ≡ 45(mod 8).
Kongruensi pertama diselesaikan sebagai berikut:
33 ≡ 15(mod 9) ↔ 11 · 3 ≡ 5 · 3(mod 9) ↔ 11 ≡ 5(mod 9) sebab
gcd(3, 9) = 3.
Untuk kongruensi kedua diselesaikan sejalan,
−35 ≡ 45(mod 8) ↔ 5 · (−7) ≡ 5 · 9(mod 8) ↔ −7 ≡ 9(mod 8) sebab
5
dan
8
prima relatif.
3.2 Kelas-kelas Ekuivalensi Pada Teorema (3.2), sifat re eksif, simetris dan transitif menunjukkan bahwa untuk sebarang ibatnya,
n bulat positif, relasi kongruensi ≡n merupakan relasi ekuivalensi pada Z. Akhimpunan Z terpartisi atas kelompok-kelompok yang saling asing yang disebut
43
3 TEORI KONGRUENSI kelas-kelas ekuivalensi.
Kelas-kelas ekuivalensi ini dinyatakan dengan notasi
[a]n dan
dide nisikan sebagai
[a]n : = {b ∈ R : a ≡ b(mod n)} = {· · · , a − 2n, a − n, a, a + n, a + 2n, · · · } . [a]n merupakan himpunan semua bilangan bulat yang kongruen modulo n dengan a. Kita memandang para bilangan di dalam [a]n ini sebagai satu kesatuan. Bila bilangan modulo n sudah dipastikan maka cukup menggunakan notasi [a] untuk maksud [a]n . Karena pembagian dengan n akan memberikan n kemungkinan sisa r = 0, 1, · · · , n − 1 sehingga setiap bilangan pada Z pasti kongruen dengan salah satu sisa tersebut. Jadi sesungguhnya bilangan bulat Z terpartisi atas n kelas ekuivalensi, yaitu Jadi
[0] = {· · · , −2n, n, 0, n, 2n, · · · } [1] = {· · · , 1 − 2n, 1 − n, 1, 1 + n, 1 + 2n, · · · } [2] = {· · · , 2 − 2n, 2 − n, 2, 2 + n, 2 + 2n, · · · } . . .
[n − 1] = {· · · , −n − 1, −1, n − 1, 2n − 1, 3n − 1, · · · } Tidak ada kelas ekuivalensi lainnya. Bila dilanjutkan maka kelas ekuivalensi berikutnya kembali ke semula. Misalnya,
[n] = {· · · − n, 0, n, 2n, 3n, · · · } = [0]. Secara umum berlaku
[a] = [b] ←→ a ≡ b(mod n).
Contoh 3.8.
Untuk
n=1
hanya terdapat 1 kelas ekuivalensi, yaitu
[0] = {0 + k · 1 : k ∈ Z} = {k : k ∈ Z} = Z. Untuk
n=2
terdapat dua kelas ekuivalensi, yaitu
[0] = {0 + k · 2 : k ∈ Z} = {2k : k ∈ Z} = 2Z [1] = {1 + k · 2 : k ∈ Z} = {2k + 1 : k ∈ Z} = 2Z + 1.
44
(3.1)
3 TEORI KONGRUENSI
De nisi 3.2.
Untuk suatu
n≥1
yang diberikan,
kelas-kelas ekuvalensi terhadap modulo
n,
Zn
dide nisikan sebagai himpunan
yaitu
Zn := {[0], [1], · · · , [n − 1]} Selanjutnya, pada
Zn
(3.2)
dide nisikan operasi penjumlahan, pengurangan dan perkalian
berikut:
[a] + [b] := [a + b], [a] − [b] = [a − b], [ab] = [a][b] untuk setiap
Perbedaan
(3.3)
[a], [b] ∈ Zn .
Z
dan
Zn
dapat dijelaskan sebagai berikut:
Z
merupakan himpunan semua
bilangan bulat sehingga banyak anggotanya takberhingga, sedangkan himpunan yang memuat kelas-kelas ekuivalensi. Jadi banyak anggota
Zn
merupakan
Zn berhingga yaitu
n anggota, sedangkan masing-masing kelas mempunyai takberhingga anggota. Setiap a ∈ Z, pasti termuat ke dalam salah satu kelas ekuivalensi di dalam Zn . Ilustrasi
hanya
kelas-kelas ekuivalensi ditunjukkan pada Gambar berikut.
[1]
[0] [3]
[2]
...
[n-1]
Figure 3.1: Kelas-kelas ekuivalensi pada
Contoh 3.9.
Tentukan residu taknegatif terkecil modulo
Penyelesaian.
35.
35
Z
dari
28 × 33.
Pertanyaan ini sama saja dengan menentukan sisa
28 × 33
Gunakan kongruensi,
28 ≡ −7, 33 ≡ −2 −→ 28 × 33 ≡ (−7)(−2) = 14
45
jika dibagi
3 TEORI KONGRUENSI karena adalah
0 ≤ 14 < 35 14. Coba cek
maka disimpulkan residu teknegatif terkecil yang dimaksud
pakai kalkulator!
Contoh 3.10.
Tentukan digit terakhir angka desimal dari
Penyelesaian.
Digit terakhir hanya ditentukan oleh suku-suku yang angka desimalnya
tidak 0. Perhatikan pertama bilangan pasti kelipatan
10.
1! + 2! + 3! + · · · + 10!.
5! = 5·4·3·2·1 = 120.
Bilangan selanjutnya
Jadi dapat ditulis
1! + 2! + 3! + 4! + · · · + 10! = 1 + 2 + 6 + 24 + 10k = 33 + 10k = 3 + (3 + k)10. 0 maka disimpulkan digit
Karena suku kedua bilangan terakhir ini berakhir dengan terakhir yang dimaksud adalah
3.
3.3 Kongruensi Linier
De nisi 3.3. Sebuah persamaan yang berbentuk ax ≡ b(mod n)disebut kongruensi linier. Penyelesaiannya adalah setiap bilangan x0 yang memenuhi ax0 ≡ b(mod n). x0 y0 .
Dengan de nisi ini untuk setiap penyelesaian
ax0 − ny = b ax ≡ b(mod n)
untuk suatu bilangan bulat
berlaku
n|(ax0 − b),
ekuivalen dengan
Jadi menyelesaikan kongruensi linier
sama saja dengan menyelesaikan persamaan Diophantine
ax0 − ny0 = b Pada kongruensi linier
b,
jadi
x0
ax ≡ b(mod n),
jika
x
penyelesaian dan
juga merupakan penyelesaian. Walaupun
x
dan
x0
x0 ≡ x
maka
ax0 ≡ ax =
berbeda dalam arti biasa
namun mereka dianggap 'sama' karena membentuk kelas ekuivalensi. Sebagai contoh,
x = 3
dan
x = −9
keduanya memenuhi
3x ≡ 9(mod 12)
sebab
3 ≡ −9(mod 12).
Kedua penyelesaian ini dianggap sama. Banyaknya penyelesaian dihitung berdasarkan banyaknya penyelesaian yang tidak kongruen.
Teorema 3.4. Jika d = gcd(a, n) maka kongruensi linier ax ≡ b(mod n)
mempunyai penyelesaian jika hanya jika d|b. Jika d|b dan x0 penyelesaian penyelesaian
46
3 TEORI KONGRUENSI
tertentu (khusus) maka penyelesaian umumnya diberikan oleh x = x0 +
n t, t ∈ Z. d
Khususnya, para penyelesaian ini membentuk tepat d kelas-kelas ekuivalensi dengan representasi
n n n , x0 + (2), · · · , x0 + (d − 1). d d d Bukti. Karena kongruensi linier ax ≡ b(mod n) ekuivalen dengan persamaan Diophantine ax − ny = b maka ia mempunyai penyelesaian jika d = gcd(a, n) membagi b, yaitu d|b. Bila x0 dan y0 penyelesaian khusus persamaan ini maka penyelesaian x = x0 , x0 +
umumnya dapat disajikan sebagai
x = x0 +
n a t, y = y0 + t. d d d penyelesaian berdasarkan kelas, x0 + (d−1)t . Untuk ini pertama dibukd
Selanjutnya ditunjukkan hanya terdapat tepat kelas ekuivalensi
x = x0 , x0 +
t , x0 d
+
2t ,··· d
tikan tidak ada para panyelesaian ini yang kongruen satu sama lainnya. Andaikan ada dua yang kongruen, katakan
x0 +
Akhirnya diperoleh
x0 + nd t1
dan
x0 + nd t2
maka diperoleh
n n t2 ≡ x0 + t1 (mod n), 0 ≤ t1 ≤ t2 < d d d n n t2 ≡ t1 (mod n) d d n n ,n = . t2 ≡ t1 (mod d), sebab gcd d d
d|(t2 − t1 ).
Hal in tidaklah mungkin karena
t2 − t1 < d.
Kontradiksi. Jadi disimpulkan semua penyelesaian ini tidak ada yang kongruen, atau mereka dianggap penyelesaian yang berbeda. Dibuktikan juga bahwa selain dari penyelesaian tersebut yaitu
x = x0 + nd t, t = d, d + 1, · · ·
kongruen dengan
salah satu penyelesaian tersebut. Berdasarkan algoritma pembagian, dapat ditulis
t = qd + r, 0 ≤ r < d
sehingga
x0 +
Padahal,
n n t = x0 + (qd + r) d d n = x0 + nq + r d n ≡ x0 + r(mod n). d
x0 + nd r(mod n) merupakan salah satu penyelesaian yang sudah ada.
47
3 TEORI KONGRUENSI
Akibat 3.3. Bila gcd(a, n) = 1 maka kongruensi linier ax ≡ b(mod n) mempunyai tepat satu penyelesaian.
Contoh 3.11.
Diperhatikan kongruensi linier
ini mempunyai penyelesaian?
18x ≡ 30(mod 42).
Apakah kongruensi
Bila iya, ada berapa penyelesaian berbeda?
Temukan
penyelesaian tersebut!
Penyelesaian.
Karena
d = gcd(18, 42) = 6
dan ia membagi
30
maka disimpulkan kon-
gruensi ini mempunyai penyelesaian, dengan banyak penyelesaian berbeda
6 buah.
Untuk menyelesaikan kongruensi ini, ubah dulu ke dalam bentuk persamaan Diophantine berikut
18x − 42y = 30.
Tapi cara ini cukup panjang. Cara lain dapat
pula dengan melakukan inspeksi langsung, yaitu dapat diperiksa bahwa
x0 = 4
adalah salah satu penyelesaian. Penyelesaian umumnya dapat ditulis sebagai
x = 4 + 7t(mod 42), t = 0, 1, · · · , 5 atau
x = 4, 11, 18, 25, 32, 39(mod 42).
Contoh 3.12.
Selesaikan kongruesi linier berikut
(i) 9x ≡ 21(mod 30) (ii) 7x ≡ 3(mod 12) (iii) 10x ≡ 6(mod 12)
48
