Lihat sumber Fungsi phi Euler

{{short description|Memberikan jumlah bilangan bulat yang relatif prima untuk masukannya}}
{{Redirect|Φ(n)||phi}}{{Periksa terjemahan}}[[Gambar:EulerPhi.svg|thumb|Seribu nilai pertama {{math|''φ''(''n'')}}. Titik di garis atas adalah {{Math|''φ''(''p'')}} bila {{mvar | p}} adalah bilangan prima, yaitu {{Math|''p'' − 1.}}<ref>{{Cite web
| url = https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function
| title = Euler's totient function
| website = Khan Academy
| access-date = 2016-02-26
}}</ref>]]
Dalam [[teori bilangan]], '''fungsi phi Euler''' ({{Lang-en|Euler's totient function}}) adalah fungsi yang menghitung bilangan bulat positif hingga diberikan bilangan bulat <math>n</math> yang [[Koprima (bilangan)|prima nisbi]] dengan <math>n</math>. Fungsi ini ditulis dengan menggunakan huruf Yunani, [[Fi|phi]], yang dilambangkan sebagai <math>\varphi(m)</math> atau <math>\phi(m)</math> menyatakan ''kardinal'' [[himpunan]] [[bilangan asli]] <math>1\leq n\leq m</math> dimana <math>\gcd(m,n) = 1</math>.

[[Bilangan bulat]] positif yang < 9 adalah 1, 2, 3, 4, 5, 6, 7, 8. Diantara bilangan-bilangan tersebut yang [[Koprima (bilangan)|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, [[Konfederasi Swiss Lama|Swiss.]] w. 18 September 1783, [[Kekaisaran Rusia|Rusia]]).

== Identitas ==
{{tanpa referensi|date=Juni 2021}}Terdapat beberapa identitas mengenai fungsi Euler phi, diantaranya:

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

* <math>\varphi(mn) = \varphi(m) \varphi(n)</math> 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, diantaranya
* <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]].)

* {{math|''φ''(''n'')}} genap untuk {{math|''n'' ≥ 3}}. Selain itu, jika {{mvar|n}} memiliki {{mvar|r}} faktor prima ganjil yang berbeda, {{math|2<sup>''r''</sup> {{!}} ''φ''(''n'')}}
* Untuk {{math|''a'' > 1}} dan {{math|''n'' > 6}} sehingga {{math|4 ∤ ''n''}} terdapat {{math|''l'' ≥ 2''n''}} sedemikian sehingga {{math|''l'' {{!}} ''φ''(''a<sup>n</sup>'' − 1)}}.
* <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 name=Wal1963>{{cite book | zbl=0146.06003 | last=Walfisz | first=Arnold | authorlink=Arnold Walfisz | title=Weylsche Exponentialsummen in der neueren Zahlentheorie | language=Jerman | series=Mathematische Forschungsberichte | volume=16 | location=Berlin | publisher=[[VEB Deutscher Verlag der Wissenschaften]] | year=1963 }}</ref> dikutip dalam<ref>{{citation | last = Lomadse | first = G. | title = The scientific work of Arnold Walfisz | journal = Acta Arithmetica | volume = 10 | issue = 3 | pages = 227–237 | url = http://matwbn.icm.edu.pl/ksiazki/aa/aa10/aa10111.pdf | accessdate = 2020-04-22 | archive-date = 2023-06-06 | archive-url = https://web.archive.org/web/20230606045537/http://matwbn.icm.edu.pl/ksiazki/aa/aa10/aa10111.pdf | dead-url = no }}</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 name=Wal1963/>
* <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 name=Sita>{{cite journal|first=R. |last=Sitaramachandrarao |title=On an error term of Landau II |journal=Rocky Mountain J. Math. |volume=15 |date=1985 |pages=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 name=Sita />

:(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|pranala luar]]</ref>

== Beberapa bilangan ==
100 nilai pertama {{OEIS|A000010}} ditampilkan pada tabel dan grafik di bawah ini:

[[Berkas:EulerPhi100.svg|thumb|Grafik dari 100 nilai pertama]]
:{| class="wikitable" style="text-align: right"
|+<math>\varphi(n)</math> untuk <math>1 \le n \le 100</math>
! +
! 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10
|- 
! 0 
| 1 || 1 || 2 || 2 || 4 || 2 || 6 || 4 || 6 || 4 
|-
! 10
| 10 || 4 || 12 || 6 || 8 || 8 || 16 || 6 || 18 || 8 
|- 
! 20
| 12 || 10 || 22 || 8 || 20 || 12 || 18 || 12 || 28 || 8 
|-
! 30
| 30 || 16 || 20 || 16 || 24 || 12 || 36 || 18 || 24 || 16 
|-
! 40
| 40 || 12 || 42 || 20 || 24 || 22 || 46 || 16 || 42 || 20
|-
! 50
| 32 || 24 || 52 || 18 || 40 || 24 || 36 || 28 || 58 || 16 
|-
! 60
| 60 || 30 || 36 || 32 || 48 || 20 || 66 || 32 || 44 || 24 
|-
! 70
| 70 || 24 || 72 || 36 || 40 || 36 || 60 || 24 || 78 || 32
|-
! 80
| 54 || 40 || 82 || 24 || 64 || 42 || 56 || 40 || 88 || 24
|-
! 90
| 72 || 44 || 60 || 46 || 72 || 32 || 96 || 42 || 60 || 40 
|}

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 name="hw328"/>
{{clear}}

== Fungsi pembangkit ==

[[Deret Dirichlet]] untuk <math>\varphi(n)</math> dapat ditulis dalam istilah [[fungsi zeta Riemann]] sebagai:<ref>{{harvnb|Hardy|Wright|1979|loc=thm. 288}}</ref>
:<math>\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.</math>

Fungsi pembangkit [[deret Lambert]] adalah<ref>{{harvnb|Hardy|Wright|1979|loc=thm. 309}}</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 name=Rib38>Ribenboim, p.38</ref><ref name=SMC16>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 name=Rib38/><ref name=SMC16/> 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 name=Rib38/> 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 {{mvar|n}}]]
* [[Jumlah Ramanujan]]
* [[Fungsi penjumlahan total]]

== Catatan ==
{{Reflist}}

== Referensi ==

{{refbegin|colwidth=30em}}
''[[Disquisitiones Arithmeticae]]'' telah diterjemahkan dari bahasa Latin ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua makalah Gauss tentang teori bilangan: semua bukti timbal balik kuadrat, penentuan tanda jumlah Gauss, penyelidikan timbal balik biquadratic, dan catatan yang tidak diterbitkan.

Referensi ke ''Disquisitiones'' adalah dari bentuk Gauss, DA, art. ''nnn''.

*{{citation
 | last1 = Abramowitz
 | first1 = M.
 | author1-link = Milton Abramowitz
 | last2 = Stegun
 | first2 = I. A.
 | author2-link = Irene A. Stegun
 | isbn = 0-486-61272-4
 | location = New York
 | publisher = [[Dover Publications]]
 | title = Handbook of Mathematical Functions
 | year = 1964
 | url = https://archive.org/details/handbookofmathe000abra
 }}. See paragraph 24.3.2.
*{{citation
 | last1 = Bach | first1 = Eric | author1-link = Eric Bach
 | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit
 | title = Algorithmic Number Theory (Vol I: Efficient Algorithms)
 | publisher = [[The MIT Press]]
 | location = Cambridge, MA
 | year = 1996
 | isbn = 0-262-02405-5
 | zbl=0873.11070
 | series=MIT Press Series in the Foundations of Computing
}}
* Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
*{{citation
 | last = Ford | first = Kevin
 | doi = 10.2307/121103
 | mr = 1715326 | zbl=0978.11053
 | issn= 0003-486X
 | issue = 1
 | journal = [[Annals of Mathematics]]
 | jstor = 121103
 | pages = 283–311
 | title = The number of solutions of φ(''x'')&nbsp;=&nbsp;''m''
 | volume = 150
 | year = 1999}}.
*{{citation
 | last1 = Gauss | first1 = Carl Friedrich | author1-link = Carl Friedrich Gauss
 | last2 = Clarke | first2 = Arthur A. (translator into English) 
 | title = Disquisitiones Arithmeticae (Second, corrected edition)
 | publisher = [[Springer Publishing|Springer]]
 | location = New York
 | year = 1986
 | isbn = 0-387-96254-9}}
*{{citation
 | last1 = Gauss | first1 = Carl Friedrich | author1-link = Carl Friedrich Gauss
 | last2 = Maser | first2 = H. (translator into German) 
 | title = Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition)
 | publisher = Chelsea
 | location = New York
 | year = 1965
 | isbn = 0-8284-0191-8}}
*{{citation
 | last1 = Graham | first1 = Ronald | author1-link = Ronald Graham
 | last2 = Knuth | first2 = Donald | author2-link = Donald Knuth
 | last3 = Patashnik | first3 = Oren | author3-link = Oren Patashnik
 | title = [[Concrete Mathematics]]: a foundation for computer science
 | edition=2nd
 | publisher = Addison-Wesley
 | location = Reading, MA
 | year = 1994
 | isbn = 0-201-55802-5 | zbl=0836.00001}}
* {{citation | first=Richard K. | last=Guy | author-link=Richard K. Guy | title=Unsolved Problems in Number Theory | edition=3rd | publisher=[[Springer-Verlag]] | year=2004 | isbn=0-387-20860-7 | zbl=1058.11001 | series=Problem Books in Mathematics | location=New York, NY }}
*{{citation
 | last1 = Hardy | first1 = G. H. | author1-link = G. H. Hardy
 | last2 = Wright | first2 = E. M. | author2-link = E. M. Wright
 | title = [[An Introduction to the Theory of Numbers]]
 | edition = Fifth
 | publisher = [[Oxford University Press]]
 | location = Oxford
 | year = 1979
 | isbn = 978-0-19-853171-5}}
* {{citation | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = [[D. C. Heath and Company]] | location = Lexington | lccn = 77-171950 }}
* {{citation | first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | publisher = [[Prentice Hall]] | location = Englewood Cliffs | lccn = 77-81766 }}
*{{citation
 | last1 = Ribenboim | first1 = Paulo | author-link = Paulo Ribenboim
 | title = The New Book of Prime Number Records | edition=3rd
 | publisher = [[Springer Science+Business Media|Springer]]
 | location = New York
 | year = 1996
 | zbl=0856.11001
 | isbn = 0-387-94457-5}}
*{{citation
 | last1 = Sandifer | first1 = Charles
 | title = The early mathematics of Leonhard Euler
 | publisher = MAA
 | year = 2007
 | isbn = 0-88385-559-3}}
* {{citation | editor1-last=Sándor | editor1-first=József | editor2-last=Mitrinović | editor2-first=Dragoslav S. | editor3-last=Crstici |editor3-first=Borislav | title=Handbook of number theory I | location=Dordrecht | publisher=[[Springer-Verlag]] | year=2006 | isbn=1-4020-4215-9 | zbl=1151.11300 | pages=9–36}}
* {{cite book | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | url=https://archive.org/details/handbooknumberth00sand_741 | url-access=limited | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | zbl=1079.11001 | pages=[https://archive.org/details/handbooknumberth00sand_741/page/n179 179]–327 }}
*{{citation
 | last = Schramm
 | first = Wolfgang
 | issue = 8(1)
 | journal = Electronic Journal of Combinatorial Number Theory
 | title = The Fourier transform of functions of the greatest common divisor
 | volume = A50
 | year = 2008
 | url = http://www.integers-ejcnt.org/vol8.html
 | accessdate = 2021-01-27
 | archive-date = 2009-05-01
 | archive-url = https://web.archive.org/web/20090501150001/http://www.integers-ejcnt.org/vol8.html
 | dead-url = no
 }}.
{{refend}}

== Pranala luar ==<!-- Bagian ini ditautkan dari [[fungsi total Euler]] -->
* {{springer|title=Totient function|id=p/t110040}}
*[http://mathcenter.oxford.emory.edu/site/math125/chineseRemainderTheorem/ Euler's Phi Function and the Chinese Remainder Theorem — proof that {{math|''φ''(''n'')}} is multiplicative] {{Webarchive|url=https://web.archive.org/web/20210228071226/http://mathcenter.oxford.emory.edu/site/math125/chineseRemainderTheorem/ |date=2021-02-28 }}
*[http://www.javascripter.net/math/calculators/eulertotientfunction.htm Euler's totient function calculator in JavaScript — up to 20 digits] {{Webarchive|url=https://web.archive.org/web/20230706152617/http://www.javascripter.net/math/calculators/eulertotientfunction.htm |date=2023-07-06 }}
*Dineva, Rosica, [http://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf The Euler Totient, the Möbius, and the Divisor Functions] {{Webarchive|url=https://web.archive.org/web/20210116061553/https://www.mtholyoke.edu/~robinson/reu/reu05/rdineva1.pdf |date=2021-01-16 }}
*Plytage, Loomis, Polhill [http://facstaff.bloomu.edu/jpolhill/cmj034-042.pdf Summing Up The Euler Phi Function] {{Webarchive|url=https://web.archive.org/web/20230523102207/http://facstaff.bloomu.edu/jpolhill/cmj034-042.pdf |date=2023-05-23 }}
{{Daftar fungsi matematika}}
[[Kategori:Aritmetika modular]]
[[Kategori:Fungsi perkalian]]
[[Kategori:Artikel yang memuat pembuktian]]
[[Kategori:Aljabar]]
[[Kategori:Teori bilangan]]
[[Kategori:Leonhard Euler]]