2 Kongruensi

Bukti.  

1. Jika $a \equiv b\pmod n$, maka $n\mid (a-b)$. Jadi terdapat $k\in{\mathbb Z}$ sedemikian sehingga $a-b=kn$. Hal ini mengakibatkan $b-a=(-k)n$, sehingga $n\mid (b-a)$. Dengan demikian, $b\equiv a\pmod n$.

2. Karena $a\equiv b\pmod n$ dan $b\equiv c\pmod n$, berlaku $n\mid (a-b)$ dan $n\mid (b-c)$. Oleh karena itu, terdapat $k,l\in{\mathbb Z}$ sedemikian sehingga $a=b+kn$ dan $b=c+ln$. Akibatnya, $a=c+(k+l)n$. Dengan kata lain, $a\equiv c\pmod n$.

3. Karena $a\equiv b\pmod n$, berlaku $n \mid (a-b)$. Dengan menambahkan dan mengurangkan $c$, kita memperoleh $$\begin{equation*} n\mid ((a+c)-(b+c)) \end{equation*}$$ yang berarti bahwa $$\begin{equation*} a+c\equiv b+c\pmod n. \end{equation*}$$

4. Karena $a\equiv b\pmod n$, berlaku $n \mid (a-b)$. Dengan mengurangkan dan menambahkan $c$, kita memperoleh $$\begin{equation*} n\mid ((a-c)-(b-c)) \end{equation*}$$ sehingga $$\begin{equation*} a-c\equiv b-c\pmod n. \end{equation*}$$

5. Jika $a \equiv b\pmod n$, maka $n\mid (a-b)$. Jadi terdapat $k\in{\mathbb Z}$ sedemikian sehingga $a-b=kn$, dan akibatnya $ac-bc=(kc)n$. Oleh karena itu, $$\begin{equation*} n\mid (ac-bc) \end{equation*}$$ dan dengan demikian $$\begin{equation*} ac\equiv bc\pmod n. \end{equation*}$$

6. Jika $a \equiv b\pmod n$, maka $n\mid (a-b)$. Jadi terdapat $k\in{\mathbb Z}$ sedemikian sehingga $a-b=kn$, dan akibatnya $$\begin{equation*} ac-bc=kcn. \end{equation*}$$ Jadi, $$\begin{equation*} nc\mid (ac-bc) \end{equation*}$$ dan dengan demikian $$\begin{equation*} ac\equiv bc\pmod{nc}. \end{equation*}$$

7. Karena $a\equiv b\pmod n$ dan $c\equiv d\pmod n$, berlaku $n\mid (a-b)$ dan $n\mid (c-d)$. Oleh karena itu, terdapat $k,l\in{\mathbb Z}$ sedemikian sehingga $a-b=kn$ dan $c-d=ln$. Perhatikan bahwa $$\begin{equation*} (a-b)+(c-d)=(a+c)-(b+d)=(k+l)n. \end{equation*}$$ Akibatnya, $$\begin{equation*} n\mid ((a+c)-(b+d)), \end{equation*}$$ sehingga $$\begin{equation*} a+c\equiv b+d\pmod n. \end{equation*}$$

8. Jika $a=b+kn$ dan $c=d+ln$ untuk $k,l\in{\mathbb Z}$, maka $$\begin{equation*} (a-b)-(c-d)=(a-c)-(b-d)=(k-l)n. \end{equation*}$$ Akibatnya, $$\begin{equation*} n\mid ((a-c)-(b-d)), \end{equation*}$$ sehingga $$\begin{equation*} a-c\equiv b-d\pmod n. \end{equation*}$$

9. Terdapat $k,l\in{\mathbb Z}$ sedemikian sehingga $a-b=kn$ dan $c-d=ln$. Dengan demikian, $ca-cb=(ck)n$ dan $bc-bd=(bl)n$. Perhatikan bahwa $$\begin{equation*} (ca-cb)+(bc-bd)=ac-bd=(ck+bl)n. \end{equation*}$$ Akibatnya, $$\begin{equation*} n\mid (ac-bd), \end{equation*}$$ sehingga $$\begin{equation*} ac\equiv bd\pmod n. \end{equation*}$$

 ◻

