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

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.