"hah? apaan tuh?"jadi begini, kalo ada soal "apa digit terakhir dari ${ 2 }^{ 15 }$?"
"hmm...tepat sekali! kalo ${ 2 }^{ 20 }$?
${ 2 }^{ 1 } = 2$ berarti $2$
${ 2 }^{ 2 } = 4$ berarti $4$
${ 2 }^{ 3 } = 8$ berarti $8$
${ 2 }^{ 4 } = 16$ berarti $6$
${ 2 }^{ 5 } = 32$ berarti $2$
${ 2 }^{ 6 } = 64$ berarti $4$
${ 2 }^{ 7 } = 128$ berarti $8$
${ 2 }^{ 8 } = 256$ berarti $6$
${ 2 }^{ 9 } = 512$ berarti $2$
${ 2 }^{ 10 } = 1024$ berarti $4$
wah ada polanya nih!
$2\quad4\quad8\quad6$
berarti selanjutnya.. $8,\; 6,\; 2,\; 4,\; 8!$"
"berarti $6,\; 2,\; 4,\; 8,\; 6$!"sip! kalo ${ 2 }^{1000}$?
"hah? banyak banget, nyerah deh -_-"yah, jangan nyerah dulu dong :( coba liat apa yang bikin 2 bilangan punya digit belakang yang sama.
"hmm... ${ 2 }^{ 1 }$, ${ 2 }^{ 5 }$, dan ${ 2 }^{ 9 }$ digit terakhirnya sama-sama $2$ karena... selisih $1,\; 5,\; 9$ itu $4$?"..... bener sih tapi kan $2,\; 6,\; 10$ selisihnya juga $4$ padahal digit terakhirnya $4$.
"oh iya... tapi kan mereka kalo dibagi $4$ mereka sisanya $2$, padahal $1,\; 5,\; 9$ kalo dibagi $4$ sisanya $1$"nah itu dia! kembali ke pertanyaan semula, berapa jawabannya kalo ${ 2 }^{1000}$?
"$1000$ dibagi $4$ tidak bersisa, berarti dia sama kayak 4 karena 4 juga gak bersisa kalo dibagi 4... berarti digit terakhir ${ 2 }^{1000}$ sama kayak digit terakhir ${ 2 }^{4} = 6$"akhirnya :') nah, sisa pembagian itulah yang kita sebut modulo. Dalam kasus ini, kita pake modulo 4 (karena dibagi dengan 4).
Akhirnya dari cerita panjang, aneh, dan tidak bermutu itu kita tahu bahwa modulo adalah sisa pembagian.
Note: jangan mulai mencari pola dari ${2}^{0}$ karena $0$ adalah angka spesial. Berapapun angkanya (selain 0, tidak dibahas disini) jika dipangkatkan $0$ akan menjadi $1$.
Oke, buat pemanasan kita coba dulu yang dasar
$32 \mod 7= 4$ (artinya 32 dibagi 7 bersisa 4)
$123 \mod 7= 4$ (artinya 123 dibagi 7 bersisa 4)
maka
$32 \equiv 123 \pmod 7$ (gaya penulisan yang lain, artinya 32 bersisa sama dengan 123 jika dibagi 7 (dalam contoh ini sisanya sama-sama 4). Perhatikan bahwa tanda tersebut bukan "sama dengan")
perhatikan juga bahwa
$32 \mod 7= 4$ bisa ditulis sebagai $32 \equiv 4 \pmod 7$
oke, sekarang gimana kalo $-123 \mod 7$?
"hmm... kan $123 \equiv 4 \pmod 7$, berarti $-123 \equiv -4 \pmod 7$ dong?"benar! kalo $-29 \mod 11$?
"karena 29 dibagi 11 sisa 7, berarti $-29 \equiv -7 \pmod {11}$ dong B-)"benar! kalo modulo positifnya gimana?
"hah positif? gak tau lah -_-"
oke, perhatikan kalo $-29 \equiv -18 \equiv -7\pmod {11}$ (ditambahin 11 terus)
Oh paham. Karena $-7 \equiv -7+11 \equiv 4 \pmod {11}$nah gitu dong
berarti $-29 \equiv -7 \equiv 4\pmod {11}$ dong!
"ez game! $-1234 \equiv -12 \equiv 1 \pmod {13}$!"Ampun lah mendewa m(_ _)m
Sekarang kita latihan dulu ya (arahkan mouse ke soal untuk lihat jawaban)
$38 \mod 7 = \dots$ 3
$98 \mod 13 = \dots$ 7
$-45 \mod 17 = \dots$ 6
$-192 \mod 11 = \dots$ 6
Sepertinya kamu sudah terbiasa menggunakan notasi modulo. sekarang kita bahas propertiesnya ya. jika
$a \equiv b \pmod x$ dan
$c \equiv d \pmod x$ maka
$a+b \equiv c+d \pmod x$
$a-b \equiv c-d \pmod x$
$a \times b \equiv c \times d \pmod x$
Gampang kan? intuitif lah, ga perlu dihafal :v biasanya sih yang kupake cuma yang perkalian, buat nyederhanain perhitungan.
note: pembagian pada modulo agak berbeda. Belum diperlukan untuk saat ini.
Setelah jago ngitung-ngitung mod, aku mau kasih sedikit intuisi apa itu modulo, siapa tau masih belum kebayang. Seperti cerita di awal, modulo itu seperti pengulangan, pola. Lebih lanjut, polanya itu membentuk baris aritmatika. Contoh
$\dots, 3, 8, 13, 18, 23, \dots$ hubungannya $3 \pmod {5}$
$\dots, -17, -10, -3, 4, 11, 18, \dots$ hubungannya $4 \pmod {7}$
dengan ngerti konsep ini, harusnya kamu bisa jawab soal di bawah
Contoh soal ya.
Budi hanya memiliki 3 baju (kasihan Budi :'( ). Masing-masing berwarna merah, kuning, dan hijau. Budi akan menggunakannya dengan urutan merah, kuning, hijau, merah, kuning, hijau, merah, dst. Jika hari ini Budi memakai baju kuning, baju warna apa yang akan digunakan Budi 7 tahun lagi? (anggap 1 tahun 365 hari)
Coba kerjakan dulu sebelum lihat solusi.
hijau, merah, kuning, hijau, merah, kuning, hijau, merah, dst.
perhatikan bahwa hijau dipakai 1 hari lagi.
pola berulang 3, maka kita akan hitung 7 tahun = 7*365 hari dalam $\mod 3$
maka jika hasilnya
$1 \mod 3$ bajunya hijau
$2 \mod 3$ bajunya merah
$0 \mod 3$ bajunya kuning
(kalo ga ngerti kenapa bisa begini, coba balik lagi ke atas, bagian intuisi)
$7 \times 365 \equiv 1 \times 2 \equiv 2 \pmod 3$ (perhatikan bahwa $7 \equiv 1 \pmod 3$ dan $365 \equiv 2 \pmod 3$)
maka 7 tahun lagi Budi memakai baju merah.
perhatikan bahwa hijau dipakai 1 hari lagi.
pola berulang 3, maka kita akan hitung 7 tahun = 7*365 hari dalam $\mod 3$
maka jika hasilnya
$1 \mod 3$ bajunya hijau
$2 \mod 3$ bajunya merah
$0 \mod 3$ bajunya kuning
(kalo ga ngerti kenapa bisa begini, coba balik lagi ke atas, bagian intuisi)
$7 \times 365 \equiv 1 \times 2 \equiv 2 \pmod 3$ (perhatikan bahwa $7 \equiv 1 \pmod 3$ dan $365 \equiv 2 \pmod 3$)
maka 7 tahun lagi Budi memakai baju merah.
Nah ada 1 lagi nih property yang cukup powerful!
${a}^{b} \equiv { \left( a \mod c \right) }^{ b } \pmod c$
Contoh ya
${12345}^{3} \equiv {3}^{3} \equiv 27 \equiv 5 \pmod {11}$ (perhatikan bahwa $12345 \mod 11 = 3$)
The proof is left to the reader as an exercise :p
gunakan segitiga pascal untuk perumuman. ambil contoh ${7}^{3} \equiv {\left( 6+1 \right) }^{3} \pmod {3}$. jabarkan.
perhatikan bahwa karena 6 habis dibagi 3, maka bilangan berapapun yang dikali 6 akan menjadi $0 \mod 3$.
gunakan property penjumlahan/pengurangan.
Soal kuy! (arahkan mouse ke soal untuk hint)
${12345}^{4} \mod 17 = \dots$
${ 2 }^{ 10 } \times { 3 }^{ 7 } \mod 11 = \dots$ hint: $12 \mod 11 = 1$
${43}^{12345} \mod 11 = \dots$ hint: gunakan mod negatif
Wah udah cukup panjang nih, lanjut di post berikutnya aja ya! See you later!
Referensi tambahan: cara mengerjakan soal-soal tentang modulo (dari grup OSN matematika, mungkin ada beberapa yang tidak masuk materi komputer tetapi tidak ada salahnya dipelajari :p)
