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.