Menyelesaikan Modulo dengan Fungsi Euler Phi
Hallo Sobat.
Pada kesempatan kali ini kita akan membahas tentang Fungsi Euler Phi dan Teorema Euler. Yakni terkait tentang materi Teori Bilangan. Oke kita menuju ke pembahasannya.
Definisi : $a$ dan $b$ dikatakan relatif prima jika $gcd(a,b)=1$. Contohnya $2$ dan $3$ saling relatif prima.
Definisi : Fungsi $\varphi$ didefinisikan sebagai $\varphi(n)$ yang menyatakan banyaknya bilangan asli yang kurang dari atau sama dengan $n$ dan relatif prima dengan $n$. Contoh : $\varphi(1)=1$, $\varphi(2)=1, \varphi(3)=2$ dll.
Sifat 1 : Jika $p$ adalah bilangan prima maka $\varphi(p)=p-1$.
Karena faktor prima dari $p$ hanya $1$ dan $p$. Kita tau bahwa $1$ dan $p$ relatif prima. Maka bilangan asli yang kurang dari atau sama dengan $p$ dan relatif prima dengan $p$ adalah $1,2,3,...,p-1$. Sehingga $\varphi(p)=p-1$
Sifat 2 : Jika $p$ adalah bilangan prima, maka $\forall k\in\mathbb{N}$.
$\varphi(p^k)=p^{k-1}(p-1)$
Karena $p,2p,3p,\cdots,p^{k-1}p$ itu tidak relatif prima dengan $p^k$ maka banyak bilangan asli yang kurang dari atau sama dengan $p^k$ dan relatif prima dengan $p^k$ adalah $p^k-p^{k-1}=p^{k-1}(p-1)$
Contoh : $\varphi(216)=\varphi(2^8)=2^7(2-1)=2^7$
Sifat 3 : Misalkan $a,b$ relatif prima maka $\varphi(ab)=\varphi(a)\varphi(b)$
Contoh : $\varphi(10)=\varphi(2.5)$
Karena $2$ dan $5$ relatif prima maka $\varphi(10)=\varphi(2.5)=\varphi(2)\varphi(5)=1\times 4=4$
Secara umum, misalkan $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$
dengan $p_1,p_2,\cdots ,p_k$ merupakan bilangan prima yang berbeda, maka
$\begin{align*}\varphi(n) &=\varphi(p_1^{\alpha_1})\cdots \varphi(p_k^{\alpha_k})\\ =&p_1^{\alpha_1-1}(p_1-1)\cdots p_k^{\alpha_k-1}(p_k-1)\\ =&p_1^{\alpha_1-1}\cdots p_k^{\alpha_k-1}(p_1-1)\cdots (p_k-1)\\ =&\frac{p_1^{\alpha_1}\cdots p_k^{\alpha_k}}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)\\ &=\frac{n}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)\\ =&n\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)\end{align*}$
Sehingga kita dapatkan
Sifat 4 : Jika $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ maka
$\varphi(n)=\frac{n}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)$
Sebagai contoh nilai dari $\begin{align*}\varphi(180) &=\varphi(2^2.3^2.5)\\ &=\frac{180}{2.3.5}(2-1)(3-1)(5-1)\\ &=6.1.2.4\\ &=48\end{align*}$
Sekarang kita sudah paham tentang fungsi phi euler. Kita akan menggunakannya pada konsep modulo.
Teorema Euler Phi : Untuk $m$ bilangan bulat positif dan $a$ bilangan bulat dengan $gcd(m,a)=1$ maka $a^{\varphi(m)}\equiv 1\ mod\ m$.
Teorema Euler ini bisa kita gunakan dalam mencari sisa atau modulo dari suatu pembagian bilangan bulat, juga bisa diaplikasikan dalam mencari digit bilangan, dan lain lain.
Contoh Soal :
1) Tentukan digit terakhir dari $7^{100}$
Jawab : Kita tahu dengan menggunakan teorema euler phi maka
$7^{\varphi(10)}=7^4\equiv 1\ mod\ 10$
$7^{100}=\left(7^4\right)^{25}\equiv 1\ mod\ 10$
Dengan demikian digit terakhir dari $7^{100}$ adalah $1$.
2) Berapakah sisa pembagian dari $5^{1000}$ oleh $18$
Jawab : Karena $18=2.3^2$ maka $\varphi(18)=6$.
Sehingga menurut teorema euler phi $5^6\equiv 1\ mod\ 18$
Sehingga diperoleh
$\begin{align*}5^{1000}=\left(5^6\right)^{166}5^4 &\equiv 5^4\ mod\ 18\\ &\equiv 625\ mod\ 18\\ &\equiv 13\ mod\ 18\end{align*}$
Jadi, sisa pembagian dari $5^{1000}$ oleh $18$ adalah $13$
3) Jika $a$ dan $b$ relatif prima. Buktikan bahwa :
$a^{\varphi(b)}+b^{\varphi(a)}\equiv 1\ mod\ ab$
Jawab : Berdasarkan teorema euler bahwa
$a^{\varphi(b)}\equiv 1\ mod\ b$
$b^{\varphi(a)}\equiv 1\ mod\ a$
Jadi kita dapatkan
$a^{\varphi(b)}-1=kb$, untuk suatu bilangan bulat $k$
$b^{\varphi(a)}-1=la$, untuk suatu bilangan bulat $l$
Jadi $(a^{\varphi(b)}-1)(b^{\varphi(a)}-1)=mab$, untuk suatu bilangan bulat $m$. Jadi bisa ditulis
$a^{\varphi(b)}b^{\varphi(a)}-a^{\varphi(b)}-b^{\varphi(a)}+1\equiv 0\ mod\ ab$
$-a^{\varphi(b)}-b^{\varphi(a)}+1\equiv 0\ mod\ ab$
$-\left(a^{\varphi(b)}+b^{\varphi(a)}\right)\equiv -1\ mod\ ab$
$a^{\varphi(b)}+b^{\varphi(a)}\equiv 1\ mod\ ab$
Terbukti.
Pada kesempatan kali ini kita akan membahas tentang Fungsi Euler Phi dan Teorema Euler. Yakni terkait tentang materi Teori Bilangan. Oke kita menuju ke pembahasannya.
Definisi : $a$ dan $b$ dikatakan relatif prima jika $gcd(a,b)=1$. Contohnya $2$ dan $3$ saling relatif prima.
Definisi : Fungsi $\varphi$ didefinisikan sebagai $\varphi(n)$ yang menyatakan banyaknya bilangan asli yang kurang dari atau sama dengan $n$ dan relatif prima dengan $n$. Contoh : $\varphi(1)=1$, $\varphi(2)=1, \varphi(3)=2$ dll.
Sifat 1 : Jika $p$ adalah bilangan prima maka $\varphi(p)=p-1$.
Karena faktor prima dari $p$ hanya $1$ dan $p$. Kita tau bahwa $1$ dan $p$ relatif prima. Maka bilangan asli yang kurang dari atau sama dengan $p$ dan relatif prima dengan $p$ adalah $1,2,3,...,p-1$. Sehingga $\varphi(p)=p-1$
Sifat 2 : Jika $p$ adalah bilangan prima, maka $\forall k\in\mathbb{N}$.
$\varphi(p^k)=p^{k-1}(p-1)$
Karena $p,2p,3p,\cdots,p^{k-1}p$ itu tidak relatif prima dengan $p^k$ maka banyak bilangan asli yang kurang dari atau sama dengan $p^k$ dan relatif prima dengan $p^k$ adalah $p^k-p^{k-1}=p^{k-1}(p-1)$
Contoh : $\varphi(216)=\varphi(2^8)=2^7(2-1)=2^7$
Sifat 3 : Misalkan $a,b$ relatif prima maka $\varphi(ab)=\varphi(a)\varphi(b)$
Contoh : $\varphi(10)=\varphi(2.5)$
Karena $2$ dan $5$ relatif prima maka $\varphi(10)=\varphi(2.5)=\varphi(2)\varphi(5)=1\times 4=4$
Secara umum, misalkan $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$
dengan $p_1,p_2,\cdots ,p_k$ merupakan bilangan prima yang berbeda, maka
$\begin{align*}\varphi(n) &=\varphi(p_1^{\alpha_1})\cdots \varphi(p_k^{\alpha_k})\\ =&p_1^{\alpha_1-1}(p_1-1)\cdots p_k^{\alpha_k-1}(p_k-1)\\ =&p_1^{\alpha_1-1}\cdots p_k^{\alpha_k-1}(p_1-1)\cdots (p_k-1)\\ =&\frac{p_1^{\alpha_1}\cdots p_k^{\alpha_k}}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)\\ &=\frac{n}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)\\ =&n\left(1-\frac{1}{p_1}\right)\cdots \left(1-\frac{1}{p_k}\right)\end{align*}$
Sehingga kita dapatkan
Sifat 4 : Jika $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ maka
$\varphi(n)=\frac{n}{p_1\cdots p_k}(p_1-1)\cdots (p_k-1)$
Sebagai contoh nilai dari $\begin{align*}\varphi(180) &=\varphi(2^2.3^2.5)\\ &=\frac{180}{2.3.5}(2-1)(3-1)(5-1)\\ &=6.1.2.4\\ &=48\end{align*}$
Sekarang kita sudah paham tentang fungsi phi euler. Kita akan menggunakannya pada konsep modulo.
Teorema Euler Phi : Untuk $m$ bilangan bulat positif dan $a$ bilangan bulat dengan $gcd(m,a)=1$ maka $a^{\varphi(m)}\equiv 1\ mod\ m$.
Teorema Euler ini bisa kita gunakan dalam mencari sisa atau modulo dari suatu pembagian bilangan bulat, juga bisa diaplikasikan dalam mencari digit bilangan, dan lain lain.
Contoh Soal :
1) Tentukan digit terakhir dari $7^{100}$
Jawab : Kita tahu dengan menggunakan teorema euler phi maka
$7^{\varphi(10)}=7^4\equiv 1\ mod\ 10$
$7^{100}=\left(7^4\right)^{25}\equiv 1\ mod\ 10$
Dengan demikian digit terakhir dari $7^{100}$ adalah $1$.
2) Berapakah sisa pembagian dari $5^{1000}$ oleh $18$
Jawab : Karena $18=2.3^2$ maka $\varphi(18)=6$.
Sehingga menurut teorema euler phi $5^6\equiv 1\ mod\ 18$
Sehingga diperoleh
$\begin{align*}5^{1000}=\left(5^6\right)^{166}5^4 &\equiv 5^4\ mod\ 18\\ &\equiv 625\ mod\ 18\\ &\equiv 13\ mod\ 18\end{align*}$
Jadi, sisa pembagian dari $5^{1000}$ oleh $18$ adalah $13$
3) Jika $a$ dan $b$ relatif prima. Buktikan bahwa :
$a^{\varphi(b)}+b^{\varphi(a)}\equiv 1\ mod\ ab$
Jawab : Berdasarkan teorema euler bahwa
$a^{\varphi(b)}\equiv 1\ mod\ b$
$b^{\varphi(a)}\equiv 1\ mod\ a$
Jadi kita dapatkan
$a^{\varphi(b)}-1=kb$, untuk suatu bilangan bulat $k$
$b^{\varphi(a)}-1=la$, untuk suatu bilangan bulat $l$
Jadi $(a^{\varphi(b)}-1)(b^{\varphi(a)}-1)=mab$, untuk suatu bilangan bulat $m$. Jadi bisa ditulis
$a^{\varphi(b)}b^{\varphi(a)}-a^{\varphi(b)}-b^{\varphi(a)}+1\equiv 0\ mod\ ab$
$-a^{\varphi(b)}-b^{\varphi(a)}+1\equiv 0\ mod\ ab$
$-\left(a^{\varphi(b)}+b^{\varphi(a)}\right)\equiv -1\ mod\ ab$
$a^{\varphi(b)}+b^{\varphi(a)}\equiv 1\ mod\ ab$
Terbukti.
