Saran
dan komentar dipersilakan. Silakan share tanpa perlu minta ijin.
----------------------------------------------------------------------------------------
Tentukan angka terakhir dari 2013^2013.
Tentukan
sisa pembagian 2013^2012^2011 dibagi 123.
Dua
soal di atas adalah contoh soal yang cocok menggunakan modulo. Apa itu modulo?
Operasi modulo, beserta aritmatika modulus, adalah dua konsep dasar dari teori
bilangan.
Konsep
1: Operasi modulo dalam matematika
Jika a adalah
bilangan bulat dan b adalah bilangan asli (bulat positif),
maka a mod b adalah sebuah bilangan bulat c dimana 0 ≤
c ≤ b-1, sehingga a-c adalah kelipatan b.
Contohnya, 7 mod 3 = 1, karena 7-1 adalah kelipatan 3. Perhatikan bahwa 7 mod 3
!= 4, karena 4 >= 3, dan 7 mod 3 != 2, karena 7-2 bukan kelipatan 3. Bisa
dibayangkan bahwa a mod b itu sisa pembagian dari a dibagi b.
Tapi hati-hati untuk nilai a negatif: -7 mod 3 = 2.
Teorema
1: Kumpulan sifat distributif mengenai modulo
Jika a,
b adalah bilangan bulat dan n adalah bilangan asli,
maka:
1. (a+b)
mod n = (a mod n + b mod n) mod n
2. (ab)
mod n = ((a mod n) * (b mod n)) mod n
3. (a^b)
mod n = ((a mod n)^b) mod n, untuk b bilangan bulat
nonnegatif
Latihan
1
1.
Tentukan nilai dari 9876543210 mod 12.
2.
Tentukan nilai dari (97531*8642 - 13579*2468) mod 20.
3.
Tentukan angka terakhir dari 1 + 2 + 3 + ... + 2013. (Asumsi: Umumnya,
"angka terakhir" itu dalam basis 10. Kalau diperbolehkan bertanya
tentang soal, coba tanyakan; kalau tidak, bekerja dengan basis 10. Dalam soal
ini, angka terakhir adalah dalam basis 10. Hint: "Angka terakhir dalam
basis 10" berarti "mod 10". 1 + 2 + ... + n = n(n+1)/2.)
Konsep
2: Aritmatika modulo
a = b
(mod c) berarti a mod c = b mod c.
Konsep
3: Invers modulo
Jika a adalah
bilangan bulat dan n adalah bilangan asli, dan a, n saling
relatif prima, maka terdapat sebuah nilai b sehingga ab
= 1 mod n. Nilai bdisebut invers dari a modulo n.
----------------------------------------------------------------------------------------
Umumnya,
soal modulo tidak semudah Latihan 1. Ada beberapa tambahan konsep yang dipakai.
Konsep
4: Euler's totient function (φ)
Jika n adalah
bilangan asli, maka φ(n) adalah banyak bilangan asli ≤ nyang
relatif prima dengan n. Misalnya, φ(12) = 4, karena di antara
bilangan-bilangan asli ≤ 12 (yaitu 1,2,3,4,5,6,7,8,9,10,11,12), hanya ada empat
buah (1,5,7,11) yang saling relatif prima dengan 12. Perhatikan bahwa φ(1) = 1,
bukan 0.
Untuk
selanjutnya, φ akan disebut "phi".
Teorema
2: Menghitung phi(n) dari faktorisasi prima n
Jika p1,
p2, ..., pk adalah seluruh faktor prima dari n, maka phi(n)
= n * (p1 - 1)/p1 * (p2 - 1)/p2 * ... * (pk - 1)/pk. Misalnya, karena
faktor-faktor prima dari 12 adalah 2 dan 3, maka:
phi(12)
= 12 *
(2-1)/2 * (3-1)/3
= 12 *
1/2 * 2/3
= 4
yang
sesuai dengan contoh pada Konsep 3.
Latihan
2
1. Tentukan
nilai dari phi(6).
2.
Tentukan nilai dari phi(2013).
3.
Tentukan nilai dari phi(2009).
4.
Buktikan bahwa jika p adalah bilangan prima maka phi(p)
= p-1. Jika ini bisa dibuktikan tanpa menggunakan Teorema 2, berarti bagus,
ini langkah pertama membuktikan Teorema 2. Sisanya cari sendiri :)
Teorema
3: Euler's theorem
Jika a adalah
bilangan bulat, n adalah bilangan asli, dan a dan n saling
relatif prima, maka a^phi(n) = 1 (mod n).
Digunakan
bersama dengan a^(m+n) = a^m * a^n untuk bilangan bulata,m,n apapun,
kita dapat menggunakan Euler's theorem untuk menyelesaikan beberapa soal.
Contoh:
Tentukan angka terakhir dari 2013^2013.
Solusi
2013^2013
mod 10
=
(2013 mod 10)^2013 mod 10 (dari Teorema 1.3)
=
3^2013 mod 10
Perhatikan
bahwa phi(10) = 10 * 1/2 * 4/5 = 4. Maka, 2013^2013 mod 10
=
3^(2013 mod phi(10)) mod 10 (dari Euler's theorem)
=
3^(2013 mod 4) mod 10
= 3^1
mod 10
= 3
mod 10
= 3
Latihan
3
1.
Tentukan angka terakhir dari 567^890.
2.
Tentukan nilai dari 2010^2010 mod 2011. (Hint: 2011 adalah bilangan prima.)
3.
Tentukan angka terakhir dari 3^3 + 13^13 + 23^23 + ... + 2013^2013.
Teorema
4: Chinese Remainder Theorem
Jika a1,
a2, ..., ak adalah bilangan asli yang saling relatif prima, dan b1,
b2, ..., bk adalah bilangan bulat, maka ada bilangan bulat x yang
memenuhi:
x = b1
mod a1
x = b2
mod a2
...
x = bk
mod ak
Selanjutnya,
nilai x mod (a1*a2*...*ak) adalah unik.
Chinese
Remainder Theorem (disingkat CRT) umumnya dipakai dimana Euler's theorem tidak
dapat berjalan; saat a dan n tidak relatif
prima.
Contoh:
Tentukan angka terakhir dari 2012^2012.
Kita
tidak boleh langsung memasukkan ke Euler's theorem.
Solusi
salah
2012^2012
mod 10
=
2^2012 mod 10
Karena
phi(10) = 4, maka 2012^2012 mod 10
=
2^(2012 mod 4) mod 10
= 2^0
mod 10
= 1
Kita
harus menggunakan cara lain. Biasanya, kita pakai CRT dengan cara ini.
Solusi
benar
Berdasarkan
CRT, kita dapat menentukan nilai dari x mod 10 diberikan xmod
2 dan x mod 5. Untuk x = 2012^2012, kita
dapat:
2012^2012
mod 2
=
(2012 mod 2)^2012 mod 2 (Teorema 1.3)
=
0^2012 mod 2
= 0
Karena
phi(5) = 4, maka:
2012^2012
mod 5
=
(2012 mod 5)^(2012 mod phi(5)) mod 5 (Teorema 1.3 dan Euler's theorem)
= 2^0
mod 5
= 1
Maka
kita cari sebuah nilai x sehingga x = 0 (mod
2) dan x = 1 (mod 5). Didapat bahwa nilainya adalah x =
6 (mod 10), sehingga 2012^2012 mod 10 = 6.
Latihan
4
1.
Tentukan angka terakhir dari 2014^2014.
2.
Tentukan nilai dari 1000^1000 mod 2013.
3.
Tentukan nilai dari 2013^2012^2011 mod 123. (Asumsi: a^b^c berartia^(b^c),
bukan (a^b)^c = a^(bc).)
4.
Tentukan angka terakhir dari 1^1 + 2^2 + 3^3 + ... + 2013^2013.
Selamat,
sekarang Anda sudah dapat mengerjakan soal-soal modulo yang cukup umum!
Teorema
5: Teorema Wilson
Jika p bilangan
prima, maka (p-1)! = -1 mod p.
Tentukan sisa pembagian (10!)^(10!) oleh 11.
Solusi
Berdasarkan
Teorema Wilson, karena 11 adalah bilangan prima, maka 10! = -1 mod 11. Maka
kita mencari (-1)^(10!) mod 11.
Perhatikan
bahwa 10! genap; dia mengandung faktor 2. Berarti hasilnya adalah (-1)^(genap) mod
11 = 1 mod 11.
Teorema
6: Menentukan nilai yang memenuhi CRT
Ada
algoritma konstruktif untuk menentukan nilai x dalam CRT
selain mencoba satu per satu, namun algoritmanya cukup sulit. Kalau tertarik,
di bawah ini adalah algoritmanya.
Diberikan a1,
a2 bilangan yang saling relatif prima dan b1, b2 bilangan
bulat, kita akan menentukan x sehingga x = b1 mod a1 dan x
= b2 mod a2.
Pertama,
kita gunakan Extended Euclidean Algorithm untuk menghitung invers dari a1
mod a2 dan invers dari a2 mod a1. Anggap a1 >
a2; kalau tidak, ubah posisinya. Bisa dilihat di Wikipedia:https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Table_method
Siapkan
sebuah tabel berisi 4 kolom: K, D, X, Y.
Pertama,
tuliskan 0, a1, 1, 0 pada baris pertama.
Selanjutnya,
tuliskan 0, a2, 0, 1 pada baris selanjutnya.
Sekarang,
mulai dari baris ketiga. Misalkan bilangan pada kolom D, X, Y di baris
sebelumnya adalah d2, x2, y2, dan pada baris sebelumnya lagi
adalah d1, x1, y1. Maka isi pada kolom K bilangan k =
floor(d1/d2). Selanjutnya, isi pada kolom D, X, Y bilangan-bilangan d1
- k*d2, x1 - k*x2,y1 - k*y2.
Lanjutkan
terus sampai kolom D berisi angka 0. Hapus baris terakhir yang ditulis dan
ambil bilangan-bilangan pada kolom X dan Y di baris terakhir ini; misalkan
bilangannya d1 dan d2. Berarti d1 adalah
invers a1 moduloa2, dan d2 adalah
invers a2 modulo a1.
Contoh,
untuk 14 dan 11:
Permulaan:
K D X
Y
0 14 1
0
0 11 0
1
Baris
ketiga: k = floor(14/11) = 1. Berarti kita tulis 1.
K D X
Y
0 14 1
0
0 11 0
1
1
Selanjutnya,
kita tulis 14 - 1*11 = 3 pada D, 1 - 1*0 = 1 pada X, 0 - 1*1 = -1 pada Y.
K D X
Y
0 14 1
0
0 11 0
1
1 3 1
-1
Selanjutnya
lagi, k = floor(11/3) = 3.
K D X
Y
0 14 1
0
0 11 0
1
1 3 1
-1
3
D = 11
- 3*3 = 2, X = 0 - 3*1 = -3, Y = 1 - 3*(-1) = 4
K D X
Y
0 14 1
0
0 11 0
1
1 3 1
-1
3 2 -3
4
Kita
lanjutkan terus:
K D X
Y
0 14 1
0
0 11 0
1
1 3 1
-1
3 2 -3
4
1 1 4
-5
2 0
Karena
kita dapat D = 0, kita hapus baris yang terakhir ini.
K D X
Y
0 14 1
0
0 11 0
1
1 3 1
-1
3 2 -3
4
1
1 4 -5
Maka
invers dari 14 mod 11 adalah 4 (mod 11) dan invers dari 11 mod 14 adalah -5
(mod 14). Kita cek ulang, memang 14*4 = 1 (mod 11) dan 11*(-5) = 1 (mod 14).
Selanjutnya,
setelah dapat nilai-nilai d1 dan d2, kita langsung
dapat nilai x = b1*a2*d2 + b2*a1*d1 (mod (a1*a2)).
Misalnya,
dari lanjutan contoh di Teorema 4:
x =
1 mod 5
x = 0
mod 2
(Selalu
susun supaya modulo lebih besar di atas.)
Kita
mulai dengan Extended Euclidean Algorithm:
K D X
Y
0 5 1
0
0 2 0
1
2
1 1 -2
2 0
Berarti x =
1*2*(-2) + 0*5*1 = -4 = 6 (mod 10).
Comments
Post a Comment