Teorema kecil Fermat

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

$a^p\equiv a(\mathrm{mod}p).$

Sebagai contoh, jika $a=2$ dan $p=7$, maka $2^7=128$ dan nilai dari $128-2=126=7\times 18$ adalah kelipatan $7$.

Jika $a$ tidak habis dibagi dengan $p$, maka Teorema kecil Fermat setara dengan pernyataan bahwa $a^{p-1}-1$ adalah kelipatan $p$, atau dalam persamaan:

$a^{p-1}\equiv 1(\mathrm{mod}p).$

Dengan contoh yang serupa, jika $a=2$ dan $p=7$, maka $2^6=64$ dan nilai dari $64-1=63=7\times 9$ adalah kelipatan $7$.

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 $a$ dan $n$, berlaku

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

dimana $\phi$ melambangkan fungsi phi Euler.

Sejarah

Pierre de Fermat

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 Templat:Mvar adalah bilangan prima dan Templat:Mvar adalah bilangan bulat apa pun yang tidak habis dibagi Templat:Mvar, maka Templat:Math habis dibagi Templat:Mvar.

Pernyataan asli Fermat adalah

Ini dapat diterjemahkan, dengan penjelasan dan rumus yang ditambahkan dalam tanda kurung untuk memudahkan pemahaman, seperti:

Setiap bilangan prima [[[:Templat:Mvar]]] pasti membagi salah satu pangkat minus satu dari [geometris] perkembangan [[[:Templat:Math]]] [yaitu, Templat:Mvar sehingga Templat:Mvar membagi Templat:Math], dan eksponen pangkat ini [[[:Templat:Mvar]]] membagi bilangan prima dikurangi satu [membagi Templat:Math]. Setelah menemukan pangkat pertama [[[:Templat:Mvar]]] yang memenuhi pertanyaan, semua orang yang eksponennya adalah kelipatan eksponen yang pertama memenuhi pertanyaan yang sama [yaitu, semua perkalian dari Templat:Mvar pertama memiliki sifat yang sama].

Fermat tidak mempertimbangkan kasus di mana Templat:Mvar adalah kelipatan dari Templat:Mvar 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.)

Templat:Harvnb</ref>

Sejarah lebih lanjut

Beberapa ahli matematika secara independen membuat hipotesis terkait (terkadang salah disebut Hipotesis Cina) Templat:Math jika dan hanya jika Templat:Mvar adalah bilangan prima. Bagian "jika" benar, dan ini adalah kasus khusus dari teorema kecil Fermat. Namun, bagian "hanya jika" salah: Misalnya, Templat:Math, 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 $n$ dan bilangan bulat apa pun Templat:Mvar koprima hingga Templat:Mvar, adalah

$a^{\phi (n)}\equiv 1(\mathrm{mod}n),$

dimana $\phi (n)$ menunjukkan Fungsi total Euler (yang menghitung bilangan bulat dari 1 hingga Templat:Mvar yang koprima hingga Templat:Mvar). Teorema kecil Fermat kasus khusus, karena jika $n$ adalah bilangan prima, maka $\phi (n)=n-1$.

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

$x\equiv y(\mathrm{mod}\phi (n))\text{implies}{a}^x\equiv a^y(\mathrm{mod}n),$

untuk bilangan bulat Templat:Mvar dan Templat:Mvar. Ini mengikuti dari teorema Euler, karena, jika $x\equiv y(\mathrm{mod}\phi (n))$, sehingga $x=y+k\phi (n)$ untuk beberapa bilangan bulat Templat:Mvar, dan satu memiliki

$a^x=a^{y+\phi (n)k}=a^y(a^{\phi (n)}{)}^k\equiv a^y{1}^k\equiv a^y(\mathrm{mod}n).$

Jika Templat:Mvar 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 Templat:Mvar.

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

$y=x^e(\mathrm{mod}n),$

Templat:Mvar dari nilai Templat:Mvar dan Templat:Mvar jika $\phi (n).$ Faktanya, algoritme Euklides memungkinkan komputasi modular invers dari Templat:Mvar modulo $\phi (n),$ itu adalah bilangan bulat Templat:Mvar maka $ef\equiv 1(\mathrm{mod}\phi (n)).$

$x\equiv x^{ef}\equiv (x^e{)}^f\equiv y^f(\mathrm{mod}n).$

Di sisi lain, jika Templat:Math adalah hasil kali dari dua bilangan prima yang berbeda, maka $\phi (n)=(p-1)(q-1).$ Dalam kasus ini, menemukan Templat:Mvar dari Templat:Mvar dan Templat:Mvar diketahui $\phi (n)$ (ini tidak terbukti, tetapi tidak ada algoritme yang diketahui untuk menghitung Templat:Mvar tanpa mengetahui $\phi (n)$). Jika Templat:Mvar dan $\phi (n),$ faktor Templat:Mvar dan Templat:Mvar mudah untuk disimpulkan, karena seseorang mengetahui hasil kali Templat:Mvar dan jumlahnya $n-\phi (n)+1.$ Ide dasar dari kriptosistem RSA adalah: jika pesan Templat:Mvar dienkripsi sebagai $y=x^e(\mathrm{mod}n),$ menggunakan nilai publik dari Templat:Mvar dan Templat:Mvar, kemudian, dengan pengetahuan saat ini, ia tidak dapat didekripsi tanpa menemukan faktor (rahasia) Templat:Mvar dan Templat:Mvar dari Templat:Mvar.

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 Templat:Mvar

$a^{p-1}\equiv 1(\mathrm{mod}p)$

dan untuk bilangan prima Templat:Mvar membagi Templat:Math

$a^{(p-1)/q}\equiv ̸1(\mathrm{mod}p),$

maka Templat:Mvar adalah bilangan prima.

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

Pseudoprima

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

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

$\gcd (p,\sum _{a=1}^{p-1}{a}^{p-1})=1$

bisa berupa bilangan prima atau bilangan Carmichael.

Uji primalitas Miller–Rabin

Uji primalitas Miller–Rabin menggunakan ekstensi teorema kecil Fermat berikut:

Jika Templat:Mvar adalah bilangan prima ganjil, dan Templat:Math, dengan Templat:Mvar ganjil, lalu untuk setiap Templat:Mvar prima hingga Templat:Mvar, yaitu Templat:Math, atau Templat:Mvar sehingga Templat:Math dan Templat:Math

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

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

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-P | Turunan-Templat:Mvar]]
• Pecahan dengan penyebut utama: bilangan dengan yang berkaitan dengan teorema kecil Fermat
• RSA
• Tabel kekongruenan
• Perkalian modular invers

Referensi

• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation
• Templat:Citation

Bacaan lebih lanjut

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

Pranala luar

• Templat:Commons category inline
• Templat:Britannica
• 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
• Templat:Springer
• Templat:MathWorld
• Templat:MathWorld