3 Bilangan Prima

Bukti. Misalkan $n$ komposit. Maka $n$ mempunyai suatu pembagi sejati $a\in{\mathbb N}$. Perhatikan bahwa $n=a\cdot\frac{n}{a}$, sehingga $\frac{n}{a}\in{\mathbb N}$ juga merupakan pembagi. Namun, $a$ dan $\frac{n}{a}$ tidak mungkin keduanya lebih besar daripada $\sqrt{n}$, sebab jika demikian, kita akan memperoleh $$n=a\cdot\frac{n}{a}>\sqrt{n}\cdot\sqrt{n}=n,$$ suatu kontradiksi. Jadi, setidaknya salah satu dari $a$ atau $\frac{n}{a}$ merupakan pembagi $d$ yang dijanjikan dalam pernyataan teorema. ◻

Bukti. Perhatikan bahwa $\gcd(p,a)\mid p$. Karena $p$ prima, $\gcd(p,a)$ bernilai $1$ atau $p$. Selain itu, $\gcd(a,p)\mid a$, sehingga $p\mid a$ atau $\gcd(a,p)=1$. Jika $p\mid a$, pembuktian selesai. Jika tidak, $\gcd(a,p)=1$, sehingga Lemma Euklides 2.6 menyatakan bahwa $p\mid b$. ◻

Bukti. Diserahkan kepada pembaca (gunakan induksi pada $k$). ◻

Bukti. Untuk bagian eksistensi, kita menggunakan Prinsip Kedua Induksi Matematika.

Pernyataan umum yang akan dibuktikan adalah $\forall n\in{\mathbb Z},\ n>1\Rightarrow S(n)$, dengan $S(n)$ menyatakan “terdapat $k\in{\mathbb N}$ dan bilangan-bilangan prima $p_1,\dots,p_k$ sedemikian sehingga $n=p_1\dots p_k$.”

Sebagai langkah dasar, ambil $n=2$. Pilihan $k=1$ dan $p_1=2$ memenuhi pernyataan tersebut.

Sekarang, anggap $S(r)$ benar untuk setiap bilangan bulat $r$ yang memenuhi $1<r<n$. Jika $n$ prima, pilihan $k=1$ dan $p_1=n$ memenuhi pernyataan. Sebaliknya, misalkan $n$ komposit dengan pembagi sejati $d$. Maka $1<d<n$ dan $1<\frac{n}{d}<n$. Berdasarkan hipotesis induksi, terdapat $k,k^\prime\in{\mathbb N}$ dan bilangan-bilangan prima $p_1,\dots,p_k,p^\prime_1,\dots,p^\prime_{k^\prime}$ sedemikian sehingga $d=p_1\dots p_k$ dan $\frac{n}{d}=p^\prime_1\dots p^\prime_{k^\prime}$. Dengan demikian, $n$ merupakan hasil kali $$n=p_1\dots p_k\cdot p^\prime_1\dots p^\prime_{k^\prime}$$ dari $k+k^\prime$ bilangan prima. Jadi, $S(n)$ juga benar; dengan demikian, faktorisasi prima selalu ada.

Sekarang, misalkan $n\in{\mathbb Z}$, $n>1$, mempunyai dua faktorisasi prima, yakni terdapat $k,l\in{\mathbb N}$ dan bilangan-bilangan prima $p_1,\dots,p_k$ serta $q_1,\dots,q_l$ sedemikian sehingga $$p_1\dots p_k = n = q_1\dots q_l\ .$$ Jelas bahwa $p_1$ membagi ruas kiri, sehingga $p_1$ juga membagi $q_1\dots q_l$. Berdasarkan Akibat 3.6, $p_1$ membagi salah satu $q_j$. Karena $p_1$ dan $q_j$ keduanya prima, haruslah $p_1=q_j$. Setelah membatalkan $p_1$ pada ruas kiri dan $q_j$ pada ruas kanan, kita memperoleh $$\prod_{i=2}^{k}p_i=\frac{n}{p_1} =\prod_{\substack{1\le i\le l\\i\ne j}}q_i\ ,$$ dengan hasil kali kosong ditafsirkan sebagai $1$. Lanjutkan pembatalan dengan cara yang sama. Salah satu daftar faktor tidak mungkin habis lebih dahulu, sebab hal itu akan membuat hasil kali satu atau lebih bilangan prima pada ruas lain sama dengan $1$, yang mustahil. Jadi, kedua daftar mempunyai panjang yang sama, dan faktor-faktornya sama hingga urutan. Inilah ketunggalan yang dinyatakan dalam teorema. ◻

Bukti. Misalkan $p$ bilangan prima dan $n\in{\mathbb N}$ merupakan invers bagi dirinya sendiri modulo $p$. Artinya, $n^2=n\cdot n\equiv1\pmod{p}$. Menurut definisi, $p\mid n^2-1=(n+1)(n-1)$. Berdasarkan Proposisi 3.5, hal ini berarti $p\mid n+1$ atau $p\mid n-1$.

Sebaliknya, andaikan $n\equiv1\pmod{p}$ atau $n\equiv-1\pmod{p}$. Berdasarkan Teorema 2.3, $n^2\equiv(\pm1)^2=1\pmod{p}$, sehingga $n$ merupakan invers bagi dirinya sendiri modulo $p$. ◻

Bukti. Andaikan $p$ prima. Jika $p=2$, maka $(p-1)!=1\equiv-1\pmod{2}$, sehingga kesimpulan yang diinginkan berlaku. Sekarang andaikan $p$ ganjil. Menurut Akibat 2.17, setiap bilangan $2,\dots,p-2$ mempunyai invers modulo $p$, dan menurut Lemma 3.8, tidak satu pun di antaranya merupakan invers bagi dirinya sendiri. Oleh karena itu, bilangan-bilangan tersebut dapat dikelompokkan menjadi $(p-3)/2$ pasangan invers. Dengan menyisakan hanya $1$ dan $(p-1)$, kita memperoleh $$(p-1)! \equiv 1\cdot 1^{(p-3)/2}\cdot(p-1) \equiv p-1\equiv -1\pmod{p}.$$

Sebaliknya, andaikan $p\in{\mathbb N}$ memenuhi $p\ge2$ dan $(p-1)!\equiv-1\pmod{p}$. Kongruensi ini dapat ditulis kembali sebagai $(p-1)!+1\equiv0\pmod{p}$, atau $p\mid((p-1)!+1)$.

Sekarang, misalkan $d\in{\mathbb N}$ pembagi $p$ dengan $d\neq p$. Dengan demikian, $d$ merupakan salah satu bilangan dalam hasil kali $(p-1)!$, sehingga $d\mid(p-1)!$. Selain itu, karena $d\mid p$ dan $p\mid((p-1)!+1)$, berlaku pula $d\mid((p-1)!+1)$. Oleh Teorema 1.15, $$d\mid((p-1)!+1)-(p-1)!=1,$$ yang berarti $d=1$.

Dengan kata lain, setiap pembagi $d\in{\mathbb N}$ dari $p$ haruslah $p$ atau $1$; jadi, $p$ prima. ◻

Bukti. Masalah yang mungkin muncul dalam definisi $\operatorname{ord}_n(a)$ adalah tidak adanya nilai $k\in{\mathbb N}$ yang memenuhi $a^k\equiv1\pmod{n}$.

Namun, perhatikan bahwa ini adalah sebuah kongruensi, sehingga kita sebenarnya hanya memperhatikan kelas kongruensi dari elemen-elemen $a^k$.

Perhatikan $\{[a^p]_n\mid p\in{\mathbb N}\}$ dan bayangkan kita memasukkan setiap bilangan asli $p\in{\mathbb N}$ ke dalam kotak yang ditentukan oleh kelas kongruensi $[a^p]\in{\mathbb Z}/n{\mathbb Z}$. Karena ${\mathbb N}$ mempunyai tak berhingga banyak elemen, sedangkan ${\mathbb Z}/n{\mathbb Z}$ hanya mempunyai $n$ elemen—atau $n$ kotak—maka menurut Prinsip Sarang Merpati (Teorema 1.2) terdapat dua (bahkan tak berhingga banyak pasangan) nilai berbeda $p,q\in{\mathbb N}$ yang masuk ke kotak yang sama. Artinya, $[a^p]=[a^q]$. Tanpa mengurangi keumuman, andaikan $p>q$, sehingga $p-q\in{\mathbb N}$.

Kita mengetahui bahwa $\gcd(a,n)=1$, sehingga, berdasarkan Akibat 2.17, invers $a^{-1}$ ada modulo $n$. Oleh karena itu, $$a^{p-q}\equiv a^p\,(a^{-1})^q\equiv a^q\,(a^{-1})^q \equiv a^0\equiv1\pmod{n}.$$ Di bagian tengah kongruensi ini, kita mengganti $a^p$ dengan $a^q$ karena $[a^p]=[a^q]$, yang berarti $a^p\equiv a^q\pmod{n}$. Jadi, himpunan semua $k\in{\mathbb N}$ yang memenuhi $a^k\equiv1\pmod{n}$ tidak kosong. Orde adalah nilai terkecil dalam himpunan tersebut, dan keberadaannya dijamin oleh Prinsip Keterurutan Baik. ◻

Bukti. Mulailah dengan memperhatikan kelas-kelas kongruensi $[a],[a^2],[a^3],\dots$. Kelas-kelas ini berlanjut hingga $[a^{\operatorname{ord}_n(a)}]=[1]$, lalu mulai berulang. Berdasarkan keminimalan $\operatorname{ord}_n(a)$, kelas-kelas sebelum pengulangan itu berbeda satu sama lain. Jadi, himpunan $$\left<a\right>=\{[a^j]\mid j\in{\mathbb N}, j\le\operatorname{ord}_n(a)\}$$ terdiri atas $\operatorname{ord}_n(a)$ elemen dari ${\mathbb Z}/n{\mathbb Z}$. Dalam teori grup, himpunan $\left<a\right>$ disebut subgrup siklik dari $({\mathbb Z}/n{\mathbb Z})^*$ yang dibangkitkan oleh $a$. Perhatikan bahwa $a^{\operatorname{ord}_n(a)}\equiv1\pmod{n}$, sehingga $[1]\in\left<a\right>$. Selain itu, jika $a^{-1}$ adalah invers $a$ modulo $n$, maka $(a^{-1})^k$ adalah invers $a^k$ untuk setiap $k\in{\mathbb N}$. Dengan demikian, $\left<a\right>\subseteq({\mathbb Z}/n{\mathbb Z})^*$.

Untuk menyelesaikan pembuktian, kita akan menunjukkan bahwa $({\mathbb Z}/n{\mathbb Z})^*$ tersusun atas sejumlah bagian, katakanlah $m$ bagian, yang kita sebut koset. Setiap koset berkorespondensi secara bijektif dengan $\left<a\right>$, sehingga masing-masing mempunyai $\operatorname{ord}_n(a)$ elemen. Oleh karena itu, $$m\cdot\operatorname{ord}_n(a)=\#\left(({\mathbb Z}/n{\mathbb Z})^*\right)=\phi(n),$$

dan hasil yang diinginkan pun mengikuti.

Sebuah koset dari $\left<a\right>$ adalah himpunan berbentuk $$x\left<a\right>=\{[x]\cdot[a^j]=[x\,a^j]\mid j\in{\mathbb N}, j\le\operatorname{ord}_n(a)\}$$ dengan $[x]\in({\mathbb Z}/n{\mathbb Z})^*$. Kita telah melihat bahwa $[1]\in\left<a\right>$. Jadi, untuk setiap $[x]\in({\mathbb Z}/n{\mathbb Z})^*$, berlaku $[x]\in x\left<a\right>$. Artinya, setiap kelas kongruensi dalam $({\mathbb Z}/n{\mathbb Z})^*$ berada di suatu koset. Karena setiap koset juga merupakan subhimpunan $({\mathbb Z}/n{\mathbb Z})^*$, kita mempunyai $$({\mathbb Z}/n{\mathbb Z})^*=\bigcup_{[x]\in({\mathbb Z}/n{\mathbb Z})^*}x\left<a\right>.$$

Setiap koset $x\left<a\right>$ memang berkorespondensi secara bijektif dengan $\left<a\right>$. Bijeksinya adalah pemetaan $f_x:\left<a\right>\to x\left<a\right>$ yang didefinisikan oleh $f_x([a^j])=[x a^j]$ untuk $j\in{\mathbb N}$ dengan $j\le\operatorname{ord}_n(a)$. Pemetaan ini mempunyai invers berupa perkalian dengan kelas $[x^{-1}]$, yang berasal dari invers $x$ modulo $n$.

Sekarang, misalkan $x\left<a\right>$ dan $y\left<a\right>$ adalah dua koset. Kita akan menunjukkan bahwa keduanya sama atau saling lepas. Andaikan $x\left<a\right>\cap y\left<a\right>\neq\emptyset$. Maka terdapat $[z]\in x\left<a\right>\cap y\left<a\right>$, sehingga terdapat $j,k\in{\mathbb N}$ dengan $j,k\le\operatorname{ord}_n(a)$ dan $[xa^j]=[z]=[ya^k]$. Dengan kata lain, $$xa^j\equiv ya^k\pmod{n}.$$ Tanpa mengurangi keumuman, andaikan $j\le k$. Dengan mengalikan kedua ruas kongruensi tersebut dengan $(a^{-1})^j$, kita memperoleh $x\equiv ya^{k-j}\pmod{n}$. Karena itu, setiap elemen $[x a^t]\in x\left<a\right>$ dapat ditulis sebagai $[y a^{t+k-j}]$; dengan mengurangi pangkatnya modulo $\operatorname{ord}_n(a)$ (dan mewakili sisa nol dengan $\operatorname{ord}_n(a)$), kelas ini berada di $y\left<a\right>$. Jadi, $x\left<a\right>\subseteq y\left<a\right>$. Kedua koset mempunyai banyak elemen berhingga yang sama, yaitu $\operatorname{ord}_n(a)$, sehingga keduanya sama. Dengan demikian, dua koset mana pun sama atau saling lepas, dan koset-koset tersebut membentuk partisi $({\mathbb Z}/n{\mathbb Z})^*$. Persamaan kardinalitas di atas kini membuktikan bahwa $\operatorname{ord}_n(a)\mid\phi(n)$. ◻

Bukti. Jika $n=1$, hasilnya langsung berlaku karena semua bilangan bulat kongruen modulo $1$. Sekarang andaikan $n\ge2$. Teorema sebelumnya, Teorema 3.13, menyatakan bahwa $\operatorname{ord}_n(a)\mid\phi(n)$. Jadi, terdapat $m\in{\mathbb N}$ sedemikian sehingga $m\cdot\operatorname{ord}_n(a)=\phi(n)$. Berdasarkan definisi orde, $$a^{\phi(n)}\equiv a^{m\operatorname{ord}_n(a)} \equiv\left(a^{\operatorname{ord}_n(a)}\right)^m\equiv1^m\equiv1\pmod{n}.$$ ◻

Bukti. Kita telah melihat bahwa $\phi(p)=p-1$ untuk setiap bilangan prima $p$, sehingga hasil ini langsung mengikuti dari Teorema Euler. ◻

Bukti. Jika $\gcd(a,p)=1$, maka, berdasarkan Teorema Kecil Fermat, $a^{p-1}\equiv1\pmod{p}$. Mengalikan kedua ruas kongruensi ini dengan $a$ menghasilkan kesimpulan yang diinginkan.

Sebaliknya, jika $\gcd(a,p)\neq1$, maka $\gcd(a,p)=p$, sebab FPB tersebut merupakan pembagi bilangan prima $p$. FPB itu juga membagi $a$, sehingga $p\mid a$. Akibatnya, $a$ dan semua pangkat positifnya kongruen dengan $0$ modulo $p$, dan $a^p\equiv0\equiv a\pmod{p}$. ◻

Bukti. Kita mulai dengan membuktikan bahwa himpunan $$M_a=\left\{[0]_p,[a]_p,[2a]_p,\dots,[(p-1)a]_p\right\}$$ yang terdiri atas kelipatan-kelipatan $[a]_p$ dalam ${\mathbb Z}/p{\mathbb Z}$ mempunyai $p$ elemen.

Di antara tanda $\{$ dan $\}$ hanya tercantum $p$ kelas kongruensi, sehingga himpunan tersebut tidak mungkin mempunyai lebih dari $p$ elemen.

Sekarang, ambil dua elemen dari himpunan ini, yaitu $[ja]_p$ dan $[ka]_p$, dengan $0\le j,k<p$, dan andaikan keduanya sama. Artinya, $ja\equiv ka\pmod{p}$, atau $p\mid(j-k)a$. Menurut Proposisi 3.5, berlaku $p\mid(j-k)$ atau $p\mid a$. Karena $\gcd(p,a)=1$, tidak mungkin $p\mid a$. Jadi, $p\mid(j-k)$.

Karena $0\le j,k<p$, kita mempunyai $-p<j-k<p$, dan satu-satunya kelipatan $p$ dalam rentang ini adalah $0$. Oleh karena itu, $j=k$. Semua elemen dalam deskripsi $M_a$ di atas berbeda, sehingga $\#(M_a)=p$. Kita juga telah mengetahui bahwa ${\mathbb Z}/p{\mathbb Z}$ mempunyai $p$ elemen; jadi, $M_a$ hanyalah cara lain untuk mendeskripsikan ${\mathbb Z}/p{\mathbb Z}$.

