Struktrur Himpunan Bilangan Bulat Modulo n

Pada artikel mengenai Kongruensi Bilangan Bulat sudah dijelaskan bahwa konruensi memenuhi Sifat 1,2, dan 3 pada Teorema 4 pada artikel tersebut.

Misalkan diberikan bilangan asli n>1. Untuk setiap bilangan bulat $a$ didefinisikan

$K\left( a\right) =\left\{ x\in\mathbb{Z} |x\equiv a\mod n\right\}$

Sebagai contoh

$K\left( 0\right) =\left\{ x\in \mathbb{Z} |x\equiv 0\mod n\right\} =\left\{ x\in \mathbb{Z} |x=nk\right\} =\left\{ nk|k\in\mathbb{Z} \right\} =n\mathbb{Z},$

$K\left( 1\right) =\left\{ x\in \mathbb{Z} |x\equiv 1\mod n\right\} =\left\{ x\in \mathbb{Z}|x=nk+1\right\} =n\mathbb{Z}+1,$

$K\left( 2\right) =\left\{ x\in \mathbb{Z} |x\equiv 2\mod n\right\} =\left\{ x\in \mathbb{Z}|x=nk+2\right\} =n\mathbb{Z}+2,$

$\vdots$

$K\left( n-1\right) =\left\{ x\in \mathbb{Z} |x\equiv n-1\mod n\right\} =\left\{ x\in \mathbb{Z}|x=nk+(n-1)\right\} =n\mathbb{Z}+(n-1),$

$K\left( n\right) =\left\{ x\in \mathbb{Z} |x\equiv n\mod n\right\} =\left\{ x\in \mathbb{Z}|x=nk+n\right\} =n\mathbb{Z}.$

Perhatikan bahwa perhitungan di atas dilanjutkan maka akan didapat $K\left( 0\right) =K\left( n\right) =K\left( 2n\right) =...=K\left( mn\right)$ untuk sebarang bilangan bulat $m$ (termasuk untuk $m<0$ ). Hal yang sama untuk $K\left( r\right)$ dengan $1\leq r\leq n-1,$ kita juga akan punya $K\left( r\right) =K\left( n+r\right) =K\left( 2n+r\right) =...=K\left( mn+r\right) .$ Dengan demikian, setiap bilangan bulat masuk tepat ke dalam salah satu dari $K\left( r\right)$ untuk $0\leq r\leq n-1.$ Nah, $K\left( r\right)$ ini biasa dituliskan dengan $\protect\overset{\_}{r}$ dan $\left\{ \protect\overset{\_}{0},\protect\overset{\_}{1},...,\protect\overset{\_\_\_\_\_}{n-1}\right\}$ kita tuliskan sebagai $\mathbb{Z}_{n}$ yang disebut sebagai \textbf{sistem residu lengkap modulo } $n.$ Untuk mempermudah penulisan, pada pembahasan selanjutnya, tanda garis di atas akan kita hilangkan artinya yang dimaksud dengan $\mathbb{Z}_{n}=_{n}=\left\{ 0,1,2,...,n-1\right\}$ adalah sistem residu lengkap modulo $n$ .

Teorema 1

[box] Diberikan sebarang bilangan asli $n>1.$ Untuk sebarang bilangan bulat $a$ dan $b$ dengan $\left( a,n\right) =1$ berlaku $a\mathbb{Z}_{n}+b$ merupakan sistem residu lengkap modulo $n.$ [/box]

[learn_more caption=”Bukti:” state=”open”]

Sifat ini mengatakan bahwa $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b=% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}.$ Jelas bahwa $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b\subseteq %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n},$ sekarang akan dibuktikan $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b\supseteq %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}.$ Diambil sebarang $x\in %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}.$ Perhatikan bahwa persamaan $ay+b=x$ mempunyai solusi bulat (ingat
pada saat kita membahas Persamaan Diophantine). Dengan demikian $x\in a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b$ yang artinya $% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}\subseteq a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b.$ Terbukti bahwa $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b=% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}$ yang artinya bahwa $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}+b$ merupakan sistem lengkap modulo $n.$

