Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-25T13:57:08Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29439030; atribusi sumber disertakan.

2026-08-25T13:17:19Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29439030; atribusi sumber disertakan.

Halaman baru

'''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

:<math>a^p \equiv a \pmod{p}.</math>
Sebagai contoh, jika <math>a=2</math> dan <math>p=7</math>, maka <math>2^7=128</math> dan nilai dari <math>128-2=126=7\times18</math> adalah kelipatan <math>7</math>.

Jika <math>a</math> tidak habis dibagi dengan ''<math>p</math>'', maka Teorema kecil Fermat setara dengan pernyataan bahwa <math>a^{p-1} - 1</math> adalah kelipatan ''<math>p</math>'', atau dalam persamaan:
:<math>a^{p-1} \equiv 1 \pmod{p}.</math>
Dengan contoh yang serupa, jika <math>a=2</math> dan <math>p=7</math>, maka <math>2^6=64</math> dan nilai dari <math>64-1=63=7\times9</math> adalah kelipatan <math>7</math>.

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 terakhir Fermat]].

Teorema ini adalah kasus khusus dari [[Teorema Euler]], yang menyatakan bahwa untuk semua bilangan bulat <math>a</math> dan ''<math>n</math>'', berlaku
:<math>a^{\varphi(n)} \equiv 1 \pmod{n},</math>
dimana <math>\varphi</math> 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:

<blockquote>Jika adalah bilangan prima dan adalah bilangan bulat apa pun yang tidak habis dibagi , maka habis dibagi .
</blockquote>

Pernyataan asli Fermat adalah
<blockquote>
</blockquote>
Ini dapat diterjemahkan, dengan penjelasan dan rumus yang ditambahkan dalam tanda kurung untuk memudahkan pemahaman, seperti:
<blockquote>
Setiap bilangan prima [] pasti membagi salah satu pangkat minus satu dari [geometris] [[perkembangan 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].
</blockquote>

Fermat tidak mempertimbangkan kasus di mana adalah kelipatan dari atau membuktikan pernyataannya, hanya menyatakan:
<blockquote></blockquote>
<blockquote>(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.)</blockquote>

[[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 [[Gottfried Leibniz|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]]:

<blockquote></blockquote>

<blockquote>(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.)</blockquote></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 [[#Pseudoprima|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 [[aritmetika modular|modulus]] <math>n</math> dan bilangan bulat apa pun [[koprima]] hingga , adalah

: <math>a^{\varphi (n)} \equiv 1 \pmod n,</math>

dimana <math>\varphi(n)</math> menunjukkan [[Fungsi total Euler]] (yang menghitung bilangan bulat dari 1 hingga yang koprima hingga ). Teorema kecil Fermat kasus khusus, karena jika <math>n</math> adalah bilangan prima, maka <math>\varphi(n)=n-1</math>.

Teorema Euler adalah: untuk setiap bilangan bulat positif , jika bilangan bulat adalah [[bilangan bulat koprima|koprime]] dengan maka
:<math>x \equiv y \pmod{\varphi(n)}\quad\text{implies}\quad a^x \equiv a^y \pmod n, </math>
untuk bilangan bulat dan .
Ini mengikuti dari teorema Euler, karena, jika <math>x \equiv y \pmod{\varphi(n)}</math>, sehingga <math>x=y+k\varphi(n)</math> untuk beberapa bilangan bulat , dan satu memiliki
:<math>a^x = a^{y + \varphi(n)k} = a^y (a^{\varphi(n)})^k \equiv a^y 1^k \equiv a^y \pmod n.</math>

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 [[Eksponensiasi|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
:<math>y=x^e\pmod n,</math>
dari nilai dan jika <math>\varphi(n).</math> Faktanya, [[algoritme Euklides]] memungkinkan komputasi [[modular invers]] dari modulo <math>\varphi(n),</math> itu adalah bilangan bulat maka <math>ef\equiv 1\pmod{\varphi(n)}.</math>
:<math>x\equiv x^{ef}\equiv (x^e)^f \equiv y^f\pmod n.</math>
Di sisi lain, jika adalah hasil kali dari dua bilangan prima yang berbeda, maka <math>\varphi(n)=(p-1)(q-1).</math> Dalam kasus ini, menemukan dari dan diketahui <math>\varphi(n)</math> (ini tidak terbukti, tetapi tidak ada algoritma yang diketahui untuk menghitung tanpa mengetahui <math>\varphi(n)</math>). Jika dan <math>\varphi(n),</math> faktor dan mudah untuk disimpulkan, karena seseorang mengetahui hasil kali dan jumlahnya <math>n-\varphi(n)+1.</math> Ide dasar dari kriptosistem RSA adalah: jika pesan dienkripsi sebagai <math>y=x^e\pmod n,</math> 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 (teori grup)|Teorema Lagrange dalam teori grup]].

== Konversi ==
[[Konversi logis|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
:<math> a^{p-1}\equiv 1\pmod p </math>
dan untuk bilangan prima membagi
:<math> a^{(p-1)/q}\not\equiv 1\pmod p, </math>
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
:<math>\gcd\left(p, \sum_{a=1}^{p-1} a^{p-1}\right)=1</math>
bisa berupa bilangan prima atau bilangan Carmichael.

== Uji primalitas Miller–Rabin ==
[[Uji primalitas Miller–Rabin]] menggunakan ekstensi teorema kecil Fermat berikut:
<blockquote>Jika adalah bilangan prima ganjil, dan , dengan ganjil, lalu untuk setiap prima hingga , yaitu , atau sehingga dan </blockquote>

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'' = 2<sup>''s''</sup> ''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-P | Turunan-]]
* [[Desimal berulang#Pecahan dengan penyebut utama|Pecahan dengan penyebut utama]]: bilangan dengan yang berkaitan dengan teorema kecil Fermat
* [[RSA (algoritma)|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 ==
*
*
* [https://web.archive.org/web/20041022022031/http://bolyai.port5.com/kisfermat.htm János Bolyai and the pseudoprimes] (dalam bahasa Hungaria)
* [http://www.cut-the-knot.org/blue/Fermat.shtml Teorema Kecil Fermat] di [[potong-simpul]]
* [http://www.cut-the-knot.org/blue/Euler.shtml Euler Fungsi dan Teorema] di cut-the-knot
* [http://fermatslasttheorem.blogspot.com/2005/08/fermats-little-theorem.html Teorema Kecil Fermat dan Bukti Sophie]
*
*
*

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Teorema+kecil+Fermat&oldid=29439030 Wikipedia bahasa Indonesia], revisi 29439030 (2026-07-10T08:20:06Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

Teorema kecil Fermat - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29439030; atribusi sumber disertakan.