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.
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
Bukti. 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 . 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
Bukti. 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.
Buktikan
41
membagi habis
220 − 1.
Bukti. 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
220 − 1
merupakan kelipatan
1! + 2! + 3! + · · · + 100!
41.
dibagi oleh
12.
Penyelesaian. 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:
33 ≡ 15(mod 9)dan −35 ≡ 45(mod 8).
Penyelesaian. 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 . dan
Z
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 hanya Setiap
Zn
merupakan
Zn berhingga yaitu
n anggota, sedangkan masing-masing kelas mempunyai takberhingga anggota. a ∈ Z, pasti termuat ke dalam salah satu kelas ekuivalensi di dalam Zn .
Contoh 3.9.
Tentukan residu taknegatif terkecil modulo
35
dari
28 × 33.
Penyelesaian. Pertanyaan ini sama saja dengan menentukan sisa
35.
28 × 33
jika dibagi
Gunakan kongruensi,
28 ≡ −7, 33 ≡ −2 −→ 28 × 33 ≡ (−7)(−2) = 14 karena adalah
0 ≤ 14 < 35 14. Coba cek
Contoh 3.10.
maka disimpulkan residu teknegatif terkecil yang dimaksud
pakai kalkulator!
Tentukan digit terakhir angka desimal dari
1! + 2! + 3! + · · · + 10!.
Penyelesaian. Digit terakhir hanya ditentukan oleh suku-suku yang angka desimalnya
tidak 0. Perhatikan pertama bilangan pasti kelipatan
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. Karena suku kedua bilangan terakhir ini berakhir dengan terakhir yang dimaksud adalah
3.
45
0 maka disimpulkan digit
