Lihat sumber Fungsi phi Euler

[[File:EulerPhi.svg|thumb|right|280px|EulerPhi]]

[[Gambar:EulerPhi.svg|thumb|Seribu nilai pertama . Titik di garis atas adalah  bila  adalah bilangan prima, yaitu <ref>[https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function Euler's totient function]. ''Khan Academy''.</ref>]]
Dalam [[teori bilangan]], untuk suatu [[bilangan asli]] <math>n</math>, '''fungsi phi Euler''' (), dilambangkan dengan menggunakan huruf Yunani [[Fi|phi]] sebagai <math>\varphi(n)</math> atau <math>\phi(n)</math>, menyatakan banyak bilangan bulat positif yang kurang dari <math>n</math> dan [[Koprima (bilangan)|saling prima]] dengan <math>n</math>.

Sebagai contoh, perhatikan bahwa terdapat enam bilangan bulat positif yang kurang dari 9 dan saling prima dengan 9 adalah 1, 2, 4, 5, 7, 8. Oleh sebab itu didapat bahwa''φ''(9) = 6.

Fungsi ini dikemukakan oleh [[Leonhard Euler]] (L. 15 April 1707, [[Konfederasi Swiss Lama|Swiss.]] w. 18 September 1783, [[Kekaisaran Rusia|Rusia]]).

== Definisi dan contoh ==
Fungsi phi Euler didefinisikan sebagai  <math>\varphi \colon \N^+ \to \N^+</math>,

<math>\varphi(n) \; := \; \Big| \{a\in\N \, \mid \, 1 \le a \le n \land \operatorname{FPB}(a,n) = 1\} \Big|</math>

dengan |·| menyatakan [[kardinalitas]] himpunan dan FPB adalah [[faktor persekutuan terbesar]] antara ''a'' dan ''n.'' 

Sebagai contoh:

* , karena diantara bilangan 1 sampai 1, terdapat satu bilangan, yaitu 1, yang saling prima dengan 1;
* , karena diantara bilangan 1 sampai 8, terdapat empat bilangan, yaitu 1, 3, 5, dan 7, yang saling prima dengan 8;
* , karena diantara bilangan 1 sampai 12, terdapat empat bilangan 1, 5, 7, 11, 13, dan 17, yang saling prima dengan 18;
* , karena 67 adalah bilangan prima, maka 67 akan saling prima dengan keenam puluh enam bilangan antara 1 sampai 67 selain 67 itu sendiri. 

Berikut nilai fungsi phi Euler untuk 99 bilangan asli pertama (untuk bilangan berikutnya lihat barisan  [[oeis:A000010|A000010]] di [[On-Line Encyclopedia of Integer Sequences|OEIS]]):
{| class="wikitable"
!<math>\varphi(n)</math>
!+0
!+1
!+2
!+3
!+4
!+5
!+6
!+7
!+8
!+9
|-
!0+
|&nbsp;
|1
|1
|2
|2
|4
|2
|6
|4
|6
|-
!10+
|4
|10
|4
|12
|6
|8
|8
|16
|6
|18
|-
!20+
|8
|12
|10
|22
|8
|20
|12
|18
|12
|28
|-
!30+
|8
|30
|16
|20
|16
|24
|12
|36
|18
|24
|-
!40+
|16
|40
|12
|42
|20
|24
|22
|46
|16
|42
|-
!50+
|20
|32
|24
|52
|18
|40
|24
|36
|28
|58
|-
!60+
|16
|60
|30
|36
|32
|48
|20
|66
|32
|44
|-
!70+
|24
|70
|24
|72
|36
|40
|36
|60
|24
|78
|-
!80+
|32
|54
|40
|82
|24
|64
|42
|56
|40
|88
|-
!90+
|24
|72
|44
|60
|46
|72
|32
|96
|42
|60
|}
Dalam grafik di kanan atas baris <math>y = n - 1</math> adalah [[batas atas]] valid untuk semua <math>n</math> selain satu, dan dicapai jika dan hanya jika <math>n</math> adalah [[bilangan prima]]. Batas bawah sederhana adalah <math>\varphi(n) \ge \sqrt{\frac{n}{2}} </math>, yang agak longgar: sebenarnya, [[Limit superior dan limit inferior|lower limit]] dari grafik sebanding dengan <math>\frac{n}{\log \log n}</math>.<ref>[https://id.wikipedia.org/w/index.php?title=Fungsi+phi+Euler&oldid=29299396 sumber pada Wikipedia bahasa Indonesia]</ref>

== Sifat fungsi ==
=== Sifat perkalian fungsi phi Euler ===
Fungsi phi Euler adalah [[fungsi perkalian]] sehingga sehingga untuk dua bilangan asli <math>m,n</math> yang saling prima berlaku<blockquote><math>\varphi(mn) = \varphi(m) \varphi(n)</math></blockquote>

== Perhitungan ==
* <math>\varphi(1) = 0</math>, <math>\varphi(2) = 1</math>
* <math>\varphi(p) = p - 1</math>, untuk <math>p</math> adalah bilangan prima

* jika <math>\gcd(m,n) = 1</math>
* <math>\varphi(p^n) = p^{n - 1} (p - 1)</math>
* <math>\varphi \left(\prod_{i = 1}^n p_i \right) = \prod_{i = 1}^n \left( p_i - 1 \right)</math>

== Rumus lainnya ==
Apabila rumus lain mengenai fungsi Euler phi, di antaranya
* <math>a\mid b \implies \varphi(a)\mid\varphi(b)</math>
* <math> n \mid \varphi(a^n-1)</math>, untuk setiap <math>a, n > 1</math>
* <math>\varphi(m,n) = \varphi(m) \cdot \varphi(n)</math>
:Perhatikan kasus khusus
:* <math>\varphi(2m) = \begin{cases}
2\varphi(m) &\text{ jika } m \text{ adalah genap} \\
\varphi(m) &\text{ jika } m \text{ adalah ganjil}
\end{cases}</math>
:* <math>\varphi\left(n^m\right) = n^{m-1}\varphi(n)</math>
:* <math>\varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)</math>  Bandingkan dengan rumus
:* <math>\operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n</math>

:(Lihat [[kelipatan persekutuan terkecil]].)

*  genap untuk . Selain itu, jika  memiliki  faktor prima ganjil yang berbeda, 
* Untuk  dan  sehingga  terdapat  sedemikian sehingga .
* <math>\frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}</math>
:di mana <math>\operatorname{rad}(n)</math> adalah [[bilangan bulat radikal|radikal dari <math>n</math>]].
* <math>\sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}</math>&nbsp;<ref>Dineva (dalam referensi eksternal), prop. 1</ref>
* <math>\sum_{1\le k\le n \atop (k,n)=1}\!\!k = \tfrac12 n\varphi(n)</math>, untuk <math>n > 1</math>
* <math>\sum_{k=1}^n\varphi(k) = \tfrac12 \left(1+ \sum_{k=1}^n \mu(k)\left\lfloor\frac{n}{k}\right\rfloor^2\right)
=\frac3{\pi^2}n^2+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right)</math>&nbsp;(<ref>Arnold Walfisz. ''Weylsche Exponentialsummen in der neueren Zahlentheorie''. VEB Deutscher Verlag der Wissenschaften. 1963. Vol. 16.</ref> dikutip dalam<ref>G. Lomadse. [http://matwbn.icm.edu.pl/ksiazki/aa/aa10/aa10111.pdf The scientific work of Arnold Walfisz]. ''Acta Arithmetica''. Vol. 10 (3). hlm. 227–237.</ref>)

* <math>\sum_{k=1}^n\frac{\varphi(k)}{k} = \sum_{k=1}^n\frac{\mu(k)}{k}\left\lfloor\frac{n}{k}\right\rfloor=\frac6{\pi^2}n+O\left((\log n)^\frac23(\log\log n)^\frac43\right)</math>&nbsp;<ref>Arnold Walfisz. ''Weylsche Exponentialsummen in der neueren Zahlentheorie''. VEB Deutscher Verlag der Wissenschaften. 1963. Vol. 16.</ref>
* <math>\sum_{k=1}^n\frac{k}{\varphi(k)} = \frac{315\,\zeta(3)}{2\pi^4}n-\frac{\log n}2+O\left((\log n)^\frac23\right)</math>&nbsp;<ref>R. Sitaramachandrarao. ''On an error term of Landau II''. ''Rocky Mountain J. Math''. 1985. Vol. 15. hlm. 579–588.</ref>
* <math>\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)^\frac23}n\right)</math>&nbsp;<ref>R. Sitaramachandrarao. ''On an error term of Landau II''. ''Rocky Mountain J. Math''. 1985. Vol. 15. hlm. 579–588.</ref>

