Teorema kecil Fermat

Teorema kecil Fermat menyatakan bahwa jika  adalah bilangan prima, maka untuk setiap bilangan bulat , nilai dari  adalah kelipatan dari . Dalam notasi aritmetika modular, hubungan ini dituliskan sebagai

Sebagai contoh, jika  dan , maka  dan nilai dari  adalah kelipatan .

Jika  tidak habis dibagi dengan , maka Teorema kecil Fermat setara dengan pernyataan bahwa  adalah kelipatan , atau dalam persamaan: 

Dengan contoh yang serupa, jika  dan , maka  dan nilai dari  adalah kelipatan .

Teorema kecil Fermat adalah dasar untuk test keprimaan Fermat dan salah satu hasil penting dalam teori bilangan. Namanya diambil dari matematikawan Prancis Pierre de Fermat, yang menuliskannya pada tahun 1640. Teorema ini disebut "kecil" untuk membedakannya dari Teorema terakhir Fermat.

Teorema ini adalah kasus khusus dari Teorema Euler, yang menyatakan bahwa untuk semua bilangan bulat  dan , berlaku

dimana  melambangkan fungsi phi Euler.

Sejarah 

Pierre de Fermat pertama kali menyatakan teorema tersebut dalam sebuah surat tertanggal 18 Oktober 1640, kepada teman dan orang kepercayaannya Frénicle de Bessy. Rumusannya setara dengan berikut ini:

Jika  adalah bilangan prima dan  adalah bilangan bulat apa pun yang tidak habis dibagi , maka  habis dibagi .

Pernyataan asli Fermat adalah 

Ini dapat diterjemahkan, dengan penjelasan dan rumus yang ditambahkan dalam tanda kurung untuk memudahkan pemahaman, seperti:
Setiap bilangan prima [] pasti membagi salah satu pangkat minus satu dari [geometris]  perkembangan []  [yaitu,  sehingga  membagi ], dan eksponen pangkat ini [] membagi bilangan prima dikurangi satu [membagi ]. Setelah menemukan pangkat pertama [] yang memenuhi pertanyaan, semua orang yang eksponennya adalah kelipatan eksponen yang pertama memenuhi pertanyaan yang sama [yaitu, semua perkalian dari  pertama memiliki sifat yang sama].

Fermat tidak mempertimbangkan kasus di mana  adalah kelipatan dari  atau membuktikan pernyataannya, hanya menyatakan:

(Dan proposisi ini umumnya benar untuk semua deret [ sic ] dan untuk semua bilangan prima; Saya akan mengirimkan demonstrasi kepada Anda, jika saya tidak takut terjadi terlalu lama.)

Euler memberikan bukti terbitan pertama pada tahun 1736, dalam makalah berjudul "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" dalam Proceedings di St. Petersburg. Akademi Petersburg, tetapi Leibniz telah memberikan bukti yang hampir sama dalam sebuah manuskrip yang tidak diterbitkan dari beberapa waktu sebelum 1683.

Istilah "teorema kecil Fermat" pertama kali digunakan di media cetak pada tahun 1913 di Zahlentheorie oleh Kurt Hensel:

(Ada teorema fundamental yang berlaku di setiap grup berhingga, biasanya disebut teorema kecil Fermat karena Fermat adalah orang pertama yang membuktikan bagian yang sangat khusus darinya.)</ref>

Sejarah lebih lanjut 

Beberapa ahli matematika secara independen membuat hipotesis terkait (terkadang salah disebut Hipotesis Cina)  jika dan hanya jika  adalah bilangan prima. Bagian "jika" benar, dan ini adalah kasus khusus dari teorema kecil Fermat. Namun, bagian "hanya jika" salah: Misalnya, , but 341 = 11 × 31 adalah pseudoprima. Lihat di bawah.

Bukti 

Beberapa bukti teorema kecil Fermat diketahui. Ini sering dibuktikan hasil sampingan/langsung (corollary) dari Teorema Euler.

Generalisasi 
Teorema Euler adalah generalisasi dari teorema kecil Fermat: untuk modulus  dan bilangan bulat apa pun  koprima hingga , adalah

 

dimana  menunjukkan Fungsi total Euler (yang menghitung bilangan bulat dari 1 hingga  yang koprima hingga ). Teorema kecil Fermat kasus khusus, karena jika  adalah bilangan prima, maka .

Teorema Euler adalah: untuk setiap bilangan bulat positif , jika bilangan bulat  adalah koprime dengan  maka

untuk bilangan bulat  dan .
Ini mengikuti dari teorema Euler, karena, jika , sehingga  untuk beberapa bilangan bulat , dan satu memiliki

Jika  adalah bilangan prima, ini juga merupakan akibat wajar dari teorema kecil Fermat. Ini banyak digunakan dalam aritmetika modular, karena ini memungkinkan pengurangan eksponen modular dengan eksponen besar menjadi eksponen yang lebih kecil dari .