Bukti. Berdasarkan Akibat 1.30, terdapat $m,n\in{\mathbb Z}$ sedemikian sehingga $ma+nb=1$. Dari hipotesis keterbagian, terdapat pula $p,q\in{\mathbb Z}$ sedemikian sehingga $c=pa$ dan $c=qb$. Kita hitung: $$\begin{equation*} c=c\cdot1=c(ma+nb)=mca+ncb=mqba+npab=(mq+np)ab\ . \end{equation*}$$ Ini berarti $ab\mid c$, seperti yang diinginkan. ◻

Bukti. Dari Akibat 1.30, terdapat $m,n\in{\mathbb Z}$ sedemikian sehingga $mx+ny=1$. Dengan mengalikan kedua ruas dengan $z$, kita memperoleh $mxz+nyz=z$. Namun, berdasarkan asumsi $x\mid yz$, berlaku $x\mid nyz$; jelas pula bahwa $x\mid mxz$. Jadi $x\mid mxz+nyz$, yakni $x\mid z$. ◻

Bukti. Untuk Bagian 1, jika $ab\equiv ac\pmod n$, maka $$\begin{equation*} n\mid (ab-ac)=a(b-c). \end{equation*}$$ Jadi terdapat $k\in{\mathbb Z}$ sedemikian sehingga $a(b-c)=kn$. Dengan membagi kedua ruas dengan $d$, kita memperoleh $(a/d)(b-c)=k(n/d)$, atau $(n/d)\mid (a/d)(b-c)$. Berdasarkan Teorema 1.26, $\gcd(a/d,n/d)=1$. Karena itu, Lemma Euklides 2.6 menyatakan bahwa $(n/d) \mid (b-c)$. Dengan demikian, $b\equiv c\pmod{n/d}$.

Untuk Bagian 2, arah ${}\Rightarrow{}$ merupakan Bagian 5 dari Teorema 2.3, sedangkan arah ${}\Leftarrow{}$ merupakan kasus khusus dari Bagian 1. ◻

Bukti. Misalkan $x_j=j(n/d)$ untuk $j=0,\dots,(d-1)$. Jelas bahwa masing-masing dari $d$ nilai $x_j$ ini merupakan kelipatan $n/d$, sehingga memenuhi $x\equiv 0\pmod{n/d}$. Jadi, kita hanya perlu menunjukkan bahwa setiap solusi $x$ dari $x\equiv 0\pmod{n/d}$ kongruen modulo $n$ dengan salah satu $x_j$ tersebut.

Misalkan $x$ adalah solusi semacam itu. Maka terdapat $k\in{\mathbb Z}$ sedemikian sehingga $x=k(n/d)$. Terapkan Algoritma Pembagian untuk membagi $x$ dengan $n$, sehingga $x=qn+r$ untuk suatu $q,r\in{\mathbb Z}$ dengan $0\le r<n$. Namun, $$\begin{equation*} r=x-qn=k(n/d)-qd(n/d)=(k-qd)(n/d) \end{equation*}$$ sehingga $r$ merupakan kelipatan $(n/d)$ yang terletak dalam rentang $[0,n)$. Kelipatan-kelipatan semacam itu hanyalah $x_0,\dots,x_{(d-1)}$ yang didefinisikan di atas; misalkan $r=x_j$. Maka $x=qn+r=qn+x_j\equiv x_j\pmod n$. Dengan demikian, setiap solusi $x$ kongruen modulo $n$ dengan tepat satu dari $d$ solusi khusus $x_0,\dots,x_{(d-1)}$. ◻

Bukti. Untuk Bagian 1, kita membuktikan kontraposisinya. Andaikan kongruensi tersebut memiliki solusi. Artinya, terdapat $x,k\in{\mathbb Z}$ sedemikian sehingga $ax-b=kn$, atau $ax-kn=b$. Karena $d=\gcd(a,n)$ merupakan pembagi bersama $a$ dan $n$, bilangan $d$ membagi kombinasi linear $ax-kn=b$. Jadi $d\mid b$.

Untuk Bagian 2, andaikan $d\mid b$, sehingga terdapat $k\in{\mathbb Z}$ sedemikian sehingga $kd=b$. Dari Teorema 1.29, terdapat $p,q\in{\mathbb Z}$ sedemikian sehingga $d=pa+qn$. Ini berarti $kpa+kqn=kd=b$, atau setelah disusun ulang, $a(kp)-b=(-kq)n$. Jadi $n\mid(a(kp)-b)$, yakni $a(kp)\equiv b\pmod n$. Dengan demikian, $x=kp$ merupakan salah satu solusi kongruensi linear $ax\equiv b\pmod n$.

