Teorema Euler

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

Pada tahun 1736, Leonhard Euler menerbitkan bukti dari teorema kecil FermatLihat:

 Untuk informasi lebih lanjut mengenai paper ini, termasuk terjemahan bahasa Inggris, lihat: The Euler Archive. (yang dikemukakan oleh Fermat tetapi tanpa bukti), yang merupakan kasus khusus dari teorema Euler ketika  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  bukan bilangan prima.Lihat:
  Teorema Euler muncul sebagai "Teorema 11" pada halaman 102. Paper ini pertama kali dipresentasikan ke Akademi Berlin pada 8 Juni 1758 dan ke Akademi St. Petersburg pada 15 Oktober 1759. Dalam paper ini, fungsi totient Euler, , tidak dinamai tetapi disebut sebagai "numerus partium ad  primarum" (banyaknya bagian prima dengan ; yaitu, banyaknya bilangan asli yang kurang dari  dan relatif prima dengan )
 Untuk informasi lebih lanjut mengenai makalah ini, lihat: The Euler Archive.
 Untuk ulasan pekerjaan Euler selama bertahun-tahun yang mengarah ke teorema Euler, lihat: 

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

Teorema Euler dapat diperumum lebih lanjut dengan teorema Carmichael.

Teorema Euler dapat digunakan untuk menyederhanakan nilai pangkat yang besar pada modulo . Misalnya, untuk mencari digit terakhir dari  (atau dengan kata lain, mencari nilai dari  dalam modulo ), perhatikan bahwa nilai , dan pasangan bilangan 7 dan 10 saling koprima. Berdasarkan teorema Euler, maka didapatkan . Akibatnya,

Secara umum, saat menyederhanakan nilai pangkat dari  pada modulo  (dengan  koprima dengan ), maka cukup bekerja pada modulo  dari perpangkatan :

 jika , maka .

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

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

 Teori grup 
Teorema Euler dapat dibuktikan dengan menggunakan konsep dari teori grup:Ireland & Rosen, corr. 1 to prop 3.3.2

 Bukti langsung 
Teorema Euler juga dapat dibuktikan secara langsung:

 Lihat pula 
 Bilangan 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 paper teori bilangan miliknya: semua bukti dari timbal balik kuadratik, penentuan tanda dari jumlah Gauss, penyelidikan timbal balik bikuadratik, serta catatan yang tidak diterbitkan.







 Pranala luar 



Kategori:Aritmetika modular
Kategori:Teorema dalam teori bilangan
Kategori:Artikel yang memuat pembuktian
Kategori:Leonhard Euler