Melanjutkan pos sebelumnya, sekarang kita membahas persamaan modulo. Tapi sebelumnya, mari bahas invers modulo dulu. Apa itu invers modulo? seperti yang sudah aku jelasin sebelumnya, operasi pembagian pada modulo itu agak beda sama operasi aritmatika biasa. Perhatikan kalo modulo itu selalu bilangan bulat. Berarti kalo ada $\frac{1}{5} \pmod {3}$ bisa gak? Jawabannya.... bisa! tapi pecahan disini bukan bener-bener pecahan :v
Note: sebenarnya aku ga tau bisa apa engga dijadiin bentuk pecahan gini, yang jelas bener nulisnya itu ${5}^{-1} \pmod {3}$. Tapi aku pake dulu disini biar ga bingung.
Jadi, $\frac{1}{5} \pmod {3}$ disini didefinisikan sebagai suatu bilangan bulat $x$ sehingga $x \equiv \frac{1}{5} \pmod {3}$.
Dengan kata lain, $5x \equiv 1 \pmod {3}$. Apa $x$ yang memenuhi? 2 memenuhi kan ya karena $5 \times 2 \equiv 1 \pmod {3}$. Maka $x \equiv \frac{1}{5} \equiv 2 \pmod {3}$. Mulai keliatan kan persamaannya dimana muehehe.
"Kok bisa dapet 2? Gimana cara nyarinya?"Jelas coba-coba! \:v/ Jadi untuk soal ini in the worst case kita coba-coba 3 kali kan ya, mulai dari $x$ = 0 sampai 2. Sebenarnya ada cara-cara yang bisa digunakan untuk mencari solusinya, tapi menurutku untuk soal-soal OSK dan OSP yang palingan cuma belasan (belasan kali nyari, ez lah) masih lebih cepet complete search (baca: nguli. Coba satu-satu) daripada cara beneran :v.
"Yah tapi aku mau tau caranya :("Jangan sedih! InsyaAllah aku bakal pos tentang caranya, dengan judul... "Persamaan Diophantine". Ditunggu ya (?).
"Hmm okelah, tapi gimana kalo udah nyari semuanya (di soal ini dari 0 sampe 2) tapi ga ketemu?"Ada 2 kemungkinan.
- Hitunganmu salah
- Emang ga ada solusinya
"Loh ga ada solusinya? Kok bisa?"Ya bisa dong B-) contohnya $2x \equiv 1 \pmod {4}$. Kenapa ga punya solusi? karena persamaan $ax \equiv 1 \pmod {b}$ memiliki solusi jika dan hanya jika $a$ dan $b$ relatif prima (FPBnya 1). Coba kamu buktiin ini setelah belajar persamaan diophantine :p. Tapi biasanya soal-soal di OSK & OSP ada solusinya, jadi kalo ga ketemu coba periksa lagi, siapa tau hitunganmu salah.
"Hmm.. oke deh. Coba soal-soal lain dong"Makan nih :v (arahkan mouse ke soal untuk jawabannya)
$3x \equiv 1 \pmod {5}$ 2
$23y \equiv 59 \pmod {7}$ Perhatikan kalau ekivalen dengan $2y \equiv 3 \pmod {7}$. Hasil 5.
$50z \equiv 33 \pmod {13}$ ekivalen dengan $11z \equiv 7 \pmod {13}$. Ekivalen juga dengan $-2z \equiv -6 \pmod {13}$. Hasil 3.
Coba liat soal terakhir. tau kan ya kenapa dijadiin $11z \equiv 7 \pmod {13}$. biar gampang ngitungnya. tapi masih bisa disederhanain lagi pake mod yang negatif. jadilah $-2z \equiv -6 \pmod {13}$. masih bisa lagi gak disederhanain? bisa. perhatiin kalo $-2z$ sama $-6$ sama-sama bisa dibagi -2. bagi aja -2. jadilah $z \equiv 3 \pmod {13}$. langsung ketemu deh hasilnya. Sekarang coba $2x \equiv 6 \pmod {12}$
"Wahaha gampang nih. Sederhanain aja jadi $x \equiv 3 \pmod {12}$. Ketemu deh :p"Bagus. Salah.
"Lah kok salah? bener kok $2 \times 3 = 6$ -_-"Coba masukin 9.
"$2 \times 9 \equiv 18 \equiv 6 \pmod {12}$ Oh iya 6 juga ya. terus kenapa? ._."Ya solusimu kurang lengkap lah -_- $3 \pmod {12}$ kan berarti $\dots, -21, -9, 3, 15, 27, \dots$ ga ada 9.
"... terus gimana dong :') aturannya apa sih?"
Aturan penyederhanaan mod:
$ax \equiv ab \pmod {c}$ ekivalen dengan $x \equiv b \pmod {c}$ jika $c$ tidak habis dibagi $a$.
Selain itu, $ax \equiv ab \pmod {ac}$ ekivalen dengan $x \equiv b \pmod {c}$.
"Oke oke, berarti $2x \equiv 6 \pmod {12}$ ekivalen dengan $x \equiv 3 \pmod {6}$"Mantab jiwa!
"Tapi... buat apa sih kita belajar ginian?"
Soal
ada 2 barisan aritmatika
$1, 4, 7, 10, 13, \dots$
$2, 9, 16, 23, 30, \dots$
cari bilangan positif terkecil yang ada di kedua barisan tersebut.
Perhatikan kalo barisan pertama $1 \pmod {3}$
barisan kedua $2 \pmod {7}$
katakan bilangan positif terkecil yang ada di kedua barisan adalah $x$. Maka pasti
$x \equiv 1 \pmod {3}$ dan $x \equiv 2 \pmod {7}$.
karena $x \equiv 1 \pmod {3}$ maka $x$ bisa dinyatakan dalam $x = 3a+1$. Maka
$x \equiv 3a + 1 \equiv 2 \pmod {7}$
$3a \equiv 1 \pmod {7}$
$a \equiv 5 \pmod {7}$
maka $a$ bisa dinyatakan dalam $a = 7b+5$
balikin lagi ke $x$
$x = 3a+1 = 3(7b+5)+1 = 21b+16$
$x$ juga bisa dinyatakan dengan $x \equiv 16 \pmod {21}$
maka jawabannya 16 (karena terkecil). Perhatikan juga kalo $37, 58, 79, \dots$ juga ada di kedua barisan.
barisan kedua $2 \pmod {7}$
katakan bilangan positif terkecil yang ada di kedua barisan adalah $x$. Maka pasti
$x \equiv 1 \pmod {3}$ dan $x \equiv 2 \pmod {7}$.
karena $x \equiv 1 \pmod {3}$ maka $x$ bisa dinyatakan dalam $x = 3a+1$. Maka
$x \equiv 3a + 1 \equiv 2 \pmod {7}$
$3a \equiv 1 \pmod {7}$
$a \equiv 5 \pmod {7}$
maka $a$ bisa dinyatakan dalam $a = 7b+5$
balikin lagi ke $x$
$x = 3a+1 = 3(7b+5)+1 = 21b+16$
$x$ juga bisa dinyatakan dengan $x \equiv 16 \pmod {21}$
maka jawabannya 16 (karena terkecil). Perhatikan juga kalo $37, 58, 79, \dots$ juga ada di kedua barisan.
note: perhatikan kalo 21 merupakan KPK 3 dan 7.
Udahan ya soal warasnya, males bikin cerita muehehe langsung aja tentuin $x$ yang memenuhi
$x \equiv 1 \pmod {10}$
$x \equiv 3 \pmod {18}$
$x \equiv 3 \pmod {4}$
Kita mulai dari mod yang paling besar dulu ya (coba pikirin kenapa).
$x = 18a + 3$
$18a + 3 \equiv 1 \pmod {10}$
$8a \equiv 8 \pmod {10}$
$4a \equiv 4 \pmod {5}$
$a \equiv 1 \pmod {5}$
$a = 5b+1$
$x = 18a+3 = 18(5b+1)+3 = 90b+21$
$90b+21 \equiv 3 \pmod {4}$
$2b \equiv 2 \pmod {4}$
$b \equiv 1 \pmod {2}$
$b = 2c+1$
$x = 90b+21 = 90(2c+1)+21 = 180c+111$
maka $x \equiv 111 \pmod {180}$
$x = 18a + 3$
$18a + 3 \equiv 1 \pmod {10}$
$8a \equiv 8 \pmod {10}$
$4a \equiv 4 \pmod {5}$
$a \equiv 1 \pmod {5}$
$a = 5b+1$
$x = 18a+3 = 18(5b+1)+3 = 90b+21$
$90b+21 \equiv 3 \pmod {4}$
$2b \equiv 2 \pmod {4}$
$b \equiv 1 \pmod {2}$
$b = 2c+1$
$x = 90b+21 = 90(2c+1)+21 = 180c+111$
maka $x \equiv 111 \pmod {180}$
note: perhatikan bahwa 180 adalah KPK dari 4, 10, dan 18
Tentukan $x$ yang memenuhi
$x \equiv 5 \pmod {6}$
$x \equiv 7 \pmod {8}$
$x \equiv 10 \pmod {11}$
Perhatikan kalo
$x \equiv -1 \pmod {6}$
$x \equiv -1 \pmod {8}$
$x \equiv -1 \pmod {11}$
KPK 6, 8, 11 berapa? 264
berarti jawabannya $x \equiv -1 \equiv 263 \pmod {264}$. BAMM.
$x \equiv -1 \pmod {6}$
$x \equiv -1 \pmod {8}$
$x \equiv -1 \pmod {11}$
KPK 6, 8, 11 berapa? 264
berarti jawabannya $x \equiv -1 \equiv 263 \pmod {264}$. BAMM.
Aku punya 4 pacar, 2 hari lalu ketemu sama pacar pertama dan ketemuan setiap 3 hari sekali. Bakal ketemu sama pacar kedua 3 hari lagi dan ketemuan setiap 5 hari sekali. Kalo sama pacar yang ketiga sih 11 hari sekali tapi besok ketemuan. Nah kalo yang keempat ketemuan 13 hari sekali dan 3 hari lagi ketemuan. Berapa hari lagi aku ketemu sama keempat pacarku?
$x \equiv -2 \pmod {3}$
$x \equiv 3 \pmod {5}$
$x \equiv 1 \pmod {11}$
$x \equiv 3 \pmod {13}$
coba liat kalo
$x \equiv 1 \pmod {3}$
$x \equiv 1 \pmod {11}$
$x \equiv 3 \pmod {5}$
$x \equiv 3 \pmod {13}$
sederhanain jadi
$x \equiv 1 \pmod {33}$
$x \equiv 3 \pmod {65}$
Seperti biasa, dari yang paling gede.
$x = 65a + 3$
$65a + 3 \equiv 1 \pmod {33}$
$-a \equiv -2 \pmod {33}$
$a \equiv 2 \pmod {33}$
$a = 33b+2$
$x = 65(33b+2)+3$
$x = 2145b+133$
jadi bakal ketemu keempat pacar 133 hari lagi (doain belum putus ya :') )
$x \equiv 3 \pmod {5}$
$x \equiv 1 \pmod {11}$
$x \equiv 3 \pmod {13}$
coba liat kalo
$x \equiv 1 \pmod {3}$
$x \equiv 1 \pmod {11}$
$x \equiv 3 \pmod {5}$
$x \equiv 3 \pmod {13}$
sederhanain jadi
$x \equiv 1 \pmod {33}$
$x \equiv 3 \pmod {65}$
Seperti biasa, dari yang paling gede.
$x = 65a + 3$
$65a + 3 \equiv 1 \pmod {33}$
$-a \equiv -2 \pmod {33}$
$a \equiv 2 \pmod {33}$
$a = 33b+2$
$x = 65(33b+2)+3$
$x = 2145b+133$
jadi bakal ketemu keempat pacar 133 hari lagi (doain belum putus ya :') )
Kayaknya udah cukup materi tentang mod :/ sampai jumpa di pos selanjutnya!