Terakhir, mari kita buktikan banyaknya solusi modulo $n$. Kita baru saja melihat bahwa terdapat setidaknya satu $x\in{\mathbb Z}$ yang memenuhi $ax\equiv b\pmod n$. Misalkan $y\in{\mathbb Z}$ adalah solusi lain. Maka $ax\equiv b\equiv ay\pmod n$. Berdasarkan Bagian 1 dari Teorema 2.7, berlaku $x\equiv y\pmod{n/d}$, atau $\delta=y-x\equiv0\pmod{n/d}$. Menurut Teorema 2.9, terdapat tepat $d$ kemungkinan untuk $\delta$ modulo $n$. Karena itu, terdapat paling banyak $d$ kelas solusi.

Sebaliknya, ambil salah satu dari $d$ kelas $\delta$ modulo $n$ yang memenuhi $\delta\equiv0\pmod{n/d}$, lalu pilih sebuah wakil yang juga kita namai $\delta$. Terdapat $t\in{\mathbb Z}$ sedemikian sehingga $\delta=t(n/d)$. Karena $d\mid a$, terdapat $a^\prime\in{\mathbb Z}$ dengan $a=da^\prime$, sehingga $a\delta=a^\prime tn$ dan $n\mid a\delta$. Oleh sebab itu, $a(x+\delta)\equiv ax\equiv b\pmod n$. Penambahan oleh $x$ mempertahankan perbedaan kelas modulo $n$, sehingga setiap kelas $\delta$ tersebut menghasilkan kelas solusi yang berbeda. Jadi kongruensi ini memiliki tepat $d$ solusi yang berbeda modulo $n$. ◻

Bukti. Untuk $j=1,\dots,k$, misalkan $N_j=N/n_j$. Karena modulus-modulus $n_j$ relatif prima berpasangan, $\gcd(N_j,n_j)=1$ — sebab $N_j$ merupakan hasil kali semua modulus selain $n_j$. Berdasarkan Akibat 2.17, terdapat invers $y_j=N_j^{-1}$ modulo $n_j$ yang memenuhi $N_jy_j\equiv 1\pmod{n_j}$. Sekarang, tinjau $$\begin{equation*} x=\sum_{j=1}^k b_j N_j y_j \end{equation*}$$ Karena $$\begin{equation*} N_j\equiv 0\pmod{n_i} \ \ \forall i\neq j, \end{equation*}$$ kita memperoleh $$\begin{equation*} x\equiv b_j N_j y_j\equiv b_j\pmod{n_j}. \end{equation*}$$ Jadi, $x$ merupakan solusi sistem kongruensi tersebut.

Sekarang kita perlu menunjukkan bahwa setiap dua solusi kongruen modulo $N$. Misalkan $x$ dan $y$ keduanya merupakan solusi sistem kongruensi tersebut. Maka $x\equiv b_j\equiv y\pmod{n_j}$, atau $n_j\mid x-y$, untuk setiap $1\leq j\leq k$. Karena modulus-modulus itu relatif prima berpasangan, dengan menerapkan Teorema 2.4 berulang kali (secara formal, melalui induksi), kita menyimpulkan bahwa $N=n_1\dots n_k\mid x-y$, atau $x\equiv y\pmod N$. ◻

Bukti. (1): Pernyataan ini tidak lain adalah sifat refleksif dari ${}\cong{}$.

(2): Misalkan $z\in[x]\cap[y]$. Ini berarti $z\cong x$ dan $z\cong y$. Berdasarkan simetri, $x\cong z$; berdasarkan transitivitas, $x\cong y$.

Sekarang, jika $a\in[x]$ dan $b\in[y]$, maka $a\cong x$ dan $b\cong y$. Karena $x\cong y$, transitivitas memberi $a\cong y$, sehingga $a\in[y]$. Selain itu, simetri memberi $y\cong x$, lalu transitivitas memberi $b\cong x$, sehingga $b\in[x]$.

Oleh karena itu, $[x]\subseteq[y]$ dan $[y]\subseteq[x]$, sehingga $[x]=[y]$.

Argumen tersebut hanya menggunakan adanya suatu elemen $z\in[x]\cap[y]$. Jadi, jika $[x]\neq[y]$, haruslah $[x]\cap[y]=\emptyset$. Kedua kemungkinan itu tidak dapat berlaku sekaligus, sebab Bagian (1) menunjukkan bahwa setiap kelas ekuivalensi tidak kosong. ◻