[/learn_more]

Sekarang kita ambil subset dari $\mathbb{Z}_{n}$ yang relatif prima terhadap $n$ dan kita notasikan dengan $\mathbb{Z}_{n}^{\ast }.$ Dengan demikian $\mathbb{Z}_{n}^{\ast}=\left\{ x\in\mathbb{Z} _{n}|\left( x,m\right) =1\right\}.$ Tentu saja banyak anggota dari $\mathbb{Z}_{n}^{\ast }$ adalah $\protect\phi \left( n\right)$ dengan $\protect\phi % \left( n\right)$ ini adalah fungsi Euler-phi. Sama halnya di $\mathbb{Z}_{n},$ pada $\mathbb{Z}_{n}^{\ast }$ juga akan berlaku $a\mathbb{Z}_{n}^{\ast }=\mathbb{Z}_{n}^{\ast }$ untuk setiap bilangan bulat $a$ yang relatif prima terhadap $n$ (buktinya hampir sama dengan membuktikan $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion_{n}+b=% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}.$ Dari sini akan diperoleh teorema sebagai berikut.

Teorema 2 [Teorema Euler]

[box] Diberikan bilangan asli $n>1.$ Untuk setiap bilangan asli $a$ dengan sifat $% \left( a,n\right) =1$ berlaku $a^{\protect\phi \left( n\right) }\equiv 1%\mod n.$ [/box]

[learn_more caption=”Bukti:” state=”open”]

Telah dibuktikan di atas bahwa $a\mathbb{Z}_{n}^{\ast}=\mathbb{Z}_{n}^{\ast}$ .

Misalkan hasil kali semua elemen di $% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}^{\ast }$ adalah $M.$ Karena $% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}^{\ast }$ berisi bilangan-bilangan yang relatif prima dengan $n$ maka $M$
juga relatif prima dengan $n.$ Di lain pihak hasil kali semua elemen di $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}^{\ast }$ adalah $a^{\protect\phi \left( n\right) }M.$ Karena $a% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}^{\ast }=% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{n}^{\ast }$ maka $a^{\protect\phi \left( n\right) }M\equiv M\mod n,$
dan karena $\left( M,n\right) =1$ maka $a^{\protect\phi \left( n\right) }\equiv 1\mod n.$

[/learn_more]

Dalam hal $n$ merupakan bilangan prima, karena $\protect\phi \left( n\right) =n-1$ (untuk $n$ prima) maka $a^{n-1}\equiv 1\mod n.$ Hal ini
dijelaskan dengan akibat di bawah ini.

Teorema 3 [Teorema Fermat Kecil]

[box] Diberikan sebarang bilangan prima $p.$ Untuk setiap bilangan bulat $a$ berlaku $a^{p}\equiv a\mod p.$ [/box]

[learn_more caption=”Bukti:” state=”open”]

Jika $p|a$ maka pernyataan jelas benar. Jika $p\nmid a$ maka dengan menggunakan Teorema Euler diperoleh $a^{p-1}\equiv 1\mod p$ dan tentu
saja berakibat $a^{p}\equiv a\mod p$ .

[/learn_more]

Sekarang akan kita lihat beberapa soal yang menggunakan teorema di atas.

Contoh 4

Buktikan bahwa untuk setiap bilangan asli $n$ berlaku $n^{13}-n$ merupakan kelipatan $210.$

Pembahasan:

Perhatikan bahwa dengan Teorema Fermat kita punya $n^{13}=\left( n^{2}\right) ^{6}\equiv n^{6}=\left( n^{2}\right) ^{3}\equiv n^{3}\equiv n^{2}.n\equiv n.n\equiv n\mod 2,$

$n^{13}=\left( n^{3}\right) ^{4}n\equiv n^{4}.n=n^{3}.n^{2}\equiv n.n^{2}=n^{3}\equiv n\mod 3,$ $n^{13}=\left( n^{5}\right) ^{2}.n^{3}\equiv n^{2}.n^{3}=n^{5}\equiv n\mod 5$ dan
$n^{13}=n^{7}.n^{6}\equiv n.n^{6}=n^{7}\equiv n\mod 7.$ Dengan demikian $n^{13}-n$ kelipatan dari $2\times 3\times 5\times 7=210.$

