Teorema Euler

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

 .

Secara umum, mengurangi nilai pangkat dari  pada modulo  (dengan  dan  saling koprima), kita cukup bekerja pada modulo  dalam perpangkatan :

 jika , maka .

Teorema Euler menjadi dasar algoritma RSA, yang banyak digunakan dalam sistem komunikasi di Internet. Dalam algoritma ini, teorema Euler digunakan bersama sebuah bilangan  yang merupakan hasil kali dari dua bilangan prima besar. Tingkat keamanan algoritma tersebut didasarkan pada tingkat kesulitan untuk memfaktorkan bilangan .

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

Teori grup 
Teorema Euler dapat dibuktikan dengan menggunakan konsep dari teori grup: Kelas residu modulo  yang coprime untuk  membentuk kelompok dalam perkalian (lihat artikel Grup perkalian bilangan bulat modulo ). urutan dari grup adalah . Teorema Lagrange urutan subgrup dari sebuah grup hingga membagi urutan seluruh grup, dalam hal ini . Jika  bilangan koprima sampai  maka  salah satu kelas residu, dan pangkat  modulo  subgrup dari grup kelas residu, dengan . Teorema Lagrange mengatakan  harus membagi , yaitu bilangan bulat  sedemikian rupa sehingga . Ini kemudian menyiratkan,

Bukti langsung 
Teorema Euler juga dapat dibuktikan secara langsung: Anggap  sebagai sistem residu yang dikurangi () dan biarkan  koprima bilangan bulat . Buktinya bergantung dasar bahwa perkalian dengan  yaitu : dengan kata, jika  maka . (Hukum pembatalxan ini dibuktikan dalam artikel Grup perkalian bilangan bulat modulo .) Yaitu, himpunan  dan , dianggap sebagai himpunan kelas (), identik (sebagai himpunan), jadi produk dari semua bilangan di  kongruen () ke produk dari bilangan :
 dan menggunakan hukum pembatalan untuk  dari teorema Euler:

Hasil bagi Euler 
Hasil bagi Euler dari bilangan bulat a dengan n didefinisikan sebagai:

Hasil bagi Fermat adalah kasus khusus dari hasil bagi Euler ketika n berupa bilangan prima.

Bilangan ganjil n yang membagi  disebut bilangan Wieferich. Hal tersebut setara dengan mengatakan . Sebagai perumuman, sebuah bilangan n yang koprima dengan bilangan bulat positif a, dan n membagi , disebut bilangan Wieferich (yang diperumum) pada basis a. Dengan kata lain, bilangan tersebut memenuhi .

Berikut adalah daftar bilangan Wieferich pada basis , untuk , yang dicari sampai 1048576.

Basis terkecil dari  sehingga  merupakan bilangan Wieferich termuat dalam barisan
2, 5, 8, 7, 7, 17, 18, 15, 26, 7, 3, 17, 19, 19, 26, 31, 38, 53, 28, 7, 19, 3, 28, 17, 57, 19, 80, 19, 14, 107, 115, 63, 118, 65, 18, 53, 18, 69, 19, 7, 51, 19, 19, 3, 26, 63, 53, 17, 18, 57, ...

Lihat pula 
 Fungsi Carmichael
 Kriteria Euler
 Teorema kecil Fermat
 Teorema Wilson

Catatan

Referensi 
Disquisitiones Arithmeticae telah diterjemahkan dari bahasa Latin Ciceronian Gauss ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua makalahnya tentang teori bilangan: semua bukti tentang reciprocity kuadrat, penentuan tanda dari jumlah Gauss, penyelidikan tentang biquadratic reciprocity, dan catatan yang tidak diterbitkan.

Pranala luar 
 
 Euler-Fermat Theorem at PlanetMath

Aritmetika modular
Teorema dalam teori bilangan
Artikel yang berisi bukti
Leonhard Euler