Bukti. Untuk $n\in{\mathbb N}$ dan $a\in{\mathbb Z}$, Algoritma Pembagian menyatakan bahwa terdapat pasangan tunggal $q,r\in{\mathbb Z}$ sedemikian sehingga $a=qn+r$ dan $0\le r<n$. Perhatikan bahwa $a\equiv r\pmod{n}$ atau, secara ekuivalen, $a\in[r]$. Jadi, setiap $a\in{\mathbb Z}$ merupakan anggota tepat satu kelas ekuivalensi $[r]$ untuk $r\in\{0,\dots,n-1\}$. Karena setiap $r$ tersebut berada dalam $[r]$, dan hanya dalam satu kelas semacam itu, kelas-kelas ekuivalensi $[0],\dots,[n-1]$ semuanya berbeda. ◻

Bukti. Misalkan $n\in{\mathbb N}$ dan ${\mathcal C},{\mathcal D}\in{\mathbb Z}/n{\mathbb Z}$. Ambil $a,p,b,q\in{\mathbb Z}$ sedemikian sehingga ${\mathcal C}=[a]=[p]$ dan ${\mathcal D}=[b]=[q]$. Maka $p\equiv a\pmod{n}$ dan $q\equiv b\pmod{n}$. Berdasarkan Teorema 2.3, $a+b\equiv p+q\pmod{n}$ dan $a\cdot b\equiv p\cdot q\pmod{n}$, sehingga $[a+b]=[p+q]$ dan $[a\cdot b]=[p\cdot q]$. Jadi, baik $[a+b]$ maupun $[p+q]$ memberikan definisi yang sama bagi ${\mathcal C}+{\mathcal D}$, dan hal yang sama berlaku untuk ${\mathcal C}\cdot{\mathcal D}$. ◻

Bukti. Diserahkan kepada pembaca. Perhatikan bahwa butir terakhir pada dasarnya merupakan Akibat 2.17 yang dinyatakan kembali dalam bahasa kelas kongruensi. ◻

Bukti. Diserahkan kepada pembaca; pernyataan ini tidak lain adalah Teorema 2.13 dalam bentuk lain. ◻

Bukti. Pernyataan ini langsung mengikuti Bagian (5) dari Teorema 2.29. ◻

Bukti. Pernyataan ini merupakan penerapan Teorema Sisa Cina yang menarik, seperti yang akan kita lihat.

Tetapkan $n,m\in{\mathbb N}$ yang relatif prima. Untuk $k\in{\mathbb N}$, misalkan $$({\mathbb Z}/k{\mathbb Z})^*=\{x\in{\mathbb Z}/k{\mathbb Z}\mid x\text{ mempunyai invers multiplikatif}\}$$ sehingga $\phi(k)=\#(({\mathbb Z}/k{\mathbb Z})^*)$.

(Notasi ini menyatakan banyaknya elemen dalam himpunan $({\mathbb Z}/k{\mathbb Z})^*$.)

Sekarang, definisikan himpunan pasangan $$({\mathbb Z}/n{\mathbb Z})^*\times({\mathbb Z}/m{\mathbb Z})^*=\{(a,b)\mid a\in({\mathbb Z}/n{\mathbb Z})^*\text{\ dan\ }b\in({\mathbb Z}/m{\mathbb Z})^*\}\ .$$ Perhatikan bahwa $\#(({\mathbb Z}/n{\mathbb Z})^*\times({\mathbb Z}/m{\mathbb Z})^*)= \#(({\mathbb Z}/n{\mathbb Z})^*)\cdot\#(({\mathbb Z}/m{\mathbb Z})^*)=\phi(n)\phi(m)$ , sebab setiap komponen pasangan dapat dipilih bebas dari himpunannya masing-masing. Jadi, banyaknya pasangan adalah hasil kali ukuran kedua himpunan. Oleh karena itu, jika kita dapat membuktikan bahwa $({\mathbb Z}/n{\mathbb Z})^*\times({\mathbb Z}/m{\mathbb Z})^*$ berkorespondensi secara bijektif dengan $({\mathbb Z}/(nm){\mathbb Z})^*$, maka

