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]
[latexpage]
0 Comments