Dalam teori bilangan, Fungsi phi Euler (bahasa Inggris: Euler's totient function) adalah Fungsi yang menghitung bilangan bulat positif hingga diberikan bilangan bulat n {\displaystyle n} yang prima nisbi dengan n {\displaystyle n} . Fungsi ini ditulis dengan menggunakan huruf Yunani, phi, yang dilambangkan sebagai φ ( m ) {\displaystyle \varphi (m)} atau ϕ ( m ) {\displaystyle \phi (m)} menyatakan kardinal himpunan bilangan asli 1 ≤ n ≤ m {\displaystyle 1\leq n\leq m} dimana gcd ( m , n ) = 1 {\displaystyle \gcd(m,n)=1} . Bilangan bulat positif yang < 9 adalah 1, 2, 3, 4, 5, 6, 7, 8. Diantara bilangan-bilangan tersebut yang saling prima terhadap 9 adalah 1, 2, 4, 5, 7, 8, maka banyaknya bilangan yang saling prima terhadap 9 adalah sebanyak 6 sehingga φ(9) = 6. Fungsi ini dikemukakan oleh Leonhard Euler (L. 15 April 1707, Swiss. w. 18 September 1783, Rusia).

Identitas

Terdapat beberapa identitas mengenai Fungsi Euler phi, diantaranya: φ ( 1 ) = 0 {\displaystyle \varphi (1)=0} , φ ( 2 ) = 1 {\displaystyle \varphi (2)=1} φ ( p ) = p − 1 {\displaystyle \varphi (p)=p-1} , untuk p {\displaystyle p} adalah bilangan prima φ ( m n ) = φ ( m ) φ ( n ) {\displaystyle \varphi (mn)=\varphi (m)\varphi (n)} jika gcd ( m , n ) = 1 {\displaystyle \gcd(m,n)=1} φ ( p n ) = p n − 1 ( p − 1 ) {\displaystyle \varphi (p^{n})=p^{n-1}(p-1)} φ ( ∏ i = 1 n p i ) = ∏ i = 1 n ( p i − 1 ) {\displaystyle \varphi \left(\prod _{i=1}^{n}p_{i}\right)=\prod _{i=1}^{n}\left(p_{i}-1\right)}

Rumus lainnya

Apabila rumus lain mengenai fungsi Euler phi, diantaranya a ∣ b ⟹ φ ( a ) ∣ φ ( b ) {\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)} n ∣ φ ( a n − 1 ) {\displaystyle n\mid \varphi (a^{n}-1)} , untuk setiap a , n > 1 {\displaystyle a,n>1} φ ( m , n ) = φ ( m ) ⋅ φ ( n ) {\displaystyle \varphi (m,n)=\varphi (m)\cdot \varphi (n)} Perhatikan kasus khusus φ ( 2 m ) = { 2 φ ( m ) jika m adalah genap φ ( m ) jika m adalah ganjil {\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ jika }}m{\text{ adalah genap}}\\\varphi (m)&{\text{ jika }}m{\text{ adalah ganjil}}\end{cases}}} φ ( n m ) = n m − 1 φ ( n ) {\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)} φ ( lcm ⁡ ( m , n ) ) ⋅ φ ( gcd ⁡ ( m , n ) ) = φ ( m ) ⋅ φ ( n ) {\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)} Bandingkan dengan rumus lcm ⁡ ( m , n ) ⋅ gcd ⁡ ( m , n ) = m ⋅ n {\displaystyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n} (Lihat kelipatan persekutuan terkecil.) φ(n) genap untuk n ≥ 3. Selain itu, jika n memiliki r faktor prima ganjil yang berbeda, 2r | φ(n) Untuk a > 1 dan n > 6 sehingga 4 ∤ n terdapat l ≥ 2n sedemikian sehingga l | φ(an − 1). φ ( n ) n = φ ( rad ⁡ ( n ) ) rad ⁡ ( n ) {\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}} di mana rad ⁡ ( n ) {\displaystyle \operatorname {rad} (n)} adalah radikal dari n {\displaystyle n} . ∑ d ∣ n μ 2 ( d ) φ ( d ) = n φ ( n ) {\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}} ∑ 1 ≤ k ≤ n ( k , n ) = 1 k = 1 2 n φ ( n ) {\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)} , untuk n > 1 {\displaystyle n>1} ∑ k = 1 n φ ( k ) = 1 2 ( 1 + ∑ k = 1 n μ ( k ) ⌊ n k ⌋ 2 ) = 3 π 2 n 2 + O ( n ( log ⁡ n ) 2 3 ( log ⁡ log ⁡ n ) 4 3 ) {\displaystyle \sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)} ( dikutip dalam) ∑ k = 1 n φ ( k ) k = ∑ k = 1 n μ ( k ) k ⌊ n k ⌋ = 6 π 2 n + O ( ( log ⁡ n ) 2 3 ( log ⁡ log ⁡ n ) 4 3 ) {\displaystyle \sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)} ∑ k = 1 n k φ ( k ) = 315 ζ ( 3 ) 2 π 4 n − log ⁡ n 2 + O ( ( log ⁡ n ) 2 3 ) {\displaystyle \sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)} ∑ k = 1 n 1 φ ( k ) = 315 ζ ( 3 ) 2 π 4 ( log ⁡ n + γ − ∑ p prime log ⁡ p p 2 − p + 1 ) + O ( ( log ⁡ n ) 2 3 n ) {\displaystyle \sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)} (dengan γ {\displaystyle \gamma } adalah konstanta Euler–Mascheroni). ∑ gcd ⁡ ( k , m ) = 1 1 ≤ k ≤ n 1 = n φ ( m ) m + O ( 2 ω ( m ) ) {\displaystyle \sum _{\stackrel {1\leq k\leq n}{\operatorname {gcd} (k,m)=1}}\!\!\!\!1=n{\frac {\varphi (m)}{m}}+O\left(2^{\omega (m)}\right)} dimana m > 1 {\displaystyle m>1} adalah bilangan bulat positif dan ω ( m ) {\displaystyle \omega (m)} adalah jumlah faktor prima yang berbeda dari m {\displaystyle m} .