Sekarang perhatikan bahwa pada saat kita membahas Persamaan Diophantine, kita tahu bahwa persamaan $ax+by=1$ mempunyai solusi bulat asalkan $\left( a,b\right) =1.$ Dengan mengganti $b$ dengan $n$ kita punya persamaan $% ax+bn=1\Leftrightarrow ax-1=bn$ dengan kata lain kita punya $ax\equiv 1\mod n.$ Jadi persamaan kongruensi ini akan punya solusi jika $\left( a,n\right) =1.$ Jika $n$ merupakan bilangan prima maka tentu $ax\equiv 1% \mod n$ ini akan punya solusi untuk setiap $a\in\mathbb{Z}_{p}^{\ast }.$

Lemma 5

[box] Diberikan bilangan prima $p.$ Untuk setiap $a\in %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{p}^{\ast }$ terdapat tepat satu $x\in %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{p}^{\ast }$ sehingga $ax\equiv 1\mod p.$ [/box]

[learn_more caption=”Bukti:” state=”open”]

Karena $\left( a,p\right) =1$ maka jelas bahwa terdapat $x$ sehingga $% ax\equiv 1\mod p.$ Sekarang tinggal dibuktikan ketunggalannya. Diambil
sebarang $x,y\in %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{p}^{\ast }$ sehingga $ax\equiv 1\mod p$ dan $ay\equiv 1\mod p.$
Dari sini diperoleh $ax\equiv ay\mod p$ dan karena $\left( a,p\right) =1$ maka $x\equiv y\mod p$ yang artinya $x$ dan $y$ sama dalam $% %TCIMACRO{\U{2124} }% %BeginExpansion \mathbb{Z} %EndExpansion _{p}^{\ast }.$

[/learn_more]

Dari Lemma 5 dapat diturunkan teorema sebagai berikut.

Teorema 6 [Teorema Wilson]

[box] Untuk sebarang bilangan prima $p$ berlaku $\left( p-1\right) !\equiv -1\mod p.$ [/box]

[learn_more caption=”Bukti:” state=”open”]

Untuk $p=2$ pernyataan jelas benar. Asumsikan $p>2.$ Perhatikan bahwa
persamaan $x^{2}\equiv 1\mod p$ hanya punya dua solusi yaitu $1$ dan $-1.$ Untuk anggota $\mathbb{Z}_{p}^{\ast }$ yang bukan $1$ atau $-1$ menurut Teorema 3 pada artikel Kongruensi Bilangan Bulat kita dapat memasangkannya dua-dua sehingga hasil kalinya kongruen dengan $1\mod p.$ Dengan demikian, jika semua elemen pada $\mathbb{Z}_{p}^{\ast }$ selain $-1$ dan $1$ dikalikan maka hasilnya akan kongruen $1\mod p$ sehingga hasil kali semua elemen di $\mathbb{Z}_{p}^{\ast }$ akan kongruen dengan $-1\mod p.$ Di lain pihak $\mathbb{Z}_{p}^{\ast }$ $=\left\{ 1,2,...,p-1\right\}$ sehingga hasil kali semua elemen di $\mathbb{Z}_{p}^{\ast }$ $\$ adalah $\left( p-1\right) !.$ Jadi $\left( p-1\right)!\equiv -1\mod p.$

[/learn_more]

Struktrur Himpunan Bilangan Bulat Modulo n

Published by nanang_susyanto on October 30, 2020October 30, 2020

0 Comments

Leave a Reply Cancel reply

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli

Struktrur Himpunan Bilangan Bulat Modulo n

Published by nanang_susyanto on October 30, 2020October 30, 2020

0 Comments

Leave a Reply Cancel reply

Related Posts

Relasi Urutan Pada Bilangan Bulat

Sistem Bilangan Bulat

Operasi Perkalian Pada Sistem Bilangan Asli