Fungsi phi Euler

EulerPhi

Seribu nilai pertama . Titik di garis atas adalah bila adalah bilangan prima, yaitu ^[1]

Dalam teori bilangan, untuk suatu bilangan asli $n$ , fungsi phi Euler (), dilambangkan dengan menggunakan huruf Yunani phi sebagai $φ (n)$ atau $ϕ (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 $φ : ℕ^{+} \to ℕ^{+}$ ,

$φ (n) := | {a \in ℕ ∣ 1 \leq a \leq n \land 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):

$φ (n)$	+0	+1	+2	+3	+4	+5	+6	+7	+8	+9
0+		1	1	2	2	4	2	6	4	6
10+	4	10	4	12	6	8	8	16	6	18
20+	8	12	10	22	8	20	12	18	12	28
30+	8	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$ adalah batas atas valid untuk semua $n$ selain satu, dan dicapai jika dan hanya jika $n$ adalah bilangan prima. Batas bawah sederhana adalah $φ (n) \geq \sqrt{\frac{n}{2}}$ , yang agak longgar: sebenarnya, lower limit dari grafik sebanding dengan $\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$ yang saling prima berlaku

$φ (m n) = φ (m) φ (n)$

Perhitungan

$φ (1) = 0$ , $φ (2) = 1$
$φ (p) = p - 1$ , untuk $p$ adalah bilangan prima

jika $gcd (m, n) = 1$
$φ (p^{n}) = p^{n - 1} (p - 1)$
$φ (\prod_{i = 1}^{n} p_{i}) = \prod_{i = 1}^{n} (p_{i} - 1)$

Rumus lainnya

Apabila rumus lain mengenai fungsi Euler phi, di antaranya

$a ∣ b ⟹ φ (a) ∣ φ (b)$
$n ∣ φ (a^{n} - 1)$ , untuk setiap $a, n > 1$
$φ (m, n) = φ (m) \cdot φ (n)$

Perhatikan kasus khusus

$φ (2 m) = {\begin{matrix} 2 φ (m) & jika m adalah genap \\ φ (m) & jika m adalah ganjil \end{matrix}$
$φ (n^{m}) = n^{m - 1} φ (n)$
$φ (lcm (m, n)) \cdot φ (gcd (m, n)) = φ (m) \cdot φ (n)$ Bandingkan dengan rumus
$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{φ (n)}{n} = \frac{φ (rad (n))}{rad (n)}$

di mana

rad (n)

adalah radikal dari

n

.

$\sum_{d ∣ n} \frac{μ^{2} (d)}{φ (d)} = \frac{n}{φ (n)}$ ^[3]
$\sum_{\binom{1 \leq k \leq n}{(k, n) = 1}} k = \frac{1}{2} n φ (n)$ , untuk $n > 1$
$\sum_{k = 1}^{n} φ (k) = \frac{1}{2} (1 + \sum_{k = 1}^{n} μ (k) {⌊ \frac{n}{k} ⌋}^{2}) = \frac{3}{π^{2}} n^{2} + O (n (\log n)^{\frac{2}{3}} (\log \log n)^{\frac{4}{3}})$ (^[4] dikutip dalam^[5])

$\sum_{k = 1}^{n} \frac{φ (k)}{k} = \sum_{k = 1}^{n} \frac{μ (k)}{k} ⌊ \frac{n}{k} ⌋ = \frac{6}{π^{2}} n + O ((\log n)^{\frac{2}{3}} (\log \log n)^{\frac{4}{3}})$ ^[6]
$\sum_{k = 1}^{n} \frac{k}{φ (k)} = \frac{315 ζ (3)}{2 π^{4}} n - \frac{\log n}{2} + O ((\log n)^{\frac{2}{3}})$ ^[7]
$\sum_{k = 1}^{n} \frac{1}{φ (k)} = \frac{315 ζ (3)}{2 π^{4}} (\log n + γ - \sum_{p prime} \frac{\log p}{p^{2} - p + 1}) + O (\frac{(\log n)^{\frac{2}{3}}}{n})$ ^[8]

(dengan

γ

adalah konstanta Euler–Mascheroni).

$\sum_{\overset{1 \leq k \leq n}{gcd (k, m) = 1}} 1 = n \frac{φ (m)}{m} + O (2^{ω (m)})$

dimana

m > 1

adalah bilangan bulat positif dan

ω (m)

adalah jumlah faktor prima yang berbeda dari

m

.^[9]

Fungsi pembangkit

Deret Dirichlet untuk $φ (n)$ dapat ditulis dalam istilah fungsi zeta Riemann sebagai:^[10]

\sum_{n = 1}^{\infty} \frac{φ (n)}{n^{s}} = \frac{ζ (s - 1)}{ζ (s)} .

Fungsi pembangkit deret Lambert adalah^[11]

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

konvergen untuk $| q | < 1$ .

Keduanya dibuktikan dengan manipulasi deret dasar dan rumus untuk $φ (n)$ .

Rasio bilangan berurutan

Pada tahun 1950 Somayajulu membuktikan^[12]^[13]

lim inf \frac{φ (n + 1)}{φ (n)} = 0

dan

lim sup \frac{φ (n + 1)}{φ (n)} = \infty

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

{\frac{φ (n + 1)}{φ (n)}, n = 1, 2, \dots}

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

{\frac{φ (n)}{n}, n = 1, 2, \dots}

padat dalam interval $(0, 1)$ .

Lihat pula

Catatan

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

Referensi

↑ Euler's totient function. Khan Academy.
↑ sumber pada Wikipedia bahasa Indonesia
↑ Dineva (dalam referensi eksternal), prop. 1
↑ Arnold Walfisz. Weylsche Exponentialsummen in der neueren Zahlentheorie. VEB Deutscher Verlag der Wissenschaften. 1963. Vol. 16.
↑ G. Lomadse. The scientific work of Arnold Walfisz. Acta Arithmetica. Vol. 10 (3). hlm. 227–237.
↑ Arnold Walfisz. Weylsche Exponentialsummen in der neueren Zahlentheorie. VEB Deutscher Verlag der Wissenschaften. 1963. Vol. 16.
↑ R. Sitaramachandrarao. On an error term of Landau II. Rocky Mountain J. Math. 1985. Vol. 15. hlm. 579–588.
↑ R. Sitaramachandrarao. On an error term of Landau II. Rocky Mountain J. Math. 1985. Vol. 15. hlm. 579–588.
↑ Bordellès di pranala luar
↑ sumber pada Wikipedia bahasa Indonesia
↑ sumber pada Wikipedia bahasa Indonesia
↑ Ribenboim, p.38
↑ Sándor, Mitrinović & Crstici (2006) p.16
↑ Ribenboim, p.38
↑ Sándor, Mitrinović & Crstici (2006) p.16
↑ Ribenboim, p.38

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). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

[1] Euler's totient function. Khan Academy.

[2] sumber pada Wikipedia bahasa Indonesia

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

[4] Arnold Walfisz. Weylsche Exponentialsummen in der neueren Zahlentheorie. VEB Deutscher Verlag der Wissenschaften. 1963. Vol. 16.

[5] G. Lomadse. The scientific work of Arnold Walfisz. Acta Arithmetica. Vol. 10 (3). hlm. 227–237.

[6] Arnold Walfisz. Weylsche Exponentialsummen in der neueren Zahlentheorie. VEB Deutscher Verlag der Wissenschaften. 1963. Vol. 16.

[7] R. Sitaramachandrarao. On an error term of Landau II. Rocky Mountain J. Math. 1985. Vol. 15. hlm. 579–588.

[8] R. Sitaramachandrarao. On an error term of Landau II. Rocky Mountain J. Math. 1985. Vol. 15. hlm. 579–588.

[9] Bordellès di pranala luar

[10] sumber pada Wikipedia bahasa Indonesia

[11] sumber pada Wikipedia bahasa Indonesia

[12] Ribenboim, p.38

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

[14] Ribenboim, p.38

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

[16] Ribenboim, p.38

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]