Teorema Euler itu apa sih?

Dalam teori bilangan, teorema Euler (juga dikenal sebagai teorema Fermat–Euler atau teorema total Euler) menyatakan bahwa jika n dan a adalah bilangan bulat positif yang saling koprima, maka a pangkat fungsi phi Euler dari n akan kongruen dengan satu dalam modulo n. Secara matematis hal ini dapat dinyatakan sebagai

dengan  adalah fungsi phi Euler. Pada tahun 1736, Leonhard Euler mempublikasikan bukti teorema kecil Fermat versinya, karena Fermat tidak menyertakan bukti teorema tersebut. Selanjutnya, Euler menerbitkan bukti lain dari teorema tersebut, yang berpuncak pada "Teorema Euler" dalam penelitiannya tahun 1763, di mana ia mencoba untuk menemukan eksponen terkecil sehinga teorema kecil Fermat selalu bernilai benar.

Kebalikan dari teorema Euler: jika kekongruenan di atas benar, maka  dan  saling koprima.

Untuk kasus  adalah suatu bilangan prima , teorema Euler adalah perumuman dari teorema kecil Fermat. Pada kasus ini, nilai , dan dengan mengalikan kedua ruas persamaan dengan , teorema Euler dapat ditulis sebagai

Teorema Euler juga dapat diperumum lebih lanjut dengan teorema Carmichael.

Teorema Euler dapat digunakan untuk mengurangi nilai pangkat yang besar pada modulo . Misalnya, anggap kita perlu untuk mencari digit desimal tempat satuan dari , dengan kata lain, mencari nilai dari . Kita dapat mencari bahwa nilai , dan mengetahui angka 7 dan 10 saling koprima. Selanjutnya, dengan menggunakan teorema Euler didapatkan  . Selanjutnya kita tinggal menyederhanakan bentuk  seperti berikut