$$\phi(n)\phi(m)=\#\left(({\mathbb Z}/n{\mathbb Z})^*\times({\mathbb Z}/m{\mathbb Z})^*\right)=\#(({\mathbb Z}/(nm){\mathbb Z})^*)=\phi(nm)$$ seperti yang diinginkan, sebab himpunan-himpunan yang berkorespondensi secara bijektif mempunyai jumlah elemen yang sama.

Korespondensi tersebut diberikan oleh fungsi $${\mathcal F}:({\mathbb Z}/(nm){\mathbb Z})^*\to({\mathbb Z}/n{\mathbb Z})^*\times({\mathbb Z}/m{\mathbb Z})^*:[x]_{nm}\mapsto([x]_n,[x]_m)\ .$$

Kita harus menunjukkan bahwa ${\mathcal F}$ terdefinisi dengan baik, injektif, dan surjektif. Pertama, ${\mathcal F}$ memang memetakan ke kodomain yang dinyatakan. Jika $[x]_{nm}$ mempunyai invers $[u]_{nm}$, maka $xu\equiv1\pmod{nm}$, sehingga $xu\equiv1\pmod n$ dan $xu\equiv1\pmod m$. Jadi, $[x]_n$ dan $[x]_m$ keduanya mempunyai invers multiplikatif.

Selanjutnya, keterdefinisian dengan baik berarti bahwa, untuk suatu $[x]_{nm}$, jika $y\in{\mathbb Z}$ merupakan wakil lain dari kelas kongruensi $[x]_{nm}$, maka $([x]_n,[x]_m)=([y]_n,[y]_m)$. Dengan demikian, ${\mathcal F}$ ditentukan hanya oleh kelas $[x]_{nm}$, bukan oleh pilihan wakil $x$. Hal ini mudah dilihat: $y\in[x]_{nm}$ berarti $y\cong_{nm}x$, sehingga terdapat $k\in{\mathbb Z}$ sedemikian sehingga $y-x=k(nm)=(km)n=(kn)m$. Dua bentuk terakhir berarti $y\cong_nx$ dan $y\cong_mx$, sehingga $[x]_n=[y]_n$ dan $[x]_m=[y]_m$. Jadi, ${\mathcal F}$ terdefinisi dengan baik.

Sekarang, misalkan $x,y\in{\mathbb Z}$ memenuhi ${\mathcal F}([x]_{nm})={\mathcal F}([y]_{nm})$, yaitu $[x]_n=[y]_n$ dan $[x]_m=[y]_m$. Dengan demikian, $z=x-y\in{\mathbb Z}$ menyelesaikan sistem $$\begin{align*} z&\equiv 0\pmod{n}\\ z&\equiv 0\pmod{m}\ . \end{align*}$$ Nilai $z=0$ juga menyelesaikan sistem ini. Teorema Sisa Cina menyatakan bahwa solusi sistem tersebut tunggal modulo $nm$ karena $\gcd(n,m)=1$.

Oleh karena itu, $x-y\equiv0\pmod{nm}$, sehingga $x\equiv y\pmod{nm}$. Jadi, $[x]_{nm}=[y]_{nm}$ dan ${\mathcal F}$ injektif.

Terakhir, ambil sebarang pasangan $([x]_n,[y]_m)\in({\mathbb Z}/n{\mathbb Z})^*\times({\mathbb Z}/m{\mathbb Z})^*$ dan tinjau sistem $$\begin{align*} z&\equiv x\pmod{n}\\ z&\equiv y\pmod{m}\ , \end{align*}$$ Karena $\gcd(n,m)=1$, Teorema Sisa Cina memberikan suatu solusi $z\in{\mathbb Z}$.

Masih perlu ditunjukkan bahwa $[z]_{nm}$ mempunyai invers. Ambil $[u]_n=[x]_n^{-1}$ dan $[v]_m=[y]_m^{-1}$. Teorema Sisa Cina memberikan $w\in{\mathbb Z}$ yang memenuhi $w\equiv u\pmod n$ dan $w\equiv v\pmod m$. Akibatnya, $zw\equiv1\pmod n$ dan $zw\equiv1\pmod m$. Karena $zw$ dan $1$ merupakan solusi sistem yang sama, ketunggalan dalam Teorema Sisa Cina memberi $zw\equiv1\pmod{nm}$. Jadi, $[z]_{nm}\in({\mathbb Z}/(nm){\mathbb Z})^*$ dan ${\mathcal F}([z]_{nm})=([x]_n,[y]_m)$. Dengan demikian, ${\mathcal F}$ juga surjektif. ◻