Fungsi phi Euler

Dalam teori bilangan, untuk suatu bilangan asli $n$, fungsi phi Euler (), dilambangkan dengan menggunakan huruf Yunani phi sebagai $\phi (n)$ atau $\varphi (n)$, menyatakan banyak bilangan bulat positif yang kurang dari $n$ dan saling prima dengan $n$.

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, Swiss. w. 18 September 1783, Rusia).

Definisi dan contoh

Fungsi phi Euler didefinisikan sebagai $\phi :{\mathbb{N}}^{+}\to {\mathbb{N}}^{+}$,

$\phi (n):=|\{a\in \mathbb{N}\mid 1\le a\le n\wedge \mathrm{FPB}(a,n)=1\}|$

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  A000010 di OEIS):

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}$.

Sifat fungsi

Sifat perkalian fungsi phi Euler

Fungsi phi Euler adalah fungsi perkalian sehingga sehingga untuk dua bilangan asli $m,n$ yang saling prima berlaku

$\phi (mn)=\phi (m)\phi (n)$

Perhitungan

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

• 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, di antaranya

• $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.)

• genap untuk . Selain itu, jika memiliki faktor prima ganjil yang berbeda,
• Untuk dan sehingga terdapat sedemikian sehingga .
• $\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$.

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

$liminf\frac{\phi (n+1)}{\phi (n)}=0$ dan $limsup\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
• Jumlah Ramanujan
• Fungsi penjumlahan total

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

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29299396 (2026-05-31T21:49:44Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.