Teorema Euler

Dalam teori bilangan, teorema Euler (dikenal juga sebagai teorema Fermat–Euler atau teorema totien Euler) menyatakan bahwa jika $a$ dan $n$ merupakan bilangan asli yang saling prima, maka $a^{\phi (n)}$ akan kongruen dengan $1$ dalam modulo $n$, dengan $\phi (n)$ menyatakan fungsi phi Euler. Secara simbolis, maka hal ini dapat dinyatakan sebagai

$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

Pada tahun 1736, Leonhard Euler menerbitkan bukti dari teorema kecil Fermat (yang dikemukakan oleh Fermat tetapi tanpa bukti), yang merupakan kasus khusus dari teorema Euler ketika $n$ merupakan bilangan prima. Euler kemudian memberikan bukti lain dari teorema tersebut, yang berpuncak pada paper tahun 1763 miliknya, di mana ia membuktikan perumuman untuk kasus $n$ bukan bilangan prima.

Konvers dari teorema Euler juga berlaku: jika berlaku kekongruenan di atas, maka $a$ haruslah relatif prima dengan $n$.

Teorema Euler dapat diperumum lebih lanjut dengan teorema Carmichael.

Teorema Euler dapat digunakan untuk menyederhanakan nilai pangkat yang besar pada modulo $n$. Misalnya, untuk mencari digit terakhir dari $7^{222}$ (atau dengan kata lain, mencari nilai dari $7^{222}$ dalam modulo $10$), perhatikan bahwa nilai $\phi (10)=4$, dan pasangan bilangan 7 dan 10 saling koprima. Berdasarkan teorema Euler, maka didapatkan $7^4\equiv 1(\mathrm{mod}10)$. Akibatnya,

$$7^{222}\equiv 7^{4\times 55+2}\equiv (7^4{)}^{55}\times 7^2\equiv 1^{55}\times 7^2\equiv 49\equiv 9(\mathrm{mod}10)$$

Secara umum, saat menyederhanakan nilai pangkat dari $a$ pada modulo $n$ (dengan $a$ koprima dengan $n$), maka cukup bekerja pada modulo $\phi (n)$ dari perpangkatan $a$:

jika $x\equiv y(\mathrm{mod}\phi (n))$, maka $a^x\equiv a^y(\mathrm{mod}n)$.

Teorema Euler menjadi dasar kriptosistem RSA, yang banyak digunakan dalam komunikasi di internet. Dalam kriptosistem ini, teorema Euler digunakan dengan memilih bilangan $n$ sebagai hasil kali dari dua bilangan prima besar. Tingkat keamanan dari sistem ini didasarkan pada tingkat kesulitan dari proses pemfaktoran bilangan $n$.

Bukti

Terdapat beberapa cara untuk membuktikan Teorema Euler, berikut dua diantaranya.

Teori grup

Teorema Euler dapat dibuktikan dengan menggunakan konsep dari teori grup:

Bukti langsung

Teorema Euler juga dapat dibuktikan secara langsung:

&\equiv 1 \cdot \cancel{x_1} \cdot \cancel{x_2} \cdot \cancel{x_3} \cdot \ldots \cdot \cancel{x_{\varphi (n)}} \pmod{n} \\

a^{\varphi (n)} &\equiv 1 \pmod{n} \end{align}</math>}}

Lihat pula

• Bilangan Carmichael
• Kriteria Euler
• Teorema kecil Fermat
• Teorema Wilson

Referensi

Disquisitiones Arithmeticae telah diterjemahkan dari bahasa Latin Ciceronian Gauss ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua paper teori bilangan miliknya: semua bukti dari timbal balik kuadratik, penentuan tanda dari jumlah Gauss, penyelidikan timbal balik bikuadratik, serta catatan yang tidak diterbitkan.

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 27941283 (2025-10-08T17:12:53Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.