Subbab 7.5 Fungsi \(\phi\) Euler
Setelah membaca dua bagian sebelumnya, Anda mungkin bertanya-tanya mengapa kami menyatakan
Prinsip Inklusi–Eksklusi dengan cara yang begitu abstrak, sebab dalam contoh-contoh tersebut
\(N(S)\) hanya bergantung pada banyaknya anggota
\(S\text{,}\) bukan pada isinya. Pada bagian ini, kami menyajikan sebuah contoh penting ketika nilai
\(N(S)\) memang bergantung pada
\(S\text{.}\) Meskipun demikian, kita dapat melakukan reduksi untuk memperoleh hasil akhir yang berguna. Dalam pembahasan berikut, misalkan
\(\posints\) menyatakan himpunan bilangan bulat positif.
Untuk bilangan bulat positif \(n\ge2\text{,}\) tetapkan
\begin{equation*}
\phi(n)=|\{m\in \posints: m\le n, \gcd(m,n)=1\}|.
\end{equation*}
Fungsi ini biasanya disebut fungsi \(\phi\) Euler atau fungsi totien Euler dan memiliki banyak kaitan dengan teori bilangan. Di sini kita tidak akan berfokus pada aspek-aspek teori bilangannya, melainkan hanya pada cara menghitung \(\phi(n)\) secara efisien untuk setiap \(n\text{.}\)
Sebagai contoh,
\(\phi(12)=4\) karena satu-satunya bilangan dalam
\(\{1,2,\dots,12\}\) yang relatif prima terhadap
\(12\) adalah
\(1\text{,}\) \(5\text{,}\) \(7\text{,}\) dan
\(11\text{.}\) Sebagai contoh kedua,
\(\phi(9)=6\) karena
\(1\text{,}\) \(2\text{,}\) \(4\text{,}\) \(5\text{,}\) \(7\text{,}\) dan
\(8\) relatif prima terhadap
\(9\text{.}\) Di sisi lain,
\(\phi(p)=p-1\) jika
\(p\) merupakan bilangan prima. Misalkan Anda diminta menghitung
\(\phi(321974)\text{.}\) Bagaimana Anda akan melakukannya?
Dalam
Bab 3, kita membahas prosedur rekursif untuk menentukan faktor persekutuan terbesar dari dua bilangan bulat dan menulis kode untuk mengerjakan tugas tersebut. Mari kita andaikan bahwa kita memiliki fungsi
gcd(m,n) yang mengembalikan faktor persekutuan terbesar dari bilangan bulat
m dan
n. (Untungnya, SageMath sudah dilengkapi fungsi semacam itu.) Dengan demikian, kita dapat menghitung
\(\phi(n)\) menggunakan cuplikan kode berikut:
Ketika dijalankan, kode di atas hampir seketika memberikan jawaban
\(\phi(321974) = 147744\text{.}\) (Seperti biasa, dalam versi web buku ini, Anda dapat mengubah nilai
321974 untuk menghitung nilai
\(\phi\) bagi bilangan bulat lain. Namun, jika nilai
n yang Anda masukkan terlalu besar, Anda mungkin menghadapi kendala memori yang diberlakukan oleh Sage Cell Server yang digunakan buku ini. Sebagai contoh, ketika buku ini ditulis, upaya menghitung
\(\phi(319572943)\) menghasilkan galat. Anda mungkin lebih berhasil jika menjalankan kode tersebut secara langsung di
CoCalc atau pada instalasi lokal SageMath.)
Mengingat kendala-kendala tersebut, bagaimana kita dapat menghitung
\(\phi(1369122257328767073)\text{?}\)
Jelaslah bahwa program tersebut tidak berguna untuk menangani bilangan raksasa ini! Program itu bukan hanya melakukan iterasi sebanyak
\(n-2\) kali, melainkan juga menjalankan rekursi pada setiap iterasi. Untungnya, prinsip inklusi–eksklusi datang menolong kita.
Teorema 7.14.
Misalkan \(n\ge2\) merupakan bilangan bulat positif dan andaikan \(n\) memiliki \(m\) faktor prima yang berbeda, yaitu \(p_1\text{,}\) \(p_2,\dots,p_m\text{.}\) Maka
\begin{equation}
\phi(n) = n\prod_{i = 1}^{m}\frac{p_i-1}{p_i}.\tag{7.5.1}
\end{equation}
Bukti kita untuk
Teorema 7.14 memerlukan proposisi elementer berikut, yang buktinya kita serahkan sebagai latihan.
Proposisi 7.15.
Misalkan \(n\ge2\text{,}\) \(k\ge1\text{,}\) dan misalkan \(p_1,p_2,\dots,p_k\) merupakan bilangan prima berbeda yang masing-masing membagi \(n\) tanpa sisa. Maka banyaknya bilangan bulat dalam \(\{1,2,\dots,n\}\) yang habis dibagi oleh masing-masing dari \(k\) bilangan prima tersebut adalah
\begin{equation*}
\frac{n}{p_1p_2\dots p_k}.
\end{equation*}
Bukti.
Kita menyajikan argumennya untuk kasus
\(m=3\text{.}\) Hasil selengkapnya diperoleh melalui perluasan yang mudah.
\begin{align*}
\phi(n) \amp = n-\left(\frac{n}{p_1}+\frac{n}{p_2}+
\frac{n}{p_3}\right) +\left(\frac{n}{p_1p_2}+\frac{n}{p_1p_3}+
\frac{n}{p_2p_3}\right)-\frac{n}{p_1p_2p_3}\\
\amp = n \frac{p_1p_2p_3 -(p_2p_3+p_1p_3+p_1p_2)+
(p_3+p_2+p_1) - 1}{p_1p_2p_3}\\
\amp =n \frac{p_1-1}{p_1}\frac{p_2-1}{p_2}
\frac{p_3-1}{p_3}.
\end{align*}
Contoh 7.16.
SageMath melaporkan bahwa
\begin{equation*}
1369122257328767073 = (3)^3(11)(19)^4(31)^2(6067)^2
\end{equation*}
merupakan faktorisasi \(1369122257328767073\) menjadi faktor-faktor prima. Dari sini diperoleh bahwa
\begin{equation*}
\phi(1369122257328767073) = 1369122257328767073
\,\,\frac{2}{3}\,\frac{10}{11}\,\frac{18}{19}\,\frac{30}{31}\,\frac{6066}{6067}.
\end{equation*}
Dengan demikian, SageMath dengan cepat melaporkan bahwa
\begin{equation*}
\phi(1369122257328767073) =760615484618973600.
\end{equation*}
Contoh 7.17.
Amanda dan Bruce menerima tantangan yang sama dari profesor mereka, yaitu mencari \(\phi(n)\) ketika
\begin{align*}
n = \amp 31484972786199768889479107860964368171543984609017931\\
\amp 39001922159851668531040708539722329324902813359241016\\
\amp 93211209710523.
\end{align*}
Namun, profesor tersebut juga memberi tahu Amanda bahwa \(n=p_1p_2\) merupakan hasil kali dua bilangan prima besar, dengan
\begin{align*}
p_1 \amp = 470287785858076441566723507866751092927015824834881906763507
\end{align*}
dan
\begin{align*}
p_2 \amp = 669483106578092405936560831017556154622901950048903016651289.
\end{align*}
Apakah informasi ini memiliki nilai khusus bagi Amanda? Apakah informasi tersebut benar-benar membuat tugasnya lebih mudah daripada tugas Bruce? Apakah kedudukan mereka akan menjadi setara jika profesor itu memberi tahu Bruce bahwa \(n\) merupakan hasil kali dua bilangan prima?
