Totien Euler pertama

Pola-pola seputar bilangan prima

Tabel-tabel perkalian kelas-kelas kongruensi modulo p.

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.

Teori Bilangan (Bukti-bukti) 2

Lemma 2 :
Taruhlah m bilangan bulat positif, dan x bilangan bulat yang relatif prima terhadap m, serta i dan j bilangan bilangan-bilangan bulat positif. Maka (x^i)=(x^j)(mod m) jika dan hanya jika i=j(mod d) dimana d adalah order kelas kongruensi modulo m terhadap x.

Bukti :
Kita akan membuktikan biimplikasi (x^i)=(x^j)(mod m) <==> i=j(mod d)
Kita bisa memilih i
Pertama kita buktikan i=j(mod d) ==> (x^i)=(x^j)(mod m) :
Jika i=j(mod d) maka d | (j-i) ata ada bilangan bulat b sehingga (j-i)=bd, sehingga karena x^d=1(mod m) [ingat bahwa d adalah order kelas kongruensi modulo m terhadap x] dan misalkan x^d=km+1. Kemudian (x^(j-i))=x^(bd)=(x^d)^b=(km+1)^b=Lm+1=1(mod m) untuk suatu L bilangan bulat. Sehingga x^j=(x^i)(x^(j-i))=(x^i)(1(mod m)) ==> (x^j)=(x^i)(mod m).

Kedua kita buktikan (x^i)=(x^j)(mod m) atau (x^j)=(x^i)(mod m) ==> i=j(mod d) :
Kita telah memilih i < j, maka (x^i)(x^(j-i))=(x^i)(mod m) dan karena x relatif prima terhadap m, sehingga x^i relatif prima terhadap m, ini menjadikan x^(j-i)=1(mod m). Sehingga jika d order kelas kongruensi modulo m terhadap x maka x^d=1(mod m). Kemudian misalkan j-i=kd+r dengan 0 =< r< d maka x^(j-i) = x^(kd+r) = ((x^d)^k)(x^r) = 1(mod m) ==> (x^r)=1(mod m).
Ehh tapi d adalah order dari kelas modulo m terhadap x jadi harusnya d yang terkecil sehingga (x^d)=1(mod m), kalau ternyata (x^r)=1(mod m) dengan 0 =< r< d maka harusnya r=0 dan terbukti bahwa
d|(j-i) atau j=i(mod d). Terbukti.

Teori Bilangan (bukti-bukti) 1

Lemma 1 :Taruhlah m bilangan bulat positif, dan x adalah bilangan bulat yang relatif prima terhadap m. Maka ada bilangan bulat positif n sedemikian hingga x^n=1(mod m).

Bukti :Kelas-kelas kongruensi modulo m banyaknya berhingga, yaitu sebanyak m :
{0(mod m)}, {1(mod m)}, {2(mod m)},. . ., {m-1(mod m)}
Setiap bilangan bulat pasti menjadi anggota dari salah satu kelas-kelas kongruensi tersebut.
Maka kita bisa memilih i dan j sehingga x^i=x^j(mod m) dengan i < j. Mungkin ini agak membingungkan mengapa bisa demikian, kita lihat lagi bahwa kelas-kelas kongruensi tersebut bisa dituliskan dengan :{km}, {km+1}, {km+2},..., {km+m-1}
Misalkan x^i anggota {km+q} dengan 0= < q < m, maka pada langkah-langkah berikutnya tentu terdapat x^j anggota {km+q}.Sebagai contoh, 8^3=512=2(mod 17), lalu 8^11=8589934592=2(mod 17), sehingga 8^3=8^11(mod 17).
Untuk generalnya, sebagai berikut :
Asumsikan tidak ada j>i sehingga x^i=x^j(mod m) berarti misalkan x^i=q(mod m) dengan 0= < q < m,>i berlaku x^j <> q(mod m), taruhlah x^i=km+q untuk suatu bilangan bulat positif k, maka (x^i)^2=(km)^2+2kmq+q^2=(mk^2+2kq)m+q^2=q^2(mod m) dan dapat ditunjukkan dengan binomial newton bahwa (x^i)^m=q^m(mod m).
Kita perhatikan bahwa menurut teorema Fermat Kecil maka q^m=q(mod m) atau dengan kata lain m membagi habis (q^m-q). Jadi q^m = (q^m-q) + q = q(mod m). Sehingga asumsi kita gagal karena dengan mengambil j=im, maka x^j=x^(im)=(x^i)^m=q^m(mod m)=q(mod m).

Karena itu Kita bisa menaruh x^j=x^i(mod m) atau x^i=x^j(mod m)
Taruhlah n=j-i maka (x^i)(x^n)=(x^i)(mod m) Karena x relatif prima terhadap m, maka ada a dan b sehingga ax + bm = 1 ==> ax=1-bm ==> (ax)^i=(1-bm)^i==> (a^i)(x^i) = 1 + Hm untuk suatu bilangan bulat H ==> (a^i)(x^i) - Hm = 1
Sampai disini kombinasi linear ini memberikan arti bahwa x^i dan m relatif prima. Akhirnya kita bisa melakukan kanselasi yang menjadikan (x^n)=1(mod m). Terbukti.