Fungsi phi Euler: Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi terkini sejak 19 Agustus 2024 04.00

Seribu nilai pertama $φ (n)$ . Titik di garis atas adalah $φ (p)$ bila $p$ adalah bilangan prima, yaitu $p - 1.$ ^[1]

Dalam teori bilangan, fungsi phi Euler (bahasa 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$ .

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 \geq 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 \geq 2 n$ sedemikian sehingga $l | φ (a n - 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)}}$ ^[2]
$\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)$ (^[3] dikutip dalam^[4])

$\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)$ ^[3]
$\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)$ ^[5]
$\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)$ ^[5]

(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

.^[6]

Beberapa bilangan

100 nilai pertama (barisan A000010 pada OEIS) ditampilkan pada tabel dan grafik di bawah ini:

$\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}}$ .^[7]

Fungsi pembangkit

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

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

Fungsi pembangkit deret Lambert adalah^[9]

\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^[10]^[11]

\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^[10]^[11] bahwa himpunan

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

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

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

padat dalam interval $(0,1)$ .

Lihat pula

Catatan

^ "Euler's totient function". Khan Academy. Diakses tanggal 2016-02-26.
^ Dineva (dalam referensi eksternal), prop. 1
^ ^a ^b Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (dalam bahasa Jerman). 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.
^ Lomadse, G., "The scientific work of Arnold Walfisz" (PDF), Acta Arithmetica, 10 (3): 227–237, diarsipkan (PDF) dari versi asli tanggal 2023-06-06, diakses tanggal 2020-04-22
^ ^a ^b Sitaramachandrarao, R. (1985). "On an error term of Landau II". Rocky Mountain J. Math. 15: 579–588.
^ Bordellès di pranala luar
^ Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama hw328
^ Hardy & Wright 1979, thm. 288
^ Hardy & Wright 1979, thm. 309
^ ^a ^b ^c Ribenboim, p.38
^ ^a ^b Sándor, Mitrinović & Crstici (2006) p.16

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.

[1] "Euler's totient function". Khan Academy. Diakses tanggal 2016-02-26.

[2] Dineva (dalam referensi eksternal), prop. 1

[Wal1963-3] Walfisz, Arnold (1963). Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (dalam bahasa Jerman). 16. Berlin: VEB Deutscher Verlag der Wissenschaften. Zbl 0146.06003.

[4] Lomadse, G., "The scientific work of Arnold Walfisz" (PDF), Acta Arithmetica, 10 (3): 227–237, diarsipkan (PDF) dari versi asli tanggal 2023-06-06, diakses tanggal 2020-04-22

[Sita-5] Sitaramachandrarao, R. (1985). "On an error term of Landau II". Rocky Mountain J. Math. 15: 579–588.

[6] Bordellès di pranala luar

[hw328-7] Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama hw328

[8] Hardy & Wright 1979, thm. 288

[9] Hardy & Wright 1979, thm. 309

[Rib38-10] Ribenboim, p.38

[SMC16-11] Sándor, Mitrinović & Crstici (2006) p.16

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

l b s Daftar fungsi matematika
Fungsi polinomial	Fungsi konstan (0) Fungsi linear (1) Fungsi kuadrat (2) Fungsi kubik (3) Fungsi kuartik (4) Fungsi kuintik (5)
Fungsi aljabar	Fungsi rasional Fungsi eksponensial Lambert W Superakar Fungsi hiperbolik Fungsi logaritma Berdasarkan basis 2 $e$ 10 teriterasi Superlogaritma
Fungsi dalam teori bilangan	Fungsi Möbius Fungsi partisi Fungsi perhitungan bilangan prima Fungsi phi Euler Fungsi sigma
Fungsi trigonometri	Sinus Kosinus Tangen Sekan Kosekan Kotangen Versinus Koversinus Verkosinus Koverkosinus Ekssekan Ekskosekan Haversinus Hakoversinus Haverkosinus Hakoverkosinus Gudermann sinc
Fungsi berdasarkan huruf Yunani	Fungsi beta Dirichlet taklengkap Fungsi chi Legendre Fungsi delta Fungsi delta Dirac Fungsi delta Kronecker potensial delta Fungsi eta Dirichlet Fungsi gamma Fungsi digamma Barnes Meijer banyak eliptik Hadamard multivariabel p-adik q taklengkap Fungsi poligamma Fungsi trigamma Fungsi lambda Dirchlet modular von Mangoldt Fungsi mu Möbius Fungsi phi Euler Fungsi pi Fungsi sigma Weierstrass Fungsi theta Fungsi zeta Hurwitz Riemann Weierstrass
Fungsi berdasarkan nama matematikawan	Airy Ackermann Bessel Bessel–Clifford Bottcher Chebyshev Clausen Dawson Dirichlet beta eta L lambda Faddeeva Fermi–Dirac lengkap taklengkap Fresnel Fox Gudermann Hermite Fungsi Jacob eliptik Jacobi Kelvin Fungsi Kummer Fungsi Lambert W Lamé Laguerre Legendre chi iring Liouville Mathieu Meijer Mittag-Leffler Painlevé Riemann xi zeta Riesz Scorer Spence von Mangoldt Weierstrass eliptik eta sigma zeta
Fungsi khusus	Fungsi bagian bilangan bulat Fungsi bilangan bulat terbesar Fungsi bilangan bulat terkecil Fungsi gergaji Fungsi indikator Fungsi nilai mutlak Fungsi persegi Fungsi segitiga Fungsi tanda Fungsi tangga Fungsi tangga Heaviside
Fungsi lainnya	Aritmetik-geometrik eliptik Fungsi hiperbolik konfluen K sinkrotron tabung parabolik tanda tanya Minkowski Pentasi Student Tetrasi