Bukti Teorema Fermat Kecil

Teorema Fermat
Taruhlah p sebuah bilangan prima. Maka x^p=x(mod p) untuk semua bilangan bulat x. Lebih lanjut jika x relatif prima terhadap p maka x^(p-1)=1(mod p).

Sebelumnya kita buktikan lemma berikut :

Lemma 1 :
Taruhlah p bilangan prima. Maka koefisien binomial C(p,k) habis dibagi p untuk semua bilangan bulat k yang memenuhi 0 < k < p.
Bukti :
Koefisien binomial diberikan dengan formula C(p,k)=p!/{(p-k)!k!}
Jika 0 < k < p maka C(p,k) = [p(p-1)!] / [(p-k)!k!] = pm / k! dengan m=(p-1)! / (p-k)!. Sehingga (k!)C(p,k) = pm, maka k! membagi habis pm. Juga karena k! relatif prima terhadap p, ini dikarenakan p prima dan semua bilangan positif lebih dari 1 dan kurang dari p akan relatif prima ternadap q.
{ jika a dan p relatif prima juga b dan p relatif prima maka ab relatif prima terhadap p, karena jika ada g,h,i,j bilangan bulat sehingga ga+hp=1 juga ib+jp=1 maka (ga)(ib)=(1-hp)(1-jp)=1-(h+j)p+hjp^2 ==> (gi)ab + (h+j-hjp)p=1 }
Karena k! membagi habis pm dan k! relatif prima terhadap p maka haruslah k! membagi habis m. Sehingga koefisien binomial C(p,k) merupakan kelipatan p. Terbukti.

Bukti Teorema Fermat :
Taruhlah p prima maka (x+1)^p=Sigma(dari k=0 ke p) C(p,k)x^k
Menurut lemma di atas maka (x+1)^p=(x^p+1)(mod p). Sehingga jika f(x)=x^p-x maka
f(x+1)(mod p)=(x^p+1)(mod p) - (x+1)(mod p)
f(x)(mod p)=(x^p)(mod p) - x(mod p)
___________________________________________ -
f(x+1)(mod p) - f(x)(mod p) = 1(mod p) - 1(mod p) = 0(mod p)
==> f(x+1)=f(x)(mod p)

Jadi f(x+1)=f(x)(mod p) untuk semua bilangan bulat x.
Karena f(0)=0^p-0=0(mod p) maka
f(1)=f(0+1)=f(0)(mod d)=0(mod p),
f(2)=f(1+1)=f(1)(mod p)=0(mod p),
f(3)=f(2+1)=f(2)(mod p)=0(mod p),
dst dengan induksi... jadi untuk semua x positif f(x)=0(mod p).

Kita bergerak pada bilangan bulat, jadi karena f(x+1)=f(x)(mod p) maka f(x)=f(x+1)(mod p), lalu
f(0)=f(-1+1)(mod p)=f(-1) dan f(0)=0(mod p) ==> f(-1)=0(mod p),
f(-1)=f(-2+1)(mod p)=f(-2)(mod p) dan f(-1)=0(mod p) ==> f(-2)=0(mod p),
f(-2)=f(-3+1)(mod p)=f(-3)(mod p) dan f(-2)=0(mod p) ==> f(-3)=0(mod p),
dst dengan induksi... jadi untuk semua x negatif f(x)=0(mod p).

Jadi untuk semua bilangan bulat f(x)=0(mod p).
Berarti x^p-x=0(mod p) ==> x^p=x(mod p), Untuk mana x relatif prima terhadap p, maka kita bisa
melakukan kanselasi (x^p)/x=1(mod p) ==> (x^(p-1))=1(mod p). Terbukti.