Fungsi Totient Euler & Teorema Euler-Fermat

Pengukuran banyaknya bilangan bulat positif yang saling prima dengan n dan sifat aritmetika modularnya.

📅 Dibuat: 2 Agustus 2026

🔄 Diperbarui: 2 Agustus 2026

Fungsi Totient Euler $\phi(n)$ menghitung banyaknya bilangan bulat $k$ dalam rentang $1 \le k \le n$ sedemikian sehingga $\gcd(k, n) = 1$ .

Formula Perhitungan

Teorema 6.1 (Formula Totient Euler)

Jika faktorisasi prima dari $n$ adalah $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$ , maka: $\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right)$

Teorema Euler-Fermat

Teorema 6.2 (Teorema Euler)

Jika $\gcd(a, n) = 1$ , maka: $a^{\phi(n)} \equiv 1 \pmod n$

Lihat juga:

Prinsip Inklusi-Eksklusi untuk penurunan kombinatorial dari $\phi(n)$ .
Teorema Lagrange untuk pembuktian berbasis orde grup $(\mathbb{Z}/n\mathbb{Z})^\times$ .

🔗

Materi Terkait (Linked References) (1)

Kombinatorika Bab 1

Prinsip Inklusi-Eksklusi (PIE)

Teknik penghitungan kardinalitas gabungan beberapa himpunan berhingga dengan memperhitungkan irisan berselang-seling.