Fungsi phi Euler

"Φ(n)" beralih ke halaman ini. Untuk kegunaan lain, lihat phi.

Dalam teori bilangan, fungsi phi Euler (Inggris: Euler's totient function) 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$.

Seribu nilai pertama φ(n). Titik di garis atas adalah φ(p) bila p adalah bilangan prima, yaitu p − 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

Terdapat beberapa identitas mengenai fungsi Euler phi, diantaranya:

• $\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, diantaranya

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

• φ(n) genap untuk n ≥ 3. Selain itu, jika n memiliki r faktor prima ganjil yang berbeda, 2^r | φ(n)
• Untuk a > 1 dan n > 6 sehingga 4 ∤ n terdapat l ≥ 2n sedemikian sehingga l | φ(aⁿ − 1).
• ${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$

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

• $\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$ 
• $\sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)$, untuk $n>1$
• $\sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ ( 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 ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ 
• $\sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)$ 
• $\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)^{\frac {2}{3}}}{n}}\right)$ 

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

• $\sum _{\stackrel {1\leq k\leq 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 (barisan A000010 pada OEIS) ditampilkan pada tabel dan grafik di bawah ini:

Grafik dari 100 nilai pertama

$\varphi (n)$ untuk $1\leq n\leq 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 $\varphi (n)\geq {\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|<1$.

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 n
• 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.

• Abramowitz, M.; Stegun, I. A. (1964), Handbook of Mathematical Functions, New York: Dover Publications, ISBN 0-486-61272-4 . See paragraph 24.3.2.
• Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), MIT Press Series in the Foundations of Computing, Cambridge, MA: The MIT Press, ISBN 0-262-02405-5, Zbl 0873.11070 
• Dickson, Leonard Eugene, "History Of The Theory Of Numbers", vol 1, chapter 5 "Euler's Function, Generalizations; Farey Series", Chelsea Publishing 1952
• Ford, Kevin (1999), "The number of solutions of φ(x) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, ISSN 0003-486X, JSTOR 121103, MR 1715326, Zbl 0978.11053 .
• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithmeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9 
• Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithmeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 
• Graham, Ronald; Knuth, Donald; Patashnik, Oren (1994), Concrete Mathematics: a foundation for computer science (edisi ke-2nd), Reading, MA: Addison-Wesley, ISBN 0-201-55802-5, Zbl 0836.00001 
• Guy, Richard K. (2004), Unsolved Problems in Number Theory, Problem Books in Mathematics (edisi ke-3rd), New York, NY: Springer-Verlag, ISBN 0-387-20860-7, Zbl 1058.11001 
• Hardy, G. H.; Wright, E. M. (1979), An Introduction to the Theory of Numbers (edisi ke-Fifth), Oxford: Oxford University Press, ISBN 978-0-19-853171-5 
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (edisi ke-2nd), Lexington: D. C. Heath and Company, LCCN 77-171950 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 
• Ribenboim, Paulo (1996), The New Book of Prime Number Records (edisi ke-3rd), New York: Springer, ISBN 0-387-94457-5, Zbl 0856.11001 
• Sandifer, Charles (2007), The early mathematics of Leonhard Euler, MAA, ISBN 0-88385-559-3 
• Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, ed. (2006), Handbook of number theory I, Dordrecht: Springer-Verlag, hlm. 9–36, ISBN 1-4020-4215-9, Zbl 1151.11300 
• Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. hlm. 179–327. ISBN 1-4020-2546-7. Zbl 1079.11001. 
• Schramm, Wolfgang (2008), "The Fourier transform of functions of the greatest common divisor", Electronic Journal of Combinatorial Number Theory, A50 (8(1)), diarsipkan dari versi asli tanggal 2009-05-01, diakses tanggal 2021-01-27 .

Pranala luar

• Hazewinkel, Michiel, ed. (2001) [1994], "Totient function", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• Euler's Phi Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative Diarsipkan 2021-02-28 di Wayback Machine.
• Euler's totient function calculator in JavaScript — up to 20 digits Diarsipkan 2023-07-06 di Wayback Machine.
• Dineva, Rosica, The Euler Totient, the Möbius, and the Divisor Functions Diarsipkan 2021-01-16 di Wayback Machine.
• Plytage, Loomis, Polhill Summing Up The Euler Phi Function Diarsipkan 2023-05-23 di Wayback Machine.