Jika  bukan bilangan prima, ini digunakan di kriptografi kunci publik, biasanya di kriptografi RSA dengan cara berikut: jika

 dari nilai  dan  jika  Faktanya, algoritme Euklides memungkinkan komputasi modular invers dari  modulo  itu adalah bilangan bulat  maka 

Di sisi lain, jika  adalah hasil kali dari dua bilangan prima yang berbeda, maka  Dalam kasus ini, menemukan  dari  dan  diketahui  (ini tidak terbukti, tetapi tidak ada algoritme yang diketahui untuk menghitung  tanpa mengetahui ). Jika  dan  faktor  dan  mudah untuk disimpulkan, karena seseorang mengetahui hasil kali  dan jumlahnya  Ide dasar dari kriptosistem RSA adalah: jika pesan  dienkripsi sebagai  menggunakan nilai publik dari  dan , kemudian, dengan pengetahuan saat ini, ia tidak dapat didekripsi tanpa menemukan faktor (rahasia)  dan  dari .

Teorema kecil Fermat juga terkait dengan Fungsi Carmichael dan Teorema Carmichael, serta Teorema Lagrange dalam teori grup.

Konversi 
Kebalikan dari teorema kecil Fermat umumnya tidak benar, karena gagal untuk bilangan Carmichael. Namun, bentuk teorema yang sedikit lebih kuat adalah benar, dan ini dikenal sebagai teorema Lehmer. Teorema tersebut adalah sebagai berikut:

Jika bilangan bulat  

dan untuk bilangan prima  membagi  

maka  adalah bilangan prima.

Teorema ini membentuk dasar untuk uji primalitas Lucas, sebuah uji primaliti.

Pseudoprima 

Jika  dan  adalah bilangan coprime sehingga  habis dibagi , maka  tidak perlu bilangan prima. Jika tidak, maka  disebut (Fermat) pseudoprima ke basis .  Pseudoprime pertama ke basis 2 ditemukan pada tahun 1820 oleh Pierre Frédéric Sarrus: 341 = 11 × 31.

Bilangan  yang merupakan pseudoprime Fermat ke basis  untuk setiap bilangan  yang koprima dengan  disebut bilangan Carmichael (misalnya 561). Bergantian, bilangan  memenuhi persamaan

bisa berupa bilangan prima atau bilangan Carmichael.

Uji primalitas Miller–Rabin 
Uji primalitas Miller–Rabin menggunakan ekstensi teorema kecil Fermat berikut: 
Jika  adalah bilangan prima ganjil, dan , dengan  ganjil, lalu untuk setiap  prima hingga , yaitu , atau  sehingga  dan 

Hasil ini dapat disimpulkan dari teorema kecil Fermat dengan fakta bahwa, jika  adalah bilangan prima ganjil, maka bilangan bulat modulo  membentuk medan berhingga, di mana  adalah 1 dengan -1.

Uji Miller–Rabin menggunakan properti ini dengan cara berikut:{math|1=p =  2s  d + 1}}, dengan  ganjil, bilangan bulat ganjil yang primalitasnya harus diuji, pilih secara acak  sehingga ; maka ; jika  bukan 1 atau −1, maka kuadratkan berulang kali modulo  sampai Anda mendapatkan 1, −1, atau telah mengkuadratkan  kali. Jika  dan −1 belum diperoleh, maka  bukan bilangan prima. Jika tidak,  mungkin bilangan prima atau tidak. Jika  bukan bilangan prima, probabilitas hal ini dibuktikan dengan pengujian lebih tinggi dari 1/4. Oleh karena itu, setelah  uji acak non-konklusif, probabilitas bahwa  bukan bilangan prima lebih rendah dari , dan karenanya dapat dibuat serendah yang diinginkan, dengan meningkatkan .

Singkatnya, pengujian tersebut membuktikan bahwa suatu bilangan bukan bilangan prima, atau menyatakan bahwa bilangan tersebut adalah bilangan prima dengan probabilitas kesalahan yang dapat dipilih rendah.
Tes ini sangat sederhana untuk diterapkan dan secara komputasi lebih efisien daripada semua tes deterministik yang diketahui. Oleh karena itu, biasanya digunakan sebelum memulai pembuktian keutamaan.

Lihat pula 

 Hasil bagi Fermat
 Endomorfisme Frobenius
  Turunan-
 Pecahan dengan penyebut utama: bilangan dengan yang berkaitan dengan teorema kecil Fermat
 RSA
 Tabel kekongruenan
 Perkalian modular invers

Catatan

Referensi

Bacaan lebih lanjut 
 Paulo Ribenboim (1995). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. .  pp. 22–25, 49.

Pranala luar 

 
 János Bolyai and the pseudoprimes (dalam bahasa Hungaria)
 Teorema Kecil Fermat di potong-simpul
 Euler Fungsi dan Teorema di cut-the-knot
 Teorema Kecil Fermat dan Bukti Sophie
 
 
 

Aritmetika modular
Teorema tentang bilangan prima