Fungsi phi Euler

Dalam teori bilangan, **fungsi phi Euler** () 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 \varphi(m) atau \phi(m) menyatakan *kardinal* himpunan bilangan asli 1\leq n\leq m dimana \gcd(m,n) = 1.

Bilangan bulat positif yang \varphi(1) = 0, \varphi(2) = 1
* \varphi(p) = p - 1, untuk p adalah bilangan prima

* \varphi(mn) = \varphi(m) \varphi(n) jika \gcd(m,n) = 1
* \varphi(p^n) = p^{n - 1} (p - 1)
* \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, di antaranya
* a\mid b \implies \varphi(a)\mid\varphi(b)
*  n \mid \varphi(a^n-1), untuk setiap a, n > 1
* \varphi(m,n) = \varphi(m) \cdot \varphi(n)
:Perhatikan kasus khusus
:* \varphi(2m) = \begin{cases}
2\varphi(m) &\text{ jika } m \text{ adalah genap} \\
\varphi(m) &\text{ jika } m \text{ adalah ganjil}
\end{cases}
:* \varphi\left(n^m\right) = n^{m-1}\varphi(n)
:* \varphi(\operatorname{lcm}(m,n))\cdot\varphi(\operatorname{gcd}(m,n)) = \varphi(m)\cdot\varphi(n)  Bandingkan dengan rumus
:* \operatorname{lcm}(m,n)\cdot \operatorname{gcd}(m,n) = m \cdot n

:(Lihat kelipatan persekutuan terkecil.)

*  genap untuk . Selain itu, jika  memiliki  faktor prima ganjil yang berbeda, 
* Untuk  dan  sehingga  terdapat  sedemikian sehingga .
* \frac{\varphi(n)}{n}=\frac{\varphi(\operatorname{rad}(n))}{\operatorname{rad}(n)}
:di mana \operatorname{rad}(n) adalah radikal dari <math>n</math>.
* \sum_{d \mid n} \frac{\mu^2(d)}{\varphi(d)} = \frac{n}{\varphi(n)}&nbsp;
* \sum_{1\le k\le n \atop (k,n)=1}\!\!k = \tfrac12 n\varphi(n), untuk n > 1
* \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)&nbsp;( dikutip dalam)

* \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)&nbsp;
* \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)&nbsp;
* \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)&nbsp;

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

* \sum_\stackrel{1\le k\le n}{\operatorname{gcd}(k,m)=1} \!\!\!\! 1 = n \frac {\varphi(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  ditampilkan pada tabel dan grafik di bawah ini:

:

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 \varphi(n) \ge \sqrt{\frac{n}{2}} , yang agak longgar: sebenarnya, lower limit dari grafik sebanding dengan \frac{n}{\log \log n}.

## Fungsi pembangkit

Deret Dirichlet untuk \varphi(n) dapat ditulis dalam istilah fungsi zeta Riemann sebagai:
:\sum_{n=1}^\infty \frac{\varphi(n)}{n^s}=\frac{\zeta(s-1)}{\zeta(s)}.

Fungsi pembangkit deret Lambert adalah

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

konvergen untuk |q| .

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

## Rasio bilangan berurutan
Pada tahun 1950 Somayajulu membuktikan

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


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

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

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

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

padat dalam interval (0,1).

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

## Catatan

## Referensi

*[[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*.

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

## Pranala luar
* 
*Euler's Phi Function and the Chinese Remainder Theorem — proof that  is multiplicative 
*Euler's totient function calculator in JavaScript — up to 20 digits 
*Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions 
*Plytage, Loomis, Polhill Summing Up The Euler Phi Function