Belajar Aritmetika Modular

Diskusi Aritmetika Modular ini merupakan diskusi tambahan setelah sebelumnya kita telah diskusikan tentang belajar modulo dengan cara sederhana atau belajar matematika di Hari Paskah. Karena dari kedua diskusi sebelumnya, konsep yang digunakan masih sama yaitu 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 juga 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:
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$.
Untuk menambah pemahaman kita terhadap defenisi modulo diatas, kita coba diskusikan beberapa contoh berikut;

Contoh 1:
Periksa kebenaran pernyataan berikut ini:
[a] $3 \equiv 24\ (mod\ 7)$
Alternatif Pembahasan:

Hint

$3 \equiv 24\ (mod\ 7)$
Benar, karena $3 – 24 = -21$ kelipatan dari $7$


[b] $-31 \equiv 11\ (mod\ 7)$
Alternatif Pembahasan:

Hint

$-31 \equiv 11\ (mod\ 7)$
Benar, karena $–31 – 11 = -42$ kelipatan dari $7$


[c] $-15 \equiv -64\ (mod\ 7)$
Alternatif Pembahasan:

Hint

$-15 \equiv -64\ (mod\ 7)$
Benar, karena $–15 + 64 = 49$ kelipatan dari $7$


[d] $13 \equiv -1\ (mod\ 7)$
Alternatif Pembahasan:

Hint

$13 \equiv -1\ (mod\ 7)$
Benar, karena $13 + 1 = 14$ kelipatan dari $7$


[e] $23 \equiv 3\ (mod\ 7)$
Alternatif Pembahasan:

Hint

$23 \equiv 3\ (mod\ 7)$
Salah, karena $23 – 3 = 20$ bukan kelipatan dari $7$


Jika $(a – b)$ bukan kelipatan dari $n$, atau ditulis $n \nmid (a – b)$, maka kita katakan bahwa $a$ tidak kongruen $b$ modulo $n$ dan ditulis $a \not\equiv b (mod\ n)$. Sebagai contoh, $23 \not\equiv 3\ (mod\ 7)$

Contoh 2:
Tentukan semua bilangan bulat $x$ sedemikian sehingga $x \equiv 1\, (mod\ 10) $
Alternatif Pembahasan:

Hint

$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,...$


Pada contoh 2 di atas, tampak bahwa setiap elemen pada ${1, 11, 21, 31, ...}$ mempunyai sisa 1 jika dibagi oleh 10. Secara umum dapat dikatakan bahwa dua buah bilangan cacah adalah kongruen modulo $n$ jika dan hanya jika sisanya pada pembagian oleh $m$ adalah sama.

Sifat 1

Misalkan $n$ suatu bilangan bulat positif dan $a, b, c,$ dan $d$ bilangan bulat sebarang berlaku:

[1] $a \equiv a\ (mod\ n)$
Alternatif Pembuktian:

Hint

Untuk $a$ bilangan bulat sebarang dan $n$ suatu bilangan bulat positif berlaku $a – a = 0 \cdot n $.
Dengan demikian $a \equiv a\ (mod\ n)$.


[2] Jika $a \equiv b\ (mod\ n)$ maka $b \equiv a\ (mod\ n)$
Alternatif Pembuktian:

Hint

$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)$.


[3] Jika $a \equiv b\ (mod\ n)$ dan $b \equiv c\ (mod\ n)$ maka $a \equiv c\ (mod\ n)$
Alternatif Pembuktian:

Hint

$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)$.


[4] Jika $a \equiv b\ (mod\ n)$ dan $c \equiv d\ (mod\ n)$ maka $a+c \equiv b+d\ (mod\ n)$
Alternatif Pembuktian:

Hint

$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)$.


[5] Jika $a \equiv b\ (mod\ n)$ dan $c \equiv d\ (mod\ n)$ maka $ac \equiv bd\ (mod\ n)$
Alternatif Pembuktian:

Hint

$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)$.


[6] Jika $a \equiv b\ (mod\ n)$ maka $a+c \equiv b+c\ (mod\ n)$
Alternatif Pembuktian:

Hint

$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)$.



[7] Jika $a \equiv b\ (mod\ n)$ maka $ac \equiv bc\ (mod\ n)$
Alternatif Pembuktian:

Hint

$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)$.



[8] Jika $a \equiv b\ (mod\ n)$ maka $a^k \equiv b^k\ (mod\ n)$ untuk $k$ bilangan bulat positif sebarang.
Alternatif Pembuktian:

Hint

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$.
Alternatif Pembahasan:

Hint

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)$.
Alternatif Pembuktian:

Hint

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)$.
Alternatif Pembuktian:

Hint

Kondisi $p \nmid c$ dan $p$ adalah bilangan prima ini mengakibatkan $FPB\ (c,p)=1$


Contoh 4:
  • 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 dimari. Jika ada yang ingin kita diskusikan mari disampaikan, mari bermatematik๐Ÿ˜Š๐Ÿ˜Š

Video pilihan khusus untuk Anda ๐Ÿ˜Š Bagaimana perkalian dikerjakan dengan cara nakal, mari kita lihat perkalian yang kreatif;

You Might Also Like: