5 Indeks = Logaritma Diskret

Bukti. Satu arah sangat mudah: jika $k\in{\mathbb N}$ memenuhi $\operatorname{ord}_n(a)\mid k$, maka $\exists d\in{\mathbb N}$ sedemikian sehingga $k=\operatorname{ord}_n(a)\cdot d$. Jadi, $$a^k=a^{\operatorname{ord}_n(a)\cdot d}=(a^{\operatorname{ord}_n(a)})^d\equiv1^d=1\pmod{n}\ .$$

Sebaliknya, misalkan $k\in{\mathbb N}$ memenuhi $a^k\equiv1\pmod{n}$. Terapkan Algoritma Pembagian untuk memperoleh $q,r\in{\mathbb Z}_{\ge0}$ sedemikian sehingga $k=\operatorname{ord}_n(a)\cdot q+r$ dan $0\le r<\operatorname{ord}_n(a)$. Maka $$1\equiv a^k=a^{\operatorname{ord}_n(a)\cdot q + r}=(a^{\operatorname{ord}_n(a)})^q\cdot a^r\equiv1^q\cdot a^r\equiv a^r\pmod{n}\ .$$ Namun, menurut definisi orde, $\operatorname{ord}_n(a)$ adalah bilangan bulat positif terkecil yang membuat $a$ berpangkat bilangan tersebut kongruen dengan 1. Karena itu, $a^r\equiv1\pmod{n}$ dan $0\le r<\operatorname{ord}_n(a)$ hanya mungkin jika $r=0$. Jadi, $k=\operatorname{ord}_n(a)\cdot q$ dan $\operatorname{ord}_n(a)\mid k$, seperti yang diinginkan. ◻

Bukti. Sekali lagi, satu arah sangat mudah. Misalkan $j,k\in{\mathbb N}$ memenuhi $j\equiv k\pmod{\operatorname{ord}_n(a)}$. Karena kesimpulannya simetris dalam $j$ dan $k$, tanpa mengurangi keumuman ambil $j\ge k$. Dengan demikian, $\exists\ell\in{\mathbb Z}_{\ge0}$ sedemikian sehingga $j=k+\operatorname{ord}_n(a)\cdot\ell$, dan $$a^j=a^{k+\operatorname{ord}_n(a)\cdot\ell}=a^k\cdot (a^{\operatorname{ord}_n(a)})^\ell\equiv a^k\cdot1^\ell=a^k\pmod{n}\ .$$

Sebaliknya, misalkan $j,k\in{\mathbb N}$ memenuhi $a^j\equiv a^k\pmod{n}$. Jika $j=k$, kesimpulannya langsung berlaku. Jika $j\ne k$, tanpa mengurangi keumuman ambil $j>k$, sehingga $j-k\in{\mathbb N}$. Kalikan kedua ruas kongruensi dengan $(a^{-1})^k$, yang ada karena $\gcd(a,n)=1$. Kita memperoleh $a^{j-k}\equiv1\pmod{n}$. Menurut Teorema 5.1, $\operatorname{ord}_n(a)\mid(j-k)$, atau dengan kata lain $j\equiv k\pmod{\operatorname{ord}_n(a)}$. ◻

Bukti. Tetapkan suatu $k\in{\mathbb N}$, lalu tuliskan $r=\operatorname{ord}_n(a^k)$ dan $s=\operatorname{ord}_n(a)$. Dengan notasi ini, kita hendak membuktikan bahwa $\displaystyle r=\frac{s}{\gcd(s,k)}$.

Dalam bukti ini kita akan berulang kali menggunakan fakta bahwa, karena $\gcd$ merupakan pembagi, $\gcd(s,k)\mid s$ dan $\gcd(s,k)\mid k$. Oleh sebab itu, $\displaystyle\frac{s}{\gcd(s,k)},\frac{k}{\gcd(s,k)}\in{\mathbb N}$.

Sekarang kita mulai pembuktiannya.

Menurut definisi orde, $r$ adalah bilangan asli terkecil yang memenuhi $(a^k)^r\equiv1\pmod{n}$. Perhatikan bahwa $$(a^k)^{\frac{s}{\gcd(s,k)}}=(a^s)^{\frac{k}{\gcd(s,k)}}\equiv 1^{\frac{k}{\gcd(s,k)}}=1\pmod{n}\ .$$

Menurut Teorema 5.1, kita menyimpulkan bahwa $\displaystyle r\mid \left(\frac{s}{\gcd(s,k)}\right)$.

Terlepas dari sifat minimalnya, karena $a^{kr}=(a^k)^r\equiv1\pmod{n}$, Teorema 5.1 memberikan $s\mid kr$. Jadi, $\exists m\in{\mathbb N}$ sedemikian sehingga $ms=kr$. Dengan membagi kedua ruas oleh $\gcd(s,k)$, kita memperoleh persamaan bilangan asli $$m \left(\frac{s}{\gcd(s,k)}\right)=\left(\frac{k}{\gcd(s,k)}\right) r;$$ yang berarti $$\frac{s}{\gcd(s,k)}\mid \left(\frac{k}{\gcd(s,k)}\right)r\ .$$ Menurut Teorema 1.26, $\displaystyle\gcd\left(\frac{s}{\gcd(s,k)},\frac{k}{\gcd(s,k)}\right)=1$, maka Lemma Euklides 2.6 menyatakan bahwa $\displaystyle\frac{s}{\gcd(s,k)}\mid r$.

Kita telah menunjukkan bahwa $r$ dan $\displaystyle\frac{s}{\gcd(s,k)}$ saling membagi. Dengan demikian, keduanya sama, seperti yang hendak dibuktikan. ◻

Bukti 1. Tetapkan $n\in{\mathbb N}$.

Untuk setiap pilihan pembagi positif $d\mid n$, definisikan himpunan bagian dari $\{1,\dots,n\}$ berikut: $$S_d=\left\{k\in{\mathbb N}\mid 1\le k\le n\ \text{dan}\ \gcd(k,n)=d\right\}\ .$$

Himpunan-himpunan ini saling lepas. Memang, untuk setiap $k\in{\mathbb N}$ dengan $1\le k\le n$, nilai $d=\gcd(k,n)$ sudah tertentu, sehingga $k$ hanya berada dalam $S_d$ tersebut.

Untuk $k\in S_d$, berlaku $\gcd(k,n)=d$. Menurut Teorema 1.26, $\gcd(k/d,n/d)=1$. Jadi, $\#(S_d)$ adalah banyaknya unsur $\ell\in{\mathbb N}$ dalam rentang $1\le\ell\le n/d$ yang relatif prima terhadap $n/d$; dengan kata lain, $\#(S_d)=\phi(n/d)$.

Setiap $k\in{\mathbb Z}$ dalam rentang $1\le k\le n$ berada tepat dalam satu $S_d$ semacam ini, dengan $d$ suatu pembagi positif dari $n$. Oleh karena itu, $$\{1,\dots,n\} = \bigcup_{\substack{d\in{\mathbb N}\\d\mid n}} S_d$$ sehingga $$n=\#\left(\{1,\dots,n\}\right) = \#\left(\bigcup_{\substack{d\in{\mathbb N}\\d\mid n}} S_d\right) = \sum_{\substack{d\in{\mathbb N}\\d\mid n}} \#\left(S_d\right) = \sum_{\substack{d\in{\mathbb N}\\d\mid n}} \phi(n/d)\ .$$ Namun, ketika $d$ merentang seluruh pembagi positif $n$, demikian pula $n/d$. Dengan kata lain, $$\left\{d\mid d\in{\mathbb N},\ 1\le d\le n\text{\ dan\ }d\mid n\right\}=\left\{n/d\mid d\in{\mathbb N},\ 1\le d\le n\text{\ dan\ }d\mid n\right\}$$

Karena itu, persamaan besar terakhir dapat ditulis ulang sebagai $$n=\sum_{\substack{d\in{\mathbb N}\\d\mid n}} \phi(n/d)=\sum_{\substack{d\in{\mathbb N}\\d\mid n}} \phi(d)$$ seperti yang hendak dibuktikan. ◻

Bukti 2. Pendekatan ini berpusat pada fungsi $$F(n)=\sum_{\substack{d\in{\mathbb N}\\d\mid n}} \phi(d)\ ,$$ yang mempunyai beberapa sifat sangat baik.

Sebagai contoh, misalkan $p$ prima dan $k\in{\mathbb N}$. Pembagi-pembagi $p^k$ adalah $1,p,p^2,\dots,p^k$, sehingga $$F(p^k)=\phi(1)+\phi(p)+\phi(p^2)+\dots+\phi(p^k) =1+(p-1)+(p^2-p)+\dots+(p^k-p^{k-1}) = p^k\ .$$

Selanjutnya, jika $p$ dan $q$ adalah bilangan prima berbeda, pembagi-pembagi $pq$ adalah $1$, $p$, $q$, dan $pq$. Selain itu, $\gcd(p,q)=1$. Jadi, menurut Teorema 2.33, $$\begin{align*} F(pq)&=\phi(1)+\phi(p)+\phi(q)+\phi(pq)\\ &=\phi(1)+\phi(p)+\phi(q)+\phi(p)\phi(q)\\ &=(1+\phi(p))(1+\phi(q))\\ &=F(p)F(q)\ . \end{align*}$$ Dari fakta ini, dapat dibuktikan (sebagai latihan di bawah) bahwa $F(ab)=F(a)F(b)$ setiap kali $a,b\in{\mathbb N}$ relatif prima. Artinya, $F$ mempunyai sifat multiplikatif terhadap faktor-faktor yang relatif prima, sama seperti $\phi$.

Sekarang kita siap menyelesaikan bukti. Ambil sebarang $n\in{\mathbb N}$ dengan $n>1$ (untuk $n=1$, teorema ini langsung benar). Misalkan faktorisasi prima dari $n$ diberikan oleh $$n=p_1^{k_1}\cdot\cdots\cdot p_r^{k_r}\ ,$$ dengan $\{p_1,\dots,p_r\}$ bilangan-bilangan prima yang berbeda. Karena itu, $\gcd(p_i^{k_i},p_j^{k_j})=1$ jika $i\neq j$. Dengan memakai sifat multiplikatif $F$ dan perhitungan $F$ untuk pangkat-pangkat bilangan prima, kita menyimpulkan $$\begin{align*} F(n)&=F(p_1^{k_1}\cdot\cdots\cdot p_r^{k_r})\\ &=F(p_1^{k_1})\cdot\cdots\cdot F(p_r^{k_r})\\ &=p_1^{k_1}\cdot\cdots\cdot p_r^{k_r}\\ &=n\ , \end{align*}$$ seperti yang hendak dibuktikan. ◻

Bukti. Misalkan $a\in({\mathbb Z}/n{\mathbb Z})^*$ suatu akar primitif. Artinya, $$\left<a\right>=\left\{a,\ a^2,\ \dots\ a^{\operatorname{ord}_n(a)}\right\}=({\mathbb Z}/n{\mathbb Z})^*$$ karena $\operatorname{ord}_n(a)=\phi(n)=\#\left(({\mathbb Z}/n{\mathbb Z})^*\right)$. Setiap akar primitif lain $b$, sebagai unsur $({\mathbb Z}/n{\mathbb Z})^*$, harus merupakan salah satu pangkat $a$ tersebut. Dengan memilih wakil pangkat secara unik, terdapat tepat satu $k$ dengan $1\le k\le\phi(n)$ sedemikian sehingga $b=a^k$.

Agar $b$ ini menjadi akar primitif, ordenya harus $\phi(n)$. Namun, menurut Teorema 5.4, $$\operatorname{ord}_n(b)=\frac{\operatorname{ord}_n(a)}{\gcd(\operatorname{ord}_n(a),k)} =\frac{\phi(n)}{\gcd(\phi(n),k)}\ .$$

Jadi, $b=a^k$ merupakan akar primitif jika dan hanya jika $\gcd(\phi(n),k)=1$. Menurut definisi fungsi $\phi$ Euler , di antara $1\le k\le\phi(n)$ terdapat tepat $\phi(\phi(n))$ nilai $k$ semacam itu. ◻

Bukti. Kita menggunakan induksi pada derajat $n$. Kasus dasar $n=1$ berarti menyelesaikan kongruensi linear $a_1x+a_0\equiv0\pmod{p}$ dengan $a_1\not\equiv0\pmod{p}$. Karena $p$ prima, hal ini berarti $\gcd(p,a_1)=1$. Jadi, menurut versi Teorema 2.13 yang dinyatakan dalam Catatan 2.14, kongruensi linear tersebut mempunyai solusi unik modulo $p$.

Untuk langkah induksi, andaikan teorema benar untuk suatu $n\in{\mathbb N}$, lalu kita buktikan kasus $n+1$. Misalkan $a_0,\dots,a_{n+1}\in{\mathbb Z}$ memenuhi $a_{n+1}\not\equiv0\pmod{p}$. Jika $$a(x)=a_{n+1}x^{n+1}+a_nx^n+\dots+a_1x+a_0$$ tidak mempunyai akar modulo $p$, teorema jelas benar untuk polinomial berderajat $n+1$ ini: banyaknya solusi $a(x)\equiv0\pmod{p}$ adalah $0<n+1$.

Sebaliknya, jika $a(x)$ mempunyai sekurang-kurangnya satu akar modulo $p$, pilih wakil bilangan bulatnya $z_1$. Pembagian panjang polinomial memberikan $$a(x)=b(x)(x-z_1) + r(x)$$ dengan $b(x)$ dan $r(x)$ polinomial berkoefisien bilangan bulat yang memenuhi $$0\le\deg(r(x))<\deg(x-z_1)=1\ .$$ Karena itu, $r(x)$ merupakan polinomial konstan, katakanlah bernilai $r_1\in{\mathbb Z}$.

Substitusikan $z_1$ ke dalam rumus hasil pembagian polinomial di atas: $$0\equiv a(z_1)\equiv b(z_1)(z_1-z_1)+r_1\equiv r_1\pmod{p}\ .$$ Jadi, $r_1\equiv0\pmod{p}$, sehingga $a(x)\equiv b(x)(x-z_1)\pmod{p}$. Koefisien $a_{n+1}$ sama dengan koefisien utama $b(x)$, sehingga koefisien utama itu tidak kongruen dengan $0$ modulo $p$.

Karena itu, hipotesis induksi berlaku bagi $b(x)$ dan menyatakan bahwa $b(x)$ mempunyai paling banyak $n$ akar modulo $p$. Akar-akar $b(x)$ tersebut, ditambah satu akar dari $(x-z_1)$, berjumlah paling banyak $n+1$ akar bagi $a(x)\equiv b(x)(x-z_1)\pmod{p}$.

Untuk menuntaskan bukti, kita hanya perlu memastikan bahwa setiap akar $a(x)$ memang merupakan akar $b(x)$ atau $(x-z_1)$. Misalkan $r\in{\mathbb Z}$ suatu akar. Maka $$a(r)=b(r)(r-z_1)\equiv0\pmod{p},$$ yang berarti $p\mid b(r)(r-z_1)$. Menurut Proposisi 3.5, haruslah $p\mid b(r)$ atau $p\mid(r-z_1)$. Dengan kata lain, $b(r)\equiv0\pmod{p}$ atau $(r-z_1)\equiv0\pmod{p}$, seperti yang diharapkan. [Ini menggunakan apa yang dalam aljabar dasar disebut “sifat hasil kali nol”. Sifat tersebut berlaku dalam ${\mathbb Z}/p{\mathbb Z}$ untuk $p$ prima menurut Proposisi 3.5; dalam aljabar abstrak, kita mengatakan bahwa ${\mathbb Z}/p{\mathbb Z}$ merupakan suatu domain jika $p$ prima.]

Jadi, semua akar $a(x)$ berasal dari akar $b(x)$ atau $(x-z_1)$, sehingga banyaknya paling besar $n+1$. Langkah induksi pun terbukti. ◻

Bukti. Misalkan $p$ dan $d$ seperti dalam pernyataan, lalu definisikan $m=(p-1)/d\in{\mathbb N}$. Kita menggunakan faktorisasi cerdik berikut: $$\begin{align*} a(x)&=x^d-1,\\ b(x)&=x^{dm-d}+x^{dm-2d}+\dots+x^d+1,\ \text{dan}\\ c(x)&=x^{p-1}-1 \end{align*}$$ sehingga $c(x)=a(x)b(x)$.

Menurut Teorema Kecil Fermat, $c(x)$ mempunyai tepat $p-1$ akar berbeda modulo $p$, yaitu $\{1,\dots,p-1\}$. Selain itu, menurut Teorema 5.9, $b(x)$ mempunyai paling banyak $\deg(b(x))=dm-d=p-1-d$ akar. Seperti dalam bukti teorema tersebut (pada bagian tentang “sifat hasil kali nol” ), himpunan akar $c(x)$ adalah gabungan himpunan akar $a(x)$ dan $b(x)$. Karena $p-1$ akar berbeda itu harus tertampung dalam gabungan tersebut, sedangkan $b(x)$ mempunyai paling banyak $p-1-d$ akar, $a(x)$ mempunyai sekurang-kurangnya $d$ akar. Di sisi lain, Teorema 5.9 membatasi polinomial berderajat $d$ ini pada paling banyak $d$ akar. Jadi, $a(x)=x^d-1$ mempunyai tepat $d$ akar modulo $p$. ◻

Bukti. Misalkan $p$ dan $d$ seperti dalam pernyataan, lalu tuliskan $$\psi(k)=\#\left(\left\{\ell\in{\mathbb Z}\mid1\le\ell\le p-1\text{\ dan\ }\operatorname{ord}_p(\ell)=k\right\}\right)\ .$$ Menurut versi Teorema Lagrange kita, Teorema 3.13, setiap $\ell\in{\mathbb Z}$ dengan $1\le\ell\le p-1$ mempunyai orde yang membagi $\phi(p)=p-1$. Jadi, $$\sum_{\substack{k\in{\mathbb N}\\k\mid p-1}} \psi(k) = p-1\ .$$ Selain itu, menurut Teorema Gauss 5.5 , $$\sum_{\substack{k\in{\mathbb N}\\k\mid p-1}} \phi(k) = p-1\ .$$

Dengan demikian, $$\sum_{\substack{k\in{\mathbb N}\\k\mid p-1}} \phi(k) = \sum_{\substack{k\in{\mathbb N}\\k\mid p-1}} \psi(k)\ .$$ Sekarang cukup ditunjukkan bahwa $\psi(k)\le\phi(k)$ untuk setiap $k\in{\mathbb N}$ yang membagi $p-1$. Karena kedua jumlah berhingga di atas sama, ketaksamaan tersebut kemudian harus berupa kesamaan untuk setiap $k$.

Ambil $k\in{\mathbb N}$ dengan $k\mid p-1$. Jika $\psi(k)=0$, tidak ada unsur berorde $k$, dan tentu saja $\psi(k)\le\phi(k)$ karena $\phi(k)>0$.