Sebagai langkah berikutnya, kalikan semua elemen tak nol dari $M_a$, atau sama saja, semua elemen tak nol dari ${\mathbb Z}/p{\mathbb Z}$: $$a\cdot2a\cdot\dots\cdot(p-1)a \equiv1\cdot2\cdot\dots\cdot(p-1)\pmod{p}.$$ Dengan menyusun ulang faktor-faktornya, kita memperoleh $$a^{p-1}(p-1)!\equiv(p-1)!\pmod{p},$$ atau $p\mid(a^{p-1}-1)(p-1)!$. Karena $p$ prima, berlaku $\gcd(p,(p-1)!)=1$. Berdasarkan Proposisi 3.5, kita memperoleh $p\mid a^{p-1}-1$. Dengan kata lain, $a^{p-1}\equiv1\pmod{p}$, seperti yang diinginkan. ◻

Bukti. Jika $n=1$, kesimpulannya langsung berlaku karena semua bilangan bulat kongruen modulo $1$. Sekarang andaikan $n\ge2$. Ingat bahwa himpunan elemen yang dapat dibalik secara multiplikatif dalam ${\mathbb Z}/n{\mathbb Z}$ dapat ditulis sebagai $$({\mathbb Z}/n{\mathbb Z})^*=\{[b_1]_n,\dots,[b_{\phi(n)}]_n\},$$ dengan bilangan-bilangan $b_1,\dots,b_{\phi(n)}$ yang semuanya relatif prima terhadap $n$ dan memenuhi $1\le b_1<\dots<b_{\phi(n)}<n$.

Kita mengklaim bahwa $({\mathbb Z}/n{\mathbb Z})^*$ juga dapat dideskripsikan sebagai himpunan $$M_a^*=\left\{[b_1a]_n,\dots,[b_{\phi(n)}a]_n\right\}.$$ Pertama, karena setiap $b_j$ relatif prima terhadap $n$, demikian pula $a$, maka $b_ja$ juga relatif prima terhadap $n$. Setiap bilangan prima yang membagi $b_ja$ membagi $b_j$ atau $a$, dan tidak ada bilangan prima semacam itu yang juga membagi $n$. Jadi, $M_a^*\subseteq({\mathbb Z}/n{\mathbb Z})^*$.

Selanjutnya, jika $[b_ja]_n=[b_ka]_n$ untuk $1\le j,k\le\phi(n)$, maka $n\mid(b_j-b_k)a$. Berdasarkan Lemma Euklides 2.6 , karena $\gcd(a,n)=1$, kita harus mempunyai $n\mid(b_j-b_k)$.

Namun, karena $1\le b_1<\dots<b_{\phi(n)}<n$, berlaku $-n+1<b_j-b_k<n-1$, dan satu-satunya kelipatan $n$ dalam rentang ini adalah $0$. Jadi, $b_j=b_k$, sehingga semua elemen dalam deskripsi $M_a^*$ di atas berbeda. Himpunan $M_a^*$ mempunyai $\phi(n)$ elemen dan merupakan subhimpunan $({\mathbb Z}/n{\mathbb Z})^*$, yang juga hanya mempunyai $\phi(n)$ elemen. Oleh karena itu, $M_a^*=({\mathbb Z}/n{\mathbb Z})^*$.

Seperti dalam pembuktian sebelumnya, hasil kali semua elemen $M_a^*$ harus sama dengan hasil kali semua elemen $({\mathbb Z}/n{\mathbb Z})^*$: $$b_1a\cdot\dots\cdot b_{\phi(n)}a \equiv b_1\cdot\dots\cdot b_{\phi(n)}\pmod{n}.$$ Dengan mengelompokkan ulang faktor-faktornya, kita memperoleh $$a^{\phi(n)}b_1\cdot\dots\cdot b_{\phi(n)} \equiv b_1\cdot\dots\cdot b_{\phi(n)}\pmod{n}.$$ Semua $b_j$ mempunyai invers modulo $n$. Dengan mengalikan kedua ruas secara berturut-turut dengan invers-invers tersebut, kita memperoleh $$a^{\phi(n)}\equiv1\pmod{n},$$ yang menyelesaikan pembuktian Teorema Euler. ◻