Dalam teori bilangan, Fermat menyumbang penemuan yang penting, termasuk Fermat's Little Theorem.
Fermat's Little Theorem
Jika adalah bilangan prima dan adalah integer positif dimana ,maka
Fermat menyertakan pernyataan ini dalam sebuah surat kepada seorang koresponden matematika, Frenicle de Bessy, tahun 1640. Dia tidak menyertakan buktinya karena menurutnya buktinya terlalu panjang. Akhirnya setelah berpuluh-puluh tahun kemudian, bukti teorema ini masih menjadi misteri. Tahun 1736, Leonhard Euler berhasil membuktikan dan mempubliksikan bukti teorema ini.
=======================================================================
Untuk menjelaskan ide di balik bukti ini, sebaiknya kita gunakan contoh sederhana.
Contoh 1:
Asumsikan dan , maka
Dengan demikian:
Note: Lihat hukum pembagian modulo di kedua ruas.
Contoh 2:
Asumsikan dan , maka
Dengan demikian:
Dari contoh di atas, seharusnya kita sudah punya gambaran bagaimana membuktikan teorema ini.Contoh 1:
Asumsikan dan , maka
Note: Lihat hukum pembagian modulo di kedua ruas.
Contoh 2:
Asumsikan dan , maka
Asumsikan adalah bilangan prima.
Asumsikan adalah integer positif dimana
Asumsikan terdapat barisan berikut:
Perhatikan bahwa tak ada satu pun suatu bilangan dari barisan di atas yang habis dibagi . Alasannya sederhana. Barisan tersebut terbentuk dengan pola dimana . Oleh karena dan , maka . |
Kemudian, dari barisan itu tidak ada dua bilangan yang kongruen modulo . Atau dengan kata lain, jika bilangan-bilangan tersebut dibagi dengan , maka sisa pembagiannya akan selalu berbeda satu sama lain. Pembuktiannya juga sederhana. Asumsikan bahwa ada dua bilangan yang kongruen modulo , yaitu dan dimana |
Dari kedua argumen di atas, maka:
TERBUKTI. ■
=======================================================================
Fermat's Little Theorem
Jika adalah bilangan prima dan adalah integer positif, maka
Note: perhatikan bahwa bukanlah syarat wajib.
Kita pisah menjadi 2 bagian:
Bagian 1:
Jika , maka teorema Fermat bentuk sebelumnya berlaku:
Jika , maka . Dengan demikian, teorema di atas terbukti benar.
Jadi, bentuk lain dari Fermat's Last Theorem pun terbukti. ■
=======================================================================
Teorema binomial:
Perhatikan bahwa hanya suku pertama dan suku terakhir saja yang TIDAK habis dibagi oleh
Oleh karena itu:
Oleh karena itu:
Note: HARUS bilangan prima.
(i) Jika , maka terbukti benar untuk semua .
(ii) Asumsikan bahwa untuk suatu , pernyataan adalah BENAR.
Dengan demikian, kita akan cek untuk . Dari teorema binomial, kita dapatkan:
Dengan demikian, Fermat's Little Theorem TERBUKTI secara induksi matematika. ■
=======================================================================
Jawab:
73 adalah bilangan prima, maka dari Fermat's Little Theorem kita tahu bahwa .
Maka, kita kelompokkan berdasarkan 72.
.
Selanjutnya, kita gunakan cara biasa.
_________
_________
_________
_________ .
Jadi, sisa pembagiannya adalah 32.
Contoh Soal 2:
Tentukan invers dari 6 modulo 11.
Jawab:
dikatakan invers dari modulo apabila memenuhi .
Kita dapat menggunakan banyak cara.
Pertama: coba-coba, mulai dari 1,2,3,...,11.
1x6 6 mod 11
2 x 6 =12 1 mod 11.
Note: karena modulo bilangan prima selalu mempunyai invers yang unik modulo p(Lihat di SINI), maka kita sudah mendapatkan jawabannya, yaitu 2.
Cara kedua: dengan algoritma Euclid sampai tahap Bezout identity.
6 = 5 + 1
Jadi, 1 = 6-5 = 6-(11-6) = 2.6 - 11
Bezout Identity-nya:
6.2 - 11 = 1
Jadi, invers modulo-nya adalah 2.Cara ketiga: Dengan Fermat Little Theorem (berlaku karena 11 adalah bilangan prima).
Fermat's Little Theorem dapat dimodifikasi menjadi
Jadi, invers dari adalah
___________
___________
___________ .
Cara Lainnya tentunya masih ada, misalnya dengan euler-phi function. Lihat di post berikutnya..
=======================================================================
Fermat's Little Theorem juga memiliki bukti-bukti lain, misalnya dengan menghitung bracelet, system dinamis, dan sebagainya. Namun, karena saya sangat malas keterbatasan tempat di post ini. Jadi, sebaiknya kalian lihat sendiri di sumbernya langsung, yaitu di "tante" wikipedia. :P
Sesungguhnya masih banyak yang harus dibahas dari Fermat's Little Theorem. Leonhard Euler mengembangkan teorema Fermat yang digeneralisasi. (Lihat Teorema Euler).Kemudian, adapula algoritma Pollard's p-1 yang didasarkan pada Fermat' Little Theorem ini. Kegunaannya pun banyak, misalnya untuk tes keprimaan (menentukan suatu bilangan prima atau tidak), dan sebagainya.
Tujuan post ini hanya untuk mengenalkan Fermat's Little Theorem. Selanjutnya, untuk pengembangan akan dibahas lebih lanjut di post-post berikutnya. Semoga post ini berguna dan saya harap post ini dapat kalian mengerti. Saya tahu ini memang bahan yang berat, karena harus mengikuti bahan-bahan sebelumnya, yaitu divisibility, modulo, dan Bezout Identity. Namun, akan sangat mudah jika kalian sudah tahu dasarnya. :)
Sesungguhnya masih banyak yang harus dibahas dari Fermat's Little Theorem. Leonhard Euler mengembangkan teorema Fermat yang digeneralisasi. (Lihat Teorema Euler).Kemudian, adapula algoritma Pollard's p-1 yang didasarkan pada Fermat' Little Theorem ini. Kegunaannya pun banyak, misalnya untuk tes keprimaan (menentukan suatu bilangan prima atau tidak), dan sebagainya.
Tujuan post ini hanya untuk mengenalkan Fermat's Little Theorem. Selanjutnya, untuk pengembangan akan dibahas lebih lanjut di post-post berikutnya. Semoga post ini berguna dan saya harap post ini dapat kalian mengerti. Saya tahu ini memang bahan yang berat, karena harus mengikuti bahan-bahan sebelumnya, yaitu divisibility, modulo, dan Bezout Identity. Namun, akan sangat mudah jika kalian sudah tahu dasarnya. :)
Sumber:
http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem
Buku Elementary Number Theory oleh Kenneth H Rosen.
http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem
Buku Elementary Number Theory oleh Kenneth H Rosen.
huaaaaa gamsahamnida,,,,
ReplyDeletejadi ngerti deh
please posting tentang algoritma Pollard's p-1 juga dong...>w<
Contoh soal 1. Jawabannya salah ya gan😊. Silahkan di cek langkahnya.
ReplyDeleteyang mana ya?
Deleteharusnya sisanya 4 ya?
ReplyDeleteBukannya 2 ya?
Delete