Teorema Euler

Dalam teori bilangan, teorema 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
  - a φ ≡ 1 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 a dan n saling koprima. Untuk kasus n adalah suatu bilangan prima p, teorema Euler adalah perumuman dari teorema kecil Fermat. Pada kasus ini, nilai φ = p − 1, dan dengan mengalikan kedua ruas persamaan dengan a, teorema Euler dapat ditulis sebagai
  - a p ≡ p Teorema Euler juga dapat diperumum lebih lanjut dengan teorema Carmichael. Teorema Euler dapat digunakan untuk mengurangi nilai pangkat yang besar pada modulo n. Misalnya, anggap kita perlu untuk mencari digit desimal tempat satuan dari 7 222, dengan kata lain, mencari nilai dari 7 222. Kita dapat mencari bahwa nilai φ = 4, dan mengetahui angka 7 dan 10 saling koprima. Selanjutnya, dengan menggunakan teorema Euler didapatkan 7 4 ≡ 1. Selanjutnya kita tinggal menyederhanakan bentuk 7 222 seperti berikut
  - 7 222 ≡ 7 4 × 55 + 2 ≡ 55 × 7 2 ≡ 1 55 × 7 2 ≡ 49 ≡ 9. Secara umum, mengurangi nilai pangkat dari a pada modulo n, kita cukup bekerja pada modulo φ dalam perpangkatan a :
  - jika x ≡ y, maka a x ≡ a y. Teorema Euler menjadi dasar algoritma RSA, yang banyak digunakan dalam sistem komunikasi di Internet. Dalam algoritma ini, teorema Euler digunakan bersama sebuah bilangan n yang merupakan hasil kali dari dua bilangan prima besar. Tingkat keamanan algoritma tersebut didasarkan pada tingkat kesulitan untuk memfaktorkan bilangan n.