Fermat's Little Theorem

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.

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 Karena , maka Karena dan harus lebih besar 1 dan harus lebih kecil dari , maka ini mengisyaratkan bahwa = . Pernyataan ini kontradiksi dengan asumsi awal bahwa dan harus berbeda. Jadi, terbukti bahwa dari barisan itu tidak ada dua bilangan yang kongruen modulo .

Dari kedua argumen di atas, maka:

Karena , maka:

TERBUKTI. ■

=======================================================================

Selain bentuk di atas, Fermat's Little Theorem juga mempunyai bentuk lain.

Fermat's Little Theorem

Jika adalah bilangan prima dan adalah integer positif, maka

Note: perhatikan bahwa bukanlah syarat wajib.

Bukti:
Kita pisah menjadi 2 bagian:

Bagian 1:
Jika , maka teorema Fermat bentuk sebelumnya berlaku:

Kalikan dengan di kedua ruas, maka hasilnya:

Bagian 2:
Jika , maka . Dengan demikian, teorema di atas terbukti benar.

Jadi, bentuk lain dari Fermat's Last Theorem pun terbukti. ■

=======================================================================

Bukti secara induksi matematika memanfaatkan konsep teorema binomial.

Teorema binomial:

Perhatikan bahwa hanya suku pertama dan suku terakhir saja yang TIDAK habis dibagi oleh
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:

Dari asumsi sebelumnya, dikatakan bahwa , maka:

Maka, teorema bernilai benar untuk .

Dengan demikian, Fermat's Little Theorem TERBUKTI secara induksi matematika. ■

=======================================================================

Contoh Soal 1:

Tentukan sisa pembagian jika dibagi 73.

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.

11 = 6 + 5
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, adalah invers dari .

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

Sumber:
http://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_little_theorem
Buku Elementary Number Theory oleh Kenneth H Rosen.