BERBAGI ITU INDAH ...: TENTANG 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.