Teorema kecil Fermat: Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi terkini sejak 23 Oktober 2021 00.48

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

a^{p}\equiv a{\pmod {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{\pmod {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^{\varphi (n)}\equiv 1{\pmod {n}},

dimana $\varphi$ 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:^[1]

Jika $p$ adalah bilangan prima dan $a$ adalah bilangan bulat apa pun yang tidak habis dibagi $p$ , maka $a p - 1 - 1$ habis dibagi $p$ .

Pernyataan asli Fermat adalah

Tout nombre premier mesure infailliblement une des puissances $-1$ de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné $-1$ ; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.

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

Setiap bilangan prima [ $p$ ] pasti membagi salah satu pangkat minus satu dari [geometris] perkembangan [ $a, a 2, a 3, ...$ ] [yaitu, $t$ sehingga $p$ membagi $a t - 1$ ], dan eksponen pangkat ini [ $t$ ] membagi bilangan prima dikurangi satu [membagi $p - 1$ ]. Setelah menemukan pangkat pertama [ $t$ ] yang memenuhi pertanyaan, semua orang yang eksponennya adalah kelipatan eksponen yang pertama memenuhi pertanyaan yang sama [yaitu, semua perkalian dari $t$ pertama memiliki sifat yang sama].

Fermat tidak mempertimbangkan kasus di mana $a$ adalah kelipatan dari $p$ atau membuktikan pernyataannya, hanya menyatakan:^[2]

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

(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.)^[3]

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,^[4] tetapi Leibniz telah memberikan bukti yang hampir sama dalam sebuah manuskrip yang tidak diterbitkan dari beberapa waktu sebelum 1683.^[1]

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

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.

(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.)

Albert 2015, hlm. 206</ref>

Sejarah lebih lanjut

Beberapa ahli matematika secara independen membuat hipotesis terkait (terkadang salah disebut Hipotesis Cina) $2 p \equiv 2 (mod p)$ jika dan hanya jika $p$ adalah bilangan prima. Bagian "jika" benar, dan ini adalah kasus khusus dari teorema kecil Fermat. Namun, bagian "hanya jika" salah: Misalnya, $2341 \equiv 2 (mod 341)$ , 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 $a$ koprima hingga $n$ , adalah

a^{\varphi (n)}\equiv 1{\pmod {n}},

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

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

x\equiv y{\pmod {\varphi (n)}}\quad {\text{implies}}\quad a^{x}\equiv a^{y}{\pmod {n}},

untuk bilangan bulat $x$ dan $y$ . Ini mengikuti dari teorema Euler, karena, jika $x\equiv y{\pmod {\varphi (n)}}$ , sehingga $x=y+k\varphi (n)$ untuk beberapa bilangan bulat $k$ , dan satu memiliki

a^{x}=a^{y+\varphi (n)k}=a^{y}(a^{\varphi (n)})^{k}\equiv a^{y}1^{k}\equiv a^{y}{\pmod {n}}.

Jika $n$ 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 $n$ .

Jika $n$ bukan bilangan prima, ini digunakan di kriptografi kunci publik, biasanya di kriptografi RSA dengan cara berikut:^[5] jika

y=x^{e}{\pmod {n}},

$x$ dari nilai $e$ dan $n$ jika $\varphi (n).$ Faktanya, algoritme Euklides memungkinkan komputasi modular invers dari $e$ modulo $\varphi (n),$ itu adalah bilangan bulat $f$ maka $ef\equiv 1{\pmod {\varphi (n)}}.$

x\equiv x^{ef}\equiv (x^{e})^{f}\equiv y^{f}{\pmod {n}}.

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

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 $a$

a^{p-1}\equiv 1{\pmod {p}}

dan untuk bilangan prima $q$ membagi $p - 1$

a^{(p-1)/q}\not \equiv 1{\pmod {p}},

maka $p$ adalah bilangan prima.

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

Pseudoprima

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

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

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

bisa berupa bilangan prima atau bilangan Carmichael.

Uji primalitas Miller–Rabin

Uji primalitas Miller–Rabin menggunakan ekstensi teorema kecil Fermat berikut:^[8]

Jika $p$ adalah bilangan prima ganjil, dan $p - 1 = 2 s d$ , dengan $d$ ganjil, lalu untuk setiap $a$ prima hingga $p$ , yaitu $a d \equiv 1 mod p$ , atau $t$ sehingga $0 \leq t < s$ dan $a 2 t d \equiv -1 mod p$

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

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

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$
Pecahan dengan penyebut utama: bilangan dengan yang berkaitan dengan teorema kecil Fermat
RSA
Tabel kekongruenan
Perkalian modular invers

Catatan

^ ^a ^b Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama Burton
^ Fermat, Pierre (1894), Tannery, P.; Henry, C., ed., Oeuvres de Fermat. Tome 2: Correspondance, Paris: Gauthier-Villars, hlm. 206–212 (in French)
^ Mahoney 1994, hlm. 295 for the English translation
^ Ore 1988, hlm. 273
^ Trappe, Wade; Washington, Lawrence C. (2002), Introduction to Cryptography with Coding Theory, Prentice-Hall, hlm. 78, ISBN 978-0-13-061814-6
^ Sloane, N.J.A. (ed.). "Sequence A128311 (Remainder upon division of 2ⁿ⁻¹−1 by n.)". On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Sarrus, Frédéric (1819–1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Demonstration of the falsity of the theorem stated on page 320 of the 9th volume of this collection]. Annales de Mathématiques Pures et Appliquées (dalam bahasa Prancis). 10: 184–187.
^ Rempe-Gillen, Lasse; Waldecker, Rebecca (2013-12-11). "4.5.1. Lemma (Roots of unity modulo a prime)". Primality Testing for Beginners (dalam bahasa Inggris). American Mathematical Soc. ISBN 9780821898833.

Referensi

Albert, A. Adrian (2015) [1938], Modern higher algebra, Cambridge University Press, ISBN 978-1-107-54462-8
Burton, David M. (2011), The History of Mathematics / An Introduction (edisi ke-7th), McGraw-Hill, ISBN 978-0-07-338315-6
Long, Calvin T. (1972), Elementary Introduction to Number Theory (edisi ke-2nd), Lexington: D. C. Heath and Company, LCCN 77171950
Mahoney, Michael Sean (1994), The Mathematical Career of Pierre de Fermat, 1601–1665 (edisi ke-2nd), Princeton University Press, ISBN 978-0-691-03666-3
Ore, Oystein (1988) [1948], Number Theory and Its History, Dover, ISBN 978-0-486-65620-5
Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766

Bacaan lebih lanjut

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

Pranala luar

Media tentang Teorema kecil Fermat di Wikimedia Commons
Fermat's theorem di Encyclopædia 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
Hazewinkel, Michiel, ed. (2001) [1994], "Fermat's little theorem", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4
(Inggris) Weisstein, Eric W. "Fermat's Little Theorem". MathWorld.
(Inggris) Weisstein, Eric W. "Fermat's Little Theorem Converse". MathWorld.

[Burton-1] Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama Burton

[2] Fermat, Pierre (1894), Tannery, P.; Henry, C., ed., Oeuvres de Fermat. Tome 2: Correspondance, Paris: Gauthier-Villars, hlm. 206–212 (in French)

[3] Mahoney 1994, hlm. 295 for the English translation

[4] Ore 1988, hlm. 273

[5] Trappe, Wade; Washington, Lawrence C. (2002), Introduction to Cryptography with Coding Theory, Prentice-Hall, hlm. 78, ISBN 978-0-13-061814-6

[6] Sloane, N.J.A. (ed.). "Sequence A128311 (Remainder upon division of 2ⁿ⁻¹−1 by n.)". On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[7] Sarrus, Frédéric (1819–1820). "Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil" [Demonstration of the falsity of the theorem stated on page 320 of the 9th volume of this collection]. Annales de Mathématiques Pures et Appliquées (dalam bahasa Prancis). 10: 184–187.

[8] Rempe-Gillen, Lasse; Waldecker, Rebecca (2013-12-11). "4.5.1. Lemma (Roots of unity modulo a prime)". Primality Testing for Beginners (dalam bahasa Inggris). American Mathematical Soc. ISBN 9780821898833.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

@@ Baris 1: / Baris 1: @@
+{{Periksa terjemahan|en|Fermat little theorem}}
-'''Teorema kecil Fermat''' menyatakan bahwa jika ''p'' adalah [[bilangan prima]], maka untuk setiap [[bilangan bulat]] ''a'',
+'''Teorema kecil Fermat''' menyatakan bahwa jika ''{{math|''p''}}'' adalah [[bilangan prima]], maka untuk setiap [[bilangan bulat]] ''{{math|''a''}}'', nilai dari {{math|''a''<sup> ''p'' </sup> − ''a''}} adalah kelipatan dari ''{{math|''p''}}''. Dalam notasi [[aritmetika modular]], hubungan ini dituliskan sebagai
-:<math>a^{p-1} = a \pmod{p}</math>
+:<math>a^p \equiv a \pmod{p}.</math>
-Ini berarti jika kita mengambil sembarang bilangan ''a'', mengalikan dengan dirinya sendiri sebanyak ''p'' kali, dan kemudian mengurangi ''a'', hasilnya akan habis dibagi dengan ''p''. Namanya diambil dari [[matematikawan]] [[Perancis]] [[Pierre de Fermat]].
+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:
-{{DEFAULTSORT:Kecil Fermat}}
+:<math>a^{p-1} \equiv 1 \pmod{p}.</math>
-{{matematika-stub}}
+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>.
-[[Kategori:Teorema matematika]]
+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]].
-[[ar:مبرهنة فيرما]]
-[[bg:Малка теорема на Ферма]]
+Teorema ini adalah kasus khusus dari [[Teorema Euler]], yang menyatakan bahwa untuk semua bilangan bulat <math>a</math> dan ''<math>n</math>'', berlaku
-[[ca:Petit teorema de Fermat]]
+:<math>a^{\varphi(n)} \equiv 1 \pmod{n},</math>
-[[cs:Malá Fermatova věta]]
+dimana <math>\varphi</math> melambangkan [[fungsi phi Euler]].
-[[de:Kleiner fermatscher Satz]]
-[[en:Fermat's little theorem]]
+== Sejarah ==
-[[eo:Malgranda teoremo de Fermat]]
-[[es:Pequeño teorema de Fermat]]
+[[Berkas:Pierre de Fermat.jpg|thumb|right|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:<ref name=Burton />
-[[fa:قضیه کوچک فرما]]
-[[fi:Fermat'n pieni lause]]
+<blockquote>Jika {{mvar | p}} adalah bilangan prima dan {{mvar | a}} adalah bilangan bulat apa pun yang tidak habis dibagi {{mvar | p}}, maka {{math|''a''<sup> ''p'' − 1</sup> − 1}} habis dibagi {{mvar | p}}.
-[[fr:Petit théorème de Fermat]]
+</blockquote>
-[[he:המשפט הקטן של פרמה]]
-[[hu:Kis Fermat-tétel]]
-[[it:Piccolo teorema di Fermat]]
+Pernyataan asli Fermat adalah
+<blockquote>{{lang|fr|Tout nombre premier mesure infailliblement une des puissances <math>-1</math> de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné <math>-1</math>; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.}}
-[[ja:フェルマーの小定理]]
+</blockquote>
-[[ka:ფერმას მცირე თეორემა]]
+Ini dapat diterjemahkan, dengan penjelasan dan rumus yang ditambahkan dalam tanda kurung untuk memudahkan pemahaman, seperti:
-[[kk:Ферманың кіші теоремасы]]
+<blockquote>
-[[ko:페르마의 소정리]]
+Setiap bilangan prima [{{mvar | p}}] pasti membagi salah satu pangkat minus satu dari [geometris] [[perkembangan geometris | perkembangan]] [{{math|''a'', ''a''<sup>2</sup>,  ''a''<sup>3</sup>, ... }}]  [yaitu, {{mvar | t}} sehingga {{mvar | p}} membagi {{math|''a<sup>t</sup>'' – 1}}], dan eksponen pangkat ini [{{mvar | t}}] membagi bilangan prima dikurangi satu [membagi {{math|''p'' – 1}}]. Setelah menemukan pangkat pertama [{{mvar | t}}] yang memenuhi pertanyaan, semua orang yang eksponennya adalah kelipatan eksponen yang pertama memenuhi pertanyaan yang sama [yaitu, semua perkalian dari {{mvar | t}} pertama memiliki sifat yang sama].
-[[lt:Mažoji Ferma teorema]]
+</blockquote>
-[[mn:Фермагийн бага теорем]]
-[[nl:Kleine stelling van Fermat]]
+Fermat tidak mempertimbangkan kasus di mana {{mvar | a}} adalah kelipatan dari {{mvar | p}} atau membuktikan pernyataannya, hanya menyatakan:<ref>{{citation|first=Pierre|last=Fermat|title=Oeuvres de Fermat. Tome 2: Correspondance|editor-last1=Tannery|editor-first1=P.|editor-last2=Henry|editor-first2=C.|year=1894|place=Paris|publisher=Gauthier-Villars|url=https://archive.org/stream/oeuvresdefermat02ferm#page/206/mode/2up|pages=206–212}} (in French)</ref>
-[[pl:Małe twierdzenie Fermata]]
+<blockquote>{{lang|fr|Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.}}</blockquote>
-[[pt:Teste de primalidade de Fermat]]
+<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.)<ref>{{harvnb|Mahoney|1994|page=295}} for the English translation</ref></blockquote>
-[[ro:Mica teoremă a lui Fermat]]
-[[ru:Малая теорема Ферма]]
+[[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,<ref>{{harvnb|Ore|1988|page=273}}</ref> tetapi [[Gottfried Leibniz|Leibniz]] telah memberikan bukti yang hampir sama dalam sebuah manuskrip yang tidak diterbitkan dari beberapa waktu sebelum 1683.<ref name=Burton />
-[[sk:Malá Fermatova veta]]
-[[sl:Fermatov mali izrek]]
+Istilah "teorema kecil Fermat" pertama kali digunakan di media cetak pada tahun 1913 di ''Zahlentheorie'' oleh [[Kurt Hensel]]:
-[[sr:Мала Фермаова теорема]]
-[[sv:Fermats lilla sats]]
+<blockquote>{{lang|de|Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.}}</blockquote>
-[[ta:ஃபெர்மாவின் சிறிய தேற்றம்]]
-[[th:ทฤษฎีบทเล็กของแฟร์มาต์]]
+<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>{{Harvnb|Albert|2015|p=206}}</ref>
-[[tr:Fermat'nın küçük teoremi]]
-[[uk:Мала теорема Ферма]]
+=== Sejarah lebih lanjut ===
-[[vi:Định lý nhỏ Fermat]]
+{{main|Hipotesis Cina}}
-[[zh:费马小定理]]
+Beberapa ahli matematika secara independen membuat hipotesis terkait (terkadang salah disebut Hipotesis Cina) {{math|2<sup>''p''</sup> ≡ 2 (mod ''p'')}} jika dan hanya jika {{mvar|p}} adalah bilangan prima. Bagian "jika" benar, dan ini adalah kasus khusus dari teorema kecil Fermat. Namun, bagian "hanya jika" salah: Misalnya, {{math|2<sup>341</sup> ≡ 2 (mod 341)}}, but 341&nbsp;=&nbsp;11&nbsp;×&nbsp;31 adalah [[pseudoprima]]. Lihat [[#Pseudoprima|di bawah]].
+== Bukti ==
+{{main|Bukti teorema kecil Fermat}}
+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 {{mvar|a}} [[koprima]] hingga {{mvar|n}}, 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 {{mvar|n}} yang koprima hingga {{mvar|n}}). 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 {{mvar | n}}, jika bilangan bulat {{mvar | a}} adalah [[bilangan bulat koprima|koprime]] dengan {{mvar | n}} maka
+:<math>x \equiv y \pmod{\varphi(n)}\quad\text{implies}\quad a^x \equiv a^y \pmod n, </math>
+untuk bilangan bulat {{mvar | x}} dan {{mvar | y}}.
+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 {{mvar | k}}, 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 {{mvar | n}} 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 {{mvar | n}}.
+Jika {{mvar | n}} bukan bilangan prima, ini digunakan di [[kriptografi kunci publik]], biasanya di [[kriptografi RSA]] dengan cara berikut:<ref>{{citation|first1=Wade|last1=Trappe|first2=Lawrence C.|last2=Washington|title=Introduction to Cryptography with Coding Theory|year=2002|publisher=Prentice-Hall|isbn=978-0-13-061814-6|page=78}}</ref> jika
+:<math>y=x^e\pmod n,</math>
+{{mvar|x}} dari nilai {{mvar|e}} dan {{mvar|n}} jika <math>\varphi(n).</math> Faktanya, [[algoritme Euklides]] memungkinkan komputasi [[modular invers]] dari {{mvar|e}} modulo <math>\varphi(n),</math> itu adalah bilangan bulat {{mvar | f}} 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 {{math|1=''n'' = ''pq''}} adalah hasil kali dari dua bilangan prima yang berbeda, maka <math>\varphi(n)=(p-1)(q-1).</math> Dalam kasus ini, menemukan {{mvar|f}} dari {{mvar|n}} dan {{mvar|e}} diketahui <math>\varphi(n)</math> (ini tidak terbukti, tetapi tidak ada algoritme yang diketahui untuk menghitung {{mvar|f}} tanpa mengetahui <math>\varphi(n)</math>). Jika {{mvar|n}} dan <math>\varphi(n),</math> faktor {{mvar|p}} dan {{mvar|q}} mudah untuk disimpulkan, karena seseorang mengetahui hasil kali {{mvar|n}} dan jumlahnya <math>n-\varphi(n)+1.</math> Ide dasar dari kriptosistem RSA adalah: jika pesan {{mvar|x}} dienkripsi sebagai <math>y=x^e\pmod n,</math> menggunakan nilai publik dari {{mvar|n}} dan {{mvar|e}}, kemudian, dengan pengetahuan saat ini, ia tidak dapat didekripsi tanpa menemukan faktor (rahasia) {{mvar|p}} dan {{mvar|q}} dari {{mvar|n}}.
+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 {{mvar|a}}
+:<math> a^{p-1}\equiv 1\pmod p </math>
+dan untuk bilangan prima {{mvar|q}} membagi {{math|''p'' &minus; 1}}
+:<math> a^{(p-1)/q}\not\equiv 1\pmod p, </math>
+maka {{mvar|p}} adalah bilangan prima.
+Teorema ini membentuk dasar untuk [[uji primalitas Lucas]], sebuah [[uji primaliti]].
+== Pseudoprima ==
+{{main|Pseudoprima}}
+Jika {{mvar|a}} dan {{mvar|p}} adalah bilangan coprime sehingga {{math|''a''<sup>''p''−1</sup> − 1}} habis dibagi {{mvar | p}}, maka {{mvar|p}} tidak perlu bilangan prima. Jika tidak, maka {{mvar|p}} disebut ''(Fermat) pseudoprima'' ke basis {{mvar|a}}.  Pseudoprime pertama ke basis 2 ditemukan pada tahun 1820 oleh [[Pierre Frédéric Sarrus]]: 341 = 11&nbsp;×&nbsp;31.<ref>{{Cite OEIS|A128311|Remainder upon division of 2<sup>''n''−1</sup>−1 by ''n''.}}</ref><ref>{{cite journal |first=Frédéric |last=Sarrus |author-link=Pierre Frédéric Sarrus |title=Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil |trans-title=Demonstration of the falsity of the theorem stated on page 320 of the 9th volume of this collection |journal=Annales de Mathématiques Pures et Appliquées |volume=10 |date=1819–1820 |pages=184–187 |language=fr |url=http://www.numdam.org/item?id=AMPA_1819-1820__10__184_0}}</ref>
+Bilangan {{mvar|p}} yang merupakan pseudoprime Fermat ke basis {{mvar|a}} untuk setiap bilangan {{mvar|a}} yang koprima dengan {{mvar|p}} disebut [[bilangan Carmichael]] (misalnya 561). Bergantian, bilangan {{mvar|p}} 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:<ref>{{Cite book|contribution=4.5.1. Lemma (Roots of unity modulo a prime)|contribution-url=https://books.google.com/books?id=nQVZAgAAQBAJ&q=The+Miller%E2%80%93Rabin+primality+test+uses+the+following+extension+of+Fermat's+little+theorem&pg=PA144|title=Primality Testing for Beginners|title-link=Primality Testing for Beginners|last1=Rempe-Gillen|first1=Lasse|last2=Waldecker|first2=Rebecca|author2-link= Rebecca Waldecker |date=2013-12-11|publisher=American Mathematical Soc.|isbn=9780821898833|language=en}}</ref>
+<blockquote>Jika {{mvar|p}} adalah bilangan prima ganjil, dan {{math|1=''p'' – 1 = 2<sup>''s''</sup>  ''d''}}, dengan {{mvar|d}} ganjil, lalu untuk setiap {{mvar|a}} prima hingga {{mvar|p}}, yaitu {{math|''a''<sup>''d''</sup> ≡ 1 mod ''p''}}, atau {{mvar|t}} sehingga {{math|0 ≤ ''t'' < s}} dan {{math|''a''<sup>2<sup>''t''</sup>''d''</sup> ≡ −1 mod ''p''}}</blockquote>
+Hasil ini dapat disimpulkan dari teorema kecil Fermat dengan fakta bahwa, jika {{mvar | p}} adalah bilangan prima ganjil, maka bilangan bulat modulo {{mvar | p}} membentuk [[medan berhingga]], di mana {{math | 1}} adalah 1 dengan -1.
+Uji Miller–Rabin menggunakan properti ini dengan cara berikut:{math|1=''p'' =  2<sup>''s''</sup>  ''d'' + 1}}, dengan {{mvar|d}} ganjil, bilangan bulat ganjil yang primalitasnya harus diuji, pilih secara acak {{mvar|a}} sehingga {{math|1 < ''a'' < ''p''}}; maka {{math|1= ''b'' = ''a''<sup>''d''</sup> mod ''p''}}; jika {{mvar|b}} bukan 1 atau −1, maka kuadratkan berulang kali modulo {{mvar|p}} sampai Anda mendapatkan 1, −1, atau telah mengkuadratkan {{mvar|s}} kali. Jika {{math|''b'' ≠ 1}} dan −1 belum diperoleh, maka {{mvar | p}} bukan bilangan prima. Jika tidak, {{mvar | p}} mungkin bilangan prima atau tidak. Jika {{mvar | p}} bukan bilangan prima, probabilitas hal ini dibuktikan dengan pengujian lebih tinggi dari 1/4. Oleh karena itu, setelah {{mvar | k}} uji acak non-konklusif, probabilitas bahwa {{mvar | p}} bukan bilangan prima lebih rendah dari {{math|(3/4)<sup>''k''</sup>}}, dan karenanya dapat dibuat serendah yang diinginkan, dengan meningkatkan {{mvar | k}}.
+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 ==
+{{Div col}}
+* [[Hasil bagi Fermat]]
+* [[Endomorfisme Frobenius]]
+* [[turunan-P | Turunan-{{mvar | p}}]]
+* [[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]]
+{{Div col end}}
+== Catatan ==
+{{reflist|2}}
+== Referensi ==
+* {{Citation | last1=Albert | first1=A. Adrian | author-link=Abraham Adrian Albert | title=Modern higher algebra | url={{Google books|iVwZCgAAQBAJ|Modern higher algebra|page=206|plainurl=yes}} | publisher=[[Cambridge University Press]] | isbn=978-1-107-54462-8 | year=2015 |orig-year=1938 }}
+* {{citation|first=David M.|last=Burton|title=The History of Mathematics / An Introduction|edition=7th|publisher=McGraw-Hill|year=2011|isbn=978-0-07-338315-6}}
+* {{citation |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |edition=2nd |publisher=[[D. C. Heath and Company]] |location=Lexington |lccn=77171950}}
+* {{citation|last=Mahoney|first=Michael Sean|title=The Mathematical Career of Pierre de Fermat, 1601–1665|year=1994|edition=2nd|publisher=Princeton University Press|isbn=978-0-691-03666-3}}
+* {{citation|first=Oystein|last=Ore|title=Number Theory and Its History|year=1988|orig-year=1948|publisher=Dover|isbn=978-0-486-65620-5|url-access=registration|url=https://archive.org/details/numbertheoryitsh0000orey}}
+* {{citation |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |publisher=[[Prentice Hall]] |location=Englewood Cliffs |lccn=71081766}}
+== Bacaan lebih lanjut ==
+* [[Paulo Ribenboim]] (1995). ''The New Book of Prime Number Records'' (3rd ed.). New York: Springer-Verlag. {{ISBN|0-387-94457-5}}.  pp.&nbsp;22–25, 49.
+== Pranala luar ==
+*{{Commons category inline}}
+* {{Britannica|204696|Fermat's theorem}}
+* [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]
+* {{springer|title=Fermat's little theorem|id=p/f038400}}
+* {{MathWorld| urlname=FermatsLittleTheorem| title=Fermat's Little Theorem}}
+* {{MathWorld| urlname=FermatsLittleTheoremConverse| title=Fermat's Little Theorem Converse}}
+{{Portal bar|Matematika}}
+{{DEFAULTSORT:Fermat's Little Theorem}}
+[[Kategori:Aritmetika modular]]
+[[Kategori:Teorema tentang bilangan prima]]