Rabu, 19 Oktober 2011

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.
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
___________
___________
___________ .

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

Tidak ada komentar:

Posting Komentar