:(dengan <math>\gamma</math> adalah [[konstanta Euler–Mascheroni]]).

* <math>\sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(m)}{m} + O \left ( 2^{\omega(m)} \right )</math>
:dimana <math>m > 1</math> adalah bilangan bulat positif dan <math>\omega(m)</math> adalah jumlah faktor prima yang berbeda dari <math>m</math>.<ref>Bordellès di pranala luar</ref>

== Fungsi pembangkit ==
[[Deret Dirichlet]] untuk <math>\varphi(n)</math> dapat ditulis dalam istilah [[fungsi zeta Riemann]] sebagai:<ref>[https://id.wikipedia.org/w/index.php?title=Fungsi+phi+Euler&oldid=29299396 sumber pada Wikipedia bahasa Indonesia]</ref>
:<math>\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.</math>

Fungsi pembangkit [[deret Lambert]] adalah<ref>[https://id.wikipedia.org/w/index.php?title=Fungsi+phi+Euler&oldid=29299396 sumber pada Wikipedia bahasa Indonesia]</ref>

:<math>\sum_{n=1}^{\infty} \frac{\varphi(n) q^n}{1-q^n}= \frac{q}{(1-q)^2}</math>

konvergen untuk <math>|q| < 1</math>.

Keduanya dibuktikan dengan manipulasi deret dasar dan rumus untuk <math>\varphi(n)</math>.

== Rasio bilangan berurutan ==
Pada tahun 1950 Somayajulu membuktikan<ref>Ribenboim, p.38</ref><ref>Sándor, Mitrinović & Crstici (2006) p.16</ref>

:<math>\lim\inf \frac{\varphi(n+1)}{\varphi(n)} = 0</math> dan <math>\lim\sup \frac{\varphi(n+1)}{\varphi(n)}= \infty
</math>

Pada tahun 1954 [[Andrzej Schinzel|Schinzel]] dan [[Wacław Sierpiński|Sierpiński]] memperkuat ini, membuktikan<ref>Ribenboim, p.38</ref><ref>Sándor, Mitrinović & Crstici (2006) p.16</ref> bahwa himpunan

:<math>\left\{\frac{\varphi(n+1)}{\varphi(n)},\;\;n = 1,2,\ldots\right\}</math> 

adalah [[Himpunan padat|padat]] dalam [[bilangan riil]] positif. Mereka pun membuktikannya<ref>Ribenboim, p.38</ref> bahwa himpunan

:<math>\left\{\frac{\varphi(n)}{n},\;\;n = 1,2,\ldots\right\}</math>

padat dalam interval <math>(0,1)</math>.

== Lihat pula ==
* [[Fungsi Carmichael]]
* [[Konjektur Duffin–Schaeffer]]
*[[Teorema kecil Fermat#Generalisasi|Generalisasi teorema kecil Fermat]]
* [[Bilangan komposit tinggi]]
* [[Grup perkalian bilangan bulat modulo n|Grup perkalian bilangan bulat modulo ]]
* [[Jumlah Ramanujan]]
* [[Fungsi penjumlahan total]]

== Catatan ==
== Pranala luar ==
* 
*[http://mathcenter.oxford.emory.edu/site/math125/chineseRemainderTheorem/ Euler's Phi Function and the Chinese Remainder Theorem — proof that  is multiplicative] 
*[http://www.javascripter.net/math/calculators/eulertotientfunction.htm Euler's totient function calculator in JavaScript — up to 20 digits] 
*Dineva, Rosica, [http://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf The Euler Totient, the Möbius, and the Divisor Functions] 
*Plytage, Loomis, Polhill [http://facstaff.bloomu.edu/jpolhill/cmj034-042.pdf Summing Up The Euler Phi Function]

== Referensi ==
<references />

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Fungsi+phi+Euler&oldid=29299396 Wikipedia bahasa Indonesia], revisi 29299396 (2026-05-31T21:49:44Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

<!-- WIKI_UNISSULA_PRESENTATION_V4 -->