Panduan Pemula Belajar Aritmetika Modular

Banyak konsep aritmetika jam dapat digunakan untuk mengerjakan masalah-masalah yang berkenan dengan kalender.
Misalkan, hari senin pada bulan Juli 2018 jatuh pada tanggal 2, 9, 16, 23, dan 30. Selisih dari sebarang dua buah tanggal-tanggal tersebut mempunyai kelipatan 7. Tanggal 1 dan tanggal 29 jatuh pada hari yang sama karena $29-1=28$ dan 28 adalah juga kelipatan 7. Kita katakan bahwa 29 adalah kongruen 1 modulo 7 dan kita tulis $29 \equiv 1 (mod\ 7)$.
Hal yang sama untuk 18 dan 6, karena selisih 18 dan 6 adalah kelipatan 12, kita tulis $18 \equiv 6\ (mod\ 12)$.
Dari beberapa contoh sederhana diatas, membawa kita kepada defenisi berikut:
Defenisi:Untuk menambah pemahaman kita terhadap defenisi modulo diatas, kita coba diskusikan beberapa contoh berikut;
Misalkan $n$ adalah suatu bilangan bulat positif, $a$ dan $b$ adalah suatu bilangan bulat.
$a$ dikatakan kongruen $b$ modulo $n$, ditulis $a \equiv b\ (mod\ n)$ jika dan hanya jika $(a-b)$ adalah kelipatan $n$.
Contoh 1:
Periksa kebenaran pernyataan berikut ini:
(a) $3 \equiv 24\ (mod\ 7)$
Show
$3 \equiv 24\ (mod\ 7)$
Benar, karena $3 – 24 = -21$ kelipatan dari $7$
Show
$-31 \equiv 11\ (mod\ 7)$
Benar, karena $–31 – 11 = -42$ kelipatan dari $7$
Show
$-15 \equiv -64\ (mod\ 7)$
Benar, karena $–15 + 64 = 49$ kelipatan dari $7$
Show
$13 \equiv -1\ (mod\ 7)$
Benar, karena $13 + 1 = 14$ kelipatan dari $7$
Show
$23 \equiv 3\ (mod\ 7)$
Salah, karena $23 – 3 = 20$ bukan kelipatan dari $7$
Contoh 2:
Tentukan semua bilangan bulat $x$ sedemikian sehingga $x \equiv 1\, (mod\ 10) $
Show
$x \equiv 1\ (mod\ 10)$ jika dan hanya jika $x-1=10k$ Untuk setiap $k$ bilangan bulat.
Jika $k = 0, 1, 2, 3, …$ maka berturut-turut $x = 1, 11, 21, 31, ...$
Begitu pula $k = -0, -1, -2, -3,...$ maka berturut-turut $x = -9, -200, 21, 31,...$
Begitu pula $k = -1, -2, -3,...$ maka berturut-turut $x = -9, -19, -29,...$
Dua barisan tersebut digabungkan sehingga himpunan penyelesaian $x \equiv 1\ (mod\ 10)$ adalah
$..., -29, -19, -9, 1, 11, 21, 31,...$
Sifat 1
Misalkan $n$ suatu bilangan bulat positif dan $a, b, c,$ dan $d$ bilangan bulat sebarang berlaku:(1) $a \equiv a\ (mod\ n)$
Show
Untuk $a$ bilangan bulat sebarang dan $n$ suatu bilangan bulat positif berlaku $a – a = 0 \cdot n $.
Dengan demikian $a \equiv a\ (mod\ n)$.
Show
$a \equiv b\ (mod\ n)$
Ada $k$ suatu bilangan bulat.
Akibatnya
$b-a=-(a-b)$
$b-a=-(kn)$
$b-a=(-k)n$
Karena $-k$ juga suatu bilangan bulat, $b \equiv a\ (mod\ n)$.
Show
$a \equiv b\ (mod\ n)$ dan $b \equiv c\ (mod\ n)$
Ada $h$ dan $k$ suatu bilangan bulat sehingga $a-b=hn$ dan $b-c=kn$.
Akibatnya:
$a-c=(a-b)+(b-c)$
$a-c=hn+kn$
$a-c=n(h+k)$
Karena $h+k$ juga bilangan, $a \equiv c\ (mod\ n)$.
Show
$a \equiv b\ (mod\ n)$ dan $c \equiv d\ (mod\ n)$
Ada $h$ dan $k$ bilangan bulat sehingga $a-b=hn$ dan $b-c=kn$.
$(a+c)-(b+d)=(a-b)+(c-d)$
$(a+c)-(b+d)=hn+kn$
$(a+c)-(b+d)=n(h+k)$
Karena $h+k$ juga bilangan bulat, $a+c \equiv b+d\ (mod\ n)$.
Show
$a \equiv b\ (mod\ n)$ dan $c \equiv d\ (mod\ n)$
Pandang
$ac=(b+hn)(d+kn)$
$ac=bd+(bk+dh+hkn)n$
Karena $(bk+dh+hkn)$ bilangan bulat,
Ada $h$ dan $k$ bilangan bulat, $ac \equiv bd\ (mod\ n)$.
Show
$a \equiv b\ (mod\ n)$
Ada $h$ bilangan sehingga $a-b=hn$
Karena $(a+c)-(b+c)=a-b=hn$
dengan demikian $a+c \equiv b+c\ (mod\ n)$.
Show
$a \equiv b\ (mod\ n)$
Ada $h$ bilangan bulat sehingga $a – b = hn $.
$ac-bc=(a-b)c=hnc=(hc)n$
Karena $hc$ bilangan bulat,
dengan demikian $ac \equiv bc\ (mod\ n)$.
Show
Untuk bukti ini ita gunakan Induksi Matematika.
Untuk $k=1$, berlaku $a \equiv a\ (mod\ n)$.
Kita asumsikan $a^k \equiv b^k\ (mod\ n)$ berlaku,
Akan ditunjukkan $a^{k+1} \equiv b^{k+1}\ (mod\ n)$ juga berlaku.
Dari sifat (5), jika $a \equiv b\ (mod\ n)$ dan $c \equiv d\ (mod\ n)$ maka $ac \equiv bd\ (mod\ n)$
kita ganti $c$ oleh $a^k$ dan $d$ oleh $b^k$ diperoleh;
$aa^k \equiv bb^k (mod\ n)$ atau $a^{k+1} \equiv b^{k+1} (mod\ n)$
Contoh 3:
Tentukan sisanya jika $3^{100}$ dibagi oleh $5$.
Show
Tampaknya kalkulator tidak dapat digunakan untuk menemukan jawaban atas masalah yang diajukan. Untuk itu kita gunakan cara lain untuk menyelesaikan masalah ini.
Kita tahu bahwa suatu bilangan bulat positif dibagi oleh 5 mempunyai sisa 0, 1, 2, 3, atau 4.
Penggunaan aritmetika modular akan membantu kita jika kita dapat menemukan bilangan bulat terkecil yang ekuivalen dengan pangkat dari 3, dan penggunaan sifat (7) dan (8) untuk membangun $3^{100}$ dan menemukan ekuivalensi mod 5.
Kita tahu bahwa $3^{2} \equiv 4\ (mod\ 5)$
Dengan demikian,
$3^3 \equiv 3 \cdot 4 \equiv 2\ (mod\ 5)$
$3^4 \equiv 3 \cdot 2 \equiv 1\ (mod\ 5)$
Dengan menggunakan sifat (8) kita peroleh,
$(3^4)^{25} \equiv 1^{25} (mod\ 5)$, atau
$3^{100} \equiv 1 (mod\ 5)$
Jadi: $3^{100}$ dibagi oleh $5$ mempunyai sisa $1$.
Sifat 2
Jika $ca \equiv cb\ (mod\ n)$ maka $a \equiv b\ (mod\ n/d )$ dimana $d = FPB(c , n)$.Show
Karena $ca \equiv cb\ (mod\ n)$,
$c(a – b) = ca – cb = kn$ untuk suatu bilangan bulat $k$.
Kita tahu bahwa $d = FPB(c , n)$, dengan demikian, ada bilangan bulat saling prima (relative prime) $r$ dan $s$ yang memenuhi $c = dr$, $n = ds$.
Jika hasil ini kita substitusikan ke persamaan $c(a – b) = ca – cb = kn$ maka kita peroleh $r(a – b) = ks$.
Hasil ini menunjukkan $s \mid r(a – b)$, dan karena $FPB (r , s) = 1$, diperoleh $s (a – b)$. Dengan kata lain,
$ca \equiv cb\ (mod\ n)$ maka $a \equiv b\ (mod\ n/d )$
Sifat 3
Jika $ca \equiv cb\ (mod\ n)$ dan $FPB(c , n) = 1$ maka $a \equiv b\ (mod\ n)$.Sifat 3 ini hanya merupakan kasus khusus dari sifat 2
Sifat 4
Jika $ca \equiv cb\ (mod\ p)$ dan $p \nmid c$, dimana $p$ adalah bilangan prima maka $a \equiv b\ (mod\ p)$.Show
Kondisi $p \nmid c$ dan $p$ adalah bilangan prima ini mengakibatkan $FPB\ (c,p)=1$
- Perhatikan $33 \equiv 15\ (mod\ 9)$, atau $3 \cdot 11 \equiv 3 \cdot 5\ (mod\ 9)$.
Karena $FPB(3,9)=1$ mengakibatkan $11 \equiv 5\ (mod\ 9)$ - Perhatikan $-35 \equiv 45\ (mod\ 8)$, atau $5 \cdot (-7) \equiv 5 \cdot 9\ (mod\ 8)$.
Karena $5$ dan $8$ bilangan bulat saling prima mengakibatkan $-7 \equiv 9\ (mod\ 8)$
Diskusi sederhana tentang aritmetika modular diatas mudah-mudahan menambah pemahaman kita tentang bilangan modular. Jika ingin mendapatkan file diskusi diatas dalam ekstensi .pdf silahakn di download pada link dibawah ini.
File ini juga menjadi sumber tulisan ini, silahkan Download File.
Untuk segala sesuatu hal yang perlu kita diskusikan terkait Panduan Pemula Belajar Aritmetika Modular silahkan disampaikan 🙏 CMIIW😊.
Jangan Lupa Untuk Berbagi 🙏 Share is Caring 👀 dan JADIKAN HARI INI LUAR BIASA! - WITH GOD ALL THINGS ARE POSSIBLE😊
Video pilihan khusus untuk Anda 😊 Cara Alternatif dalam Perkalian Dua Angka, sangat kreatif;