Beberapa bilangan

100 nilai pertama (barisan A000010 pada OEIS) ditampilkan pada tabel dan grafik di bawah ini: Dalam grafik di kanan atas baris y = n − 1 {\displaystyle y=n-1} adalah batas atas valid untuk semua n {\displaystyle n} selain satu, dan dicapai jika dan hanya jika n {\displaystyle n} adalah bilangan prima. Batas bawah sederhana adalah φ ( n ) ≥ n 2 {\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}} , yang agak longgar: sebenarnya, lower limit dari grafik sebanding dengan n log ⁡ log ⁡ n {\displaystyle {\frac {n}{\log \log n}}} .

Fungsi pembangkit

Deret Dirichlet untuk φ ( n ) {\displaystyle \varphi (n)} dapat ditulis dalam istilah Fungsi zeta Riemann sebagai: ∑ n = 1 ∞ φ ( n ) n s = ζ ( s − 1 ) ζ ( s ) . {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.} Fungsi pembangkit deret Lambert adalah ∑ n = 1 ∞ φ ( n ) q n 1 − q n = q ( 1 − q ) 2 {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}} konvergen untuk | q | < 1 {\displaystyle |q|<1} . Keduanya dibuktikan dengan manipulasi deret dasar dan rumus untuk φ ( n ) {\displaystyle \varphi (n)} .

Rasio bilangan berurutan

Pada tahun 1950 Somayajulu membuktikan lim inf φ ( n + 1 ) φ ( n ) = 0 {\displaystyle \lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}=0} dan lim sup φ ( n + 1 ) φ ( n ) = ∞ {\displaystyle \lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}=\infty } Pada tahun 1954 Schinzel dan Sierpiński memperkuat ini, membuktikan bahwa himpunan { φ ( n + 1 ) φ ( n ) , n = 1 , 2 , … } {\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}} adalah padat dalam bilangan riil positif. Mereka pun membuktikannya bahwa himpunan { φ ( n ) n , n = 1 , 2 , … } {\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}} padat dalam interval ( 0 , 1 ) {\displaystyle (0,1)} .

Lihat pula

Fungsi Carmichael Konjektur Duffin–Schaeffer Generalisasi teorema kecil Fermat Bilangan komposit tinggi Grup perkalian bilangan bulat modulo n Jumlah Ramanujan Fungsi penjumlahan total

Catatan

Referensi

Pranala luar

Hazewinkel, Michiel, ed. (2001) [1994], "Totient function", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 Euler's phi Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative Diarsipkan 2021-02-28 di Wayback Machine. Euler's totient function calculator in JavaScript — up to 20 digits Diarsipkan 2023-07-06 di Wayback Machine. Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Diarsipkan 2021-01-16 di Wayback Machine. Plytage, Loomis, Polhill Summing Up The Euler phi Function Diarsipkan 2023-05-23 di Wayback Machine.