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.

aritmatika

Prakata

Salam

Terima kasih telah membaca portal ini.
Betapa pentingnya apa yang namanya matematika, sebuah ilmu yang terus berkembang sesuai dengan problem yang terus berkembang, baik problem sosial maupun problem eksakta.
Yang jelas matematika itu sendiri juga mengembangkan dirinya sendiri untuk memudahkan mengenali pattern dari suatu fenomena.
Berhubung masih baru lahir maka masih dalam pembangunan.

Salam