Sekarang misalkan $\psi(k)>0$, sehingga terdapat unsur $a$ berorde $k$ dalam ${\mathbb Z}/p{\mathbb Z}$. Untuk setiap $n\in{\mathbb N}$, $(a^n)^k=(a^k)^n\equiv1^n\equiv1\pmod{p}$. Jadi, $a,\dots,a^k$ merupakan $k$ unsur berbeda dalam ${\mathbb Z}/p{\mathbb Z}$ yang semuanya memenuhi

$$x^k-1\equiv0\pmod{p}\ .$$ Menurut Teorema 5.10, kongruensi ini mempunyai tepat $k$ solusi. Dengan demikian, $a,\dots,a^k$ merupakan seluruh solusinya. Di antara solusi tersebut terdapat semua unsur ${\mathbb Z}/p{\mathbb Z}$ yang berorde $k$ , serta mungkin unsur berorde pembagi $k$.

Teorema 5.4 menentukan secara tepat orde unsur-unsur $a,\dots,a^k$: orde $a^\ell$ adalah $$\frac{\operatorname{ord}_p(a)}{\gcd(\operatorname{ord}_p(a),\ell)}=\frac{k}{\gcd(k,\ell)}\ .$$

Jadi, unsur-unsur ${\mathbb Z}/p{\mathbb Z}$ berorde $k$ adalah tepat unsur $a^\ell$ dengan $1\le\ell\le k$ dan $\gcd(k,\ell)=1$. Banyaknya tepat $\phi(k)$; dengan kata lain, $\psi(k)=\phi(k)$. ◻

Bukti. Gunakan $d=p-1$ dalam teorema sebelumnya. ◻

Bukti. Kita akan membuktikan dengan induksi pada $k$ bahwa, untuk setiap bilangan ganjil $a$, $$a^{2^{k-2}}\equiv1\pmod{2^k}$$ Untuk kasus dasar $k=3$, perhatikan semua kelas kongruensi dalam ${\mathbb Z}/8{\mathbb Z}$ yang mempunyai wakil ganjil beserta kuadrat kelas-kelas tersebut: $$[1]_8^2=[1]_8,\qquad[3]_8^2=[9]_8=[1]_8,\qquad[5]_8^2=[25]_8=[1]_8, \text{\ \ \ \ \ dan\ \ \ \ \ \ }[7]_8^2=[49]_8=[1]_8\ .$$ Jadi, kasus dasar $k=3$ terbukti.

Sekarang andaikan pernyataan berlaku untuk nilai $k$, yang berarti bahwa untuk setiap $a$ ganjil, $$a^{2^{k-2}}\equiv1\pmod{2^k}\ .$$ Dengan kata lain, $\exists\ell\in{\mathbb Z}$ sedemikian sehingga $$a^{2^{k-2}}=2^k\ell+1\ .$$ Dengan menguadratkan kedua ruas, kita memperoleh $$a^{2^{k-1}}=\left(a^{2^{k-2}}\right)^2=\left(2^k\ell+1\right)^2= 2^{2k}\ell^2+2\cdot2^k\ell+1=2^{k+1}\left(2^{k-1}\ell^2+\ell\right)+1,$$ yang berarti $$a^{2^{(k+1)-2}}=a^{2^{k-1}}\equiv1\pmod{2^{(k+1)}}\ .$$

Dengan demikian, bukti induktif bagi pernyataan awal selesai. Perhatikan bahwa untuk setiap $a$ ganjil, atau dengan kata lain setiap $a\in({\mathbb Z}/2^k{\mathbb Z})^*$, Teorema 5.1 memberikan $\operatorname{ord}_{2^k}(a)\mid2^{k-2}$, sehingga $\operatorname{ord}_{2^k}(a)\le2^{k-2}<2^{k-1}$. Jadi, $2^k$ tidak mempunyai akar primitif: akar semacam itu harus berupa bilangan ganjil berorde $\phi(2^k)=2^{k-1}$. ◻