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.
Tidak ada komentar:
Posting Komentar