Fungsi phi Euler

Seribu nilai pertama Templat:Math. Titik di garis atas adalah Templat:Math bila Templat:Mvar adalah bilangan prima, yaitu Templat:Math

Dalam teori bilangan, fungsi phi Euler (Templat:Lang-en) adalah fungsi yang menghitung bilangan bulat positif hingga diberikan bilangan bulat $n$ yang prima nisbi dengan $n$. Fungsi ini ditulis dengan menggunakan huruf Yunani, phi, yang dilambangkan sebagai $\phi (m)$ atau $\varphi (m)$ menyatakan kardinal himpunan bilangan asli $1\le n\le m$ dimana $\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

Templat:Tanpa referensiTerdapat beberapa identitas mengenai fungsi Euler phi, diantaranya:

• $\phi (1)=0$, $\phi (2)=1$
• $\phi (p)=p-1$, untuk $p$ adalah bilangan prima

• $\phi (mn)=\phi (m)\phi (n)$ jika $\gcd (m,n)=1$
• $\phi (p^n)=p^{n-1}(p-1)$
• $\phi \left(\prod _{i=1}^n{p}_i\right)=\prod _{i=1}^n(p_i-1)$

Rumus lainnya

Apabila rumus lain mengenai fungsi Euler phi, diantaranya

• $a\mid b⟹\phi (a)\mid \phi (b)$
• $n\mid \phi (a^n-1)$, untuk setiap $a,n>1$
• $\phi (m,n)=\phi (m)\cdot \phi (n)$

Perhatikan kasus khusus

• $\phi (2m)=\{\begin{array}{cc}2\phi (m)& \text{ jika }m\text{ adalah genap}\\ \phi (m)& \text{ jika }m\text{ adalah ganjil}\end{array}$
• $\phi \left(n^m\right)=n^{m-1}\phi (n)$
• $\phi (\mathrm{lcm}(m,n))\cdot \phi (\gcd (m,n))=\phi (m)\cdot \phi (n)$ Bandingkan dengan rumus
• $\mathrm{lcm}(m,n)\cdot \gcd (m,n)=m\cdot n$

(Lihat kelipatan persekutuan terkecil.)

• Templat:Math genap untuk Templat:Math. Selain itu, jika Templat:Mvar memiliki Templat:Mvar faktor prima ganjil yang berbeda, Templat:Math
• Untuk Templat:Math dan Templat:Math sehingga Templat:Math terdapat Templat:Math sedemikian sehingga Templat:Math.
• $\frac{\phi (n)}{n}=\frac{\phi (\mathrm{rad}(n))}{\mathrm{rad}(n)}$

di mana $\mathrm{rad}(n)$ adalah radikal dari $n$.

• $\sum _{d\mid n}\frac{{\mu }^2(d)}{\phi (d)}=\frac{n}{\phi (n)}$ 
• $\sum _{\genfrac{}{}{0ex}{}{1\le k\le n}{(k,n)=1}}k=\frac{1}{2}n\phi (n)$, untuk $n>1$
• $\sum _{k=1}^n\phi (k)=\frac{1}{2}(1+\sum _{k=1}^n\mu (k){\lfloor \frac{n}{k}\rfloor }^2)=\frac{3}{{\pi }^2}{n}^2+O(n(\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{4}{3}})$ ( dikutip dalam)

• $\sum _{k=1}^n\frac{\phi (k)}{k}=\sum _{k=1}^n\frac{\mu (k)}{k}\lfloor \frac{n}{k}\rfloor =\frac{6}{{\pi }^2}n+O((\log n{)}^{\frac{2}{3}}(\log \log n{)}^{\frac{4}{3}})$ 
• $\sum _{k=1}^n\frac{k}{\phi (k)}=\frac{315\zeta (3)}{2{\pi }^4}n-\frac{\log n}{2}+O((\log n{)}^{\frac{2}{3}})$ 
• $\sum _{k=1}^n\frac{1}{\phi (k)}=\frac{315\zeta (3)}{2{\pi }^4}(\log n+\gamma -\sum _{p\text{ prime}}\frac{\log p}{p^2-p+1})+O\left(\frac{(\log n{)}^{\frac{2}{3}}}{n}\right)$ 

(dengan $\gamma$ adalah konstanta Euler–Mascheroni).

• $\sum _{\stackrel{1\le k\le n}{\gcd (k,m)=1}}1=n\frac{\phi (m)}{m}+O\left(2^{\omega (m)}\right)$

dimana $m>1$ adalah bilangan bulat positif dan $\omega (m)$ adalah jumlah faktor prima yang berbeda dari $m$.

Beberapa bilangan

100 nilai pertama Templat:OEIS ditampilkan pada tabel dan grafik di bawah ini:

Grafik dari 100 nilai pertama

$\phi (n)$ untuk $1\le n\le 100$

+	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 $y=n-1$ adalah batas atas valid untuk semua $n$ selain satu, dan dicapai jika dan hanya jika $n$ adalah bilangan prima. Batas bawah sederhana adalah $\phi (n)\ge \sqrt{\frac{n}{2}}$, yang agak longgar: sebenarnya, lower limit dari grafik sebanding dengan $\frac{n}{\log \log n}$. Templat:Clear

Fungsi pembangkit

Deret Dirichlet untuk $\phi (n)$ dapat ditulis dalam istilah fungsi zeta Riemann sebagai:

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)}{n^s}=\frac{\zeta (s-1)}{\zeta (s)}.$

Fungsi pembangkit deret Lambert adalah

$\sum _{n=1}^{\mathrm{\infty }}\frac{\phi (n)q^n}{1-q^n}=\frac{q}{(1-q{)}^2}$

konvergen untuk $|q|<1$.

Keduanya dibuktikan dengan manipulasi deret dasar dan rumus untuk $\phi (n)$.

Rasio bilangan berurutan

Pada tahun 1950 Somayajulu membuktikan

$\lim \inf \frac{\phi (n+1)}{\phi (n)}=0$ dan $\lim \sup \frac{\phi (n+1)}{\phi (n)}=\mathrm{\infty }$

Pada tahun 1954 Schinzel dan Sierpiński memperkuat ini, membuktikan bahwa himpunan

$\{\frac{\phi (n+1)}{\phi (n)},n=1,2,\dots \}$

adalah padat dalam bilangan riil positif. Mereka pun membuktikannya bahwa himpunan

$\{\frac{\phi (n)}{n},n=1,2,\dots \}$

padat dalam interval $(0,1)$.

Lihat pula

• Fungsi Carmichael
• Konjektur Duffin–Schaeffer
• Generalisasi teorema kecil Fermat
• Bilangan komposit tinggi
• [[Grup perkalian bilangan bulat modulo n|Grup perkalian bilangan bulat modulo Templat:Mvar]]
• Jumlah Ramanujan
• Fungsi penjumlahan total

Referensi

Templat:Refbegin 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.

• Templat:Citation. See paragraph 24.3.2.
• Templat:Citation
• Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
• Templat:Citation.
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Cite book
• Templat:Citation.

Pranala luar

• Templat:Springer
• Euler's Phi Function and the Chinese Remainder Theorem — proof that Templat:Math is multiplicative Templat:Webarchive
• Euler's totient function calculator in JavaScript — up to 20 digits Templat:Webarchive
• Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Templat:Webarchive
• Plytage, Loomis, Polhill Summing Up The Euler Phi Function Templat:Webarchive