Fungsi phi Euler

Artikel atau bagian ini sedang dipersiapkan dan dikembangkan sehingga mungkin terjadi perubahan besar. Anda dapat membantu dalam penyuntingan halaman ini. Jika artikel atau bagian tidak disunting dalam beberapa hari, silakan hapus templat ini. Jika Anda adalah pengguna yang menambahkan templat ini dan Anda sedang aktif menyunting, pastikan untuk mengganti templat ini dengan {{sedang ditulis}} saat hendak menyunting. Klik pranala untuk parameter templat yang akan digunakan. Artikel ini terakhir disunting oleh HsfBot (bicara | kontrib) 40 hari lalu. (Perbarui pewaktu)

Dalam teori bilangan, untuk suatu bilangan asli n {\displaystyle n} , fungsi phi Euler (bahasa Inggris:Euler's totient function), dilambangkan dengan menggunakan huruf Yunani phi sebagai φ ( n ) {\displaystyle \varphi (n)} atau ϕ ( n ) {\displaystyle \phi (n)} , menyatakan banyak bilangan bulat positif yang kurang dari n {\displaystyle n} dan saling prima dengan n {\displaystyle 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 φ : N + → N + {\displaystyle \varphi \colon \mathbb {N} ^{+}\to \mathbb {N} ^{+}} ,

φ ( n ) := | { a ∈ N ∣ 1 ≤ a ≤ n ∧ FPB ⁡ ( a , n ) = 1 } | {\displaystyle \varphi (n)\;:=\;{\Big |}\{a\in \mathbb {N} \,\mid \,1\leq a\leq n\land \operatorname {FPB} (a,n)=1\}{\Big |}}

dengan |·| menyatakan kardinalitas himpunan dan FPB adalah faktor persekutuan terbesar antara a dan n.

Sebagai contoh:

• φ(1) = 1, karena diantara bilangan 1 sampai 1, terdapat satu bilangan, yaitu 1, yang saling prima dengan 1;
• φ(8) = 4, karena diantara bilangan 1 sampai 8, terdapat empat bilangan, yaitu 1, 3, 5, dan 7, yang saling prima dengan 8;
• φ(18) = 6, karena diantara bilangan 1 sampai 12, terdapat empat bilangan 1, 5, 7, 11, 13, dan 17, yang saling prima dengan 18;
• φ(67) = 66, 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):

φ ( n ) {\displaystyle \varphi (n)}	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
00+		01	01	02	02	04	02	06	04	06
10+	04	10	04	12	06	08	08	16	06	18
20+	08	12	10	22	08	20	12	18	12	28
30+	08	30	16	20	16	24	12	36	18	24
40+	16	40	12	42	20	24	22	46	16	42
50+	20	32	24	52	18	40	24	36	28	58
60+	16	60	30	36	32	48	20	66	32	44
70+	24	70	24	72	36	40	36	60	24	78
80+	32	54	40	82	24	64	42	56	40	88
90+	24	72	44	60	46	72	32	96	42	60

Dalam grafik di kanan atas baris y = n − 1 {\displaystyle y=n-1} adalah batas atas valid untuk semua n {\displaystyle n} selain satu, dan dicapai jika dan hanya jika n {\displaystyle n} adalah bilangan prima. Batas bawah sederhana adalah φ ( n ) ≥ n 2 {\displaystyle \varphi (n)\geq {\sqrt {\frac {n}{2}}}} , yang agak longgar: sebenarnya, lower limit dari grafik sebanding dengan n log ⁡ log ⁡ n {\displaystyle {\frac {n}{\log \log n}}} .^[2]

Sifat fungsi

Sifat perkalian fungsi phi Euler

Fungsi phi Euler adalah fungsi perkalian sehingga sehingga untuk dua bilangan asli m , n {\displaystyle m,n} yang saling prima berlaku

φ ( m n ) = φ ( m ) φ ( n ) {\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}

Perhitungan

• φ ( 1 ) = 0 {\displaystyle \varphi (1)=0} , φ ( 2 ) = 1 {\displaystyle \varphi (2)=1}
• φ ( p ) = p − 1 {\displaystyle \varphi (p)=p-1} , untuk p {\displaystyle p} adalah bilangan prima

• jika gcd ( m , n ) = 1 {\displaystyle \gcd(m,n)=1}
• φ ( p n ) = p n − 1 ( p − 1 ) {\displaystyle \varphi (p^{n})=p^{n-1}(p-1)}
• φ ( ∏ i = 1 n p i ) = ∏ i = 1 n ( p i − 1 ) {\displaystyle \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 ∣ b ⟹ φ ( a ) ∣ φ ( b ) {\displaystyle a\mid b\implies \varphi (a)\mid \varphi (b)}
• n ∣ φ ( a n − 1 ) {\displaystyle n\mid \varphi (a^{n}-1)} , untuk setiap a , n > 1 {\displaystyle a,n>1}
• φ ( m , n ) = φ ( m ) ⋅ φ ( n ) {\displaystyle \varphi (m,n)=\varphi (m)\cdot \varphi (n)}

Perhatikan kasus khusus

• φ ( 2 m ) = { 2 φ ( m )  jika  m  adalah genap φ ( m )  jika  m  adalah ganjil {\displaystyle \varphi (2m)={\begin{cases}2\varphi (m)&{\text{ jika }}m{\text{ adalah genap}}\\\varphi (m)&{\text{ jika }}m{\text{ adalah ganjil}}\end{cases}}}
• φ ( n m ) = n m − 1 φ ( n ) {\displaystyle \varphi \left(n^{m}\right)=n^{m-1}\varphi (n)}
• φ ( lcm ⁡ ( m , n ) ) ⋅ φ ( gcd ⁡ ( m , n ) ) = φ ( m ) ⋅ φ ( n ) {\displaystyle \varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)} Bandingkan dengan rumus
• lcm ⁡ ( m , n ) ⋅ gcd ⁡ ( m , n ) = m ⋅ n {\displaystyle \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).
• φ ( n ) n = φ ( rad ⁡ ( n ) ) rad ⁡ ( n ) {\displaystyle {\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}}

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

• ∑ d ∣ n μ 2 ( d ) φ ( d ) = n φ ( n ) {\displaystyle \sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}}  ^[3]
• ∑ 1 ≤ k ≤ n ( k , n ) = 1 k = 1 2 n φ ( n ) {\displaystyle \sum _{1\leq k\leq n \atop (k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)} , untuk n > 1 {\displaystyle n>1}
• ∑ k = 1 n φ ( k ) = 1 2 ( 1 + ∑ k = 1 n μ ( k ) ⌊ n k ⌋ 2 ) = 3 π 2 n 2 + O ( n ( log ⁡ n ) 2 3 ( log ⁡ log ⁡ n ) 4 3 ) {\displaystyle \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)}  (^[4] dikutip dalam^[5])

• ∑ k = 1 n φ ( k ) k = ∑ k = 1 n μ ( k ) k ⌊ n k ⌋ = 6 π 2 n + O ( ( log ⁡ n ) 2 3 ( log ⁡ log ⁡ n ) 4 3 ) {\displaystyle \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)}  ^[4]
• ∑ k = 1 n k φ ( k ) = 315 ζ ( 3 ) 2 π 4 n − log ⁡ n 2 + O ( ( log ⁡ n ) 2 3 ) {\displaystyle \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)}  ^[6]
• ∑ k = 1 n 1 φ ( k ) = 315 ζ ( 3 ) 2 π 4 ( log ⁡ n + γ − ∑ p  prime log ⁡ p p 2 − p + 1 ) + O ( ( log ⁡ n ) 2 3 n ) {\displaystyle \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)}  ^[6]

(dengan γ {\displaystyle \gamma } adalah konstanta Euler–Mascheroni).

• ∑ gcd ⁡ ( k , m ) = 1 1 ≤ k ≤ n 1 = n φ ( m ) m + O ( 2 ω ( m ) ) {\displaystyle \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 {\displaystyle m>1} adalah bilangan bulat positif dan ω ( m ) {\displaystyle \omega (m)} adalah jumlah faktor prima yang berbeda dari m {\displaystyle m} .^[7]

Fungsi pembangkit

Deret Dirichlet untuk φ ( n ) {\displaystyle \varphi (n)} dapat ditulis dalam istilah fungsi zeta Riemann sebagai:^[8]

∑ n = 1 ∞ φ ( n ) n s = ζ ( s − 1 ) ζ ( s ) . {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}.}

Fungsi pembangkit deret Lambert adalah^[9]

∑ n = 1 ∞ φ ( n ) q n 1 − q n = q ( 1 − q ) 2 {\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}

konvergen untuk | q | < 1 {\displaystyle |q|<1} .

Keduanya dibuktikan dengan manipulasi deret dasar dan rumus untuk φ ( n ) {\displaystyle \varphi (n)} .

Rasio bilangan berurutan

Pada tahun 1950 Somayajulu membuktikan^[10][11]

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

Pada tahun 1954 Schinzel dan Sierpiński memperkuat ini, membuktikan^[10][11] bahwa himpunan

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

adalah padat dalam bilangan riil positif. Mereka pun membuktikannya^[10] bahwa himpunan

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

padat dalam interval ( 0 , 1 ) {\displaystyle (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

Catatan

Referensi

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