Menurut Little Fermat Theorem jika p bilangan prima maka untuk setiap bilangan bulat a berlaku a^p=a(mod p). Khususnya jika p tidak membagi habis a atau katakan p dan a relatif prima maka  a^(p-1)=1(mod p).
Teorema ini termasuk mudah pembuktiannya asal memahami binomial newton dan induksi matematik.
Okay kita tuliskan yang lebih terang, p prima ==> a^p=a(mod p)
Di sini konversnya (a^p=a(mod p) ==> p prima ) tidak berlaku artinya kalau p dan a memenuhi a^p=a(mod p) belum tentu p prima.
Bilangan p yang memenuhi a^p=a(mod p) biasa disebut dengan aPRP (probable prime base a), kemudian kalau ternyata bilangan p itu komposit maka disebut pseudoprime.
Contohnya :
5 termasuk 2-PRP karena 2^5=32=2(mod 5) karena 32=6x5+2
7 termasuk 2-PRP karena 2^7=128=2(mod 7) karena 128=18x7+2
9 bukan termasuk 2-PRP karena 2^9=512=56x9+8 tidak sama dengan 2(mod 9) jadi tidak termasuk 2-PRP
dst...semua bilangan prima akan memenuhinya.
tapi tidak semua yang memenuhi 2-PRP akan merupakan bilangan prima, yaitu contohnya
341 termasuk 2-PRP karena
2^341=4479489484355608421114884561136888556243290994469299069799978201927583742360321890761754986543214231552=2(mod 341)
tapi 341=11x31 (komposit)
Jadi 341 ini termasuk pseudoprime. Ada beberapa tapi tak terhingga pseudoprime ini, maksudnya dalam rentang yang lumayan adanya. Berawal dari sinilah primality test yang lebih modern dikembangkan, sampai yang lebih modern lagi adalah dengan teori group terutama teorema lagrange dimana indeks suatu group berhingga merupakan hasil perkalian indeks subgroup dengan indeks quotient groupnya, dalam hal bilangan prima ini groupnya adalah Z bilangan asli dan subgroupnya adalah pZ. Dan sampai terbentur pada hipotesa Riemann. Mulai dari yang sederhana di atas silahkan dilanjutkan pembicaraan yang lebih dalam lagi seperti Strong Probable Prime base a (a-SPRP)

Dilanjut lagi primanya...
Kayaknya belum ada yang berminat, padahal aplikasinya banyak nih..

{0,7,14,21,28,...} = {0(mod 7)}
{1,8,15,22,29,...} = {1(mod 7)}
{2,9,16,23,30,...} = {2(mod 7)}
{3,10,17,24,31,...} = {3(mod 7)}
{4,11,18,25,32,...} = {4(mod 7)}
{5,12,19,26,33,...} = {5(mod 7)}
{6,13,20,27,34,...} = {6(mod 7)}

2^1=2=2(mod 7),2^4=16=2(mod7),2^7=128=2(mod 7),...
2^2=4=4(mod 7),2^5=32=4(mod 7),2^8=256=4(mod 7),...
2^3=8=1(mod 7),2^6=64=1(mod 7),2^9=512=1(mod 7),...
Order kelas kengruensi 7 terhadap 2 adalah 3

3^1=3=3(mod 7),3^7=2187=3(mod 7),...
3^2=9=2(mod 7),3^8=6561=2(mod 7),...
3^3=27=6(mod 7),3^9=19683=6(mod 7),...
3^4=81=4(mod 7),3^10=59049=4(mod 7),...
3^5=243=5(mod 7),3^11=177147=5(mod 7),...
3^6=729=1(mod 7),3^12=531441=1(mod 7),...
Order kelas kengruensi 7 terhadap 3 adalah 6

4^1=4=4(mod 7),4^4=256=4(mod 7),...
4^2=16=2(mod 7),4^5=1024=2(mod 7),...
4^3=64=1(mod 7),4^6=4096=1(mod 7),...
Order kelas kengruensi 7 terhadap 4 adalah 3

5^1=5=5(mod 7),5^7=78125=5(mod 7),...
5^2=25=4(mod 7),5^8=390625=4(mod 7),...
5^3=125=6(mod 7),5^9=1953125=6(mod 7),...
5^4=625=2(mod 7),5^10=9765625=2(mod 7),...
5^5=3125=3(mod 7),5^11=48828125=3(mod 7),...
5^6=15625=1(mod 7),5^12=244140625=1(mod 7),...
Order kelas kengruensi 7 terhadap 5 adalah 6

6^1=6(mod 7),6^3=216=6(mod 7),...
6^2=36=1(mod 7),6^4=1296=1(mod 7),...
Order kelas kengruensi 7 terhadap 6 adalah 2


x=a(mod m) dengan 0<a<m
Ada k bilangan bulat sehingga
x=km+a ==> x^2=(km)^2+2kma+a^2=(mk^2+2ka)m+a^2 ==> x^2=a^2(mod m)
Dengan binomial newton, maka
x^n=Am+a^n=a^n(mod m), untuk suatu bilangan bulat A.
 
sehingga x^i=a^i(mod m) dan x^j=a^j(mod m) dengan 0<a<m.
Kapan terjadi x^i=x^j(mod m) ? Yaitu jika m|(x^j-x^i) atau
m|{x^i)}{x^(j-1)-1} dan karena x^i relatif prima terhadap m (x relatif prima terhadap m maka x^i relatif prima terhadap m), maka m|{x^(j-1)-1} ==> x^(j-i)=1(mod m) atau a^(j-i)=1(mod m)

Ini menghasilkan lemma yang kedua, yaitu :
Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka x^i=x^j(mod m) jika dan hanya jika j=i(mod d) dengan d adalah order kelas kongruensi m terhadap x.

Ulasan mengenai lemma-lemma :

Pertama :
"Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka ada suatu bilangan bulat positif n sehingga x^n=1(mod m)."

Contoh :
m=3, x=5 maka 5^1=5=2(mod 3), 5^2=25=1(mod 3) inilah karena 3 dan 5 relatif prima maka ada n=2 shg 5^2=1(mod 3)
m=5, x=10 maka 10^1=10=0(mod 5),10^2=100=0(mod 5), kita tahu untuk selanjutnya selalu merupakan 0(mod 5) jadi tak ada dong n yang memenuhi 5^n=1(mod 5) inilah karena 5 dan 10 tidak relatif prima.
m=6, x=8 maka 8^1=8=2(mod 6),8^2=64=4(mod 6),8^3=512=2(mod 6),8^4=4096=4(mod 6), dst ini selalu berselang-seling antara 2(mod 6) dan 4(mod6) dan bisa dibuktikan dengan induksi yaitu 8^n-2 habis dibagi 6 jika n ganjil dan 8^n-4 habis dibagi 6 jika n genap. Inilah karena 6 dan 8 tidak relatif prima.

Jika m bilangan prima maka untuk x bilangan asli dibawah m akan selalu relatif prima terhadap m,
contohnya jika m=7, maka 1,2,3,4,5,dan 6 relatif prima terhadap 7.
Jadi untuk m bilangan prima, maka untuk semua x lebih kecil dari m, akan selalu ada n sehingga x^n=1(mod m)

Kedua :
"Jika jika m suatu bilangan bulat positif dan x adalah bilangan bulat yang relatif prima terhadap m maka x^i=x^j(mod m) jika dan hanya jika j=i(mod d) dengan d adalah order kelas kongruensi m terhadap x."

Kita lihat pada contoh kelas-kelas kongruensi modulo 7 di atas, yakni m=7 dan x=5 :
5^6=15625=1(mod 7),5^12=244140625=1(mod 7),...
Order kelas kengruensi 7 terhadap 5 adalah 6
Kalau kita teruskan maka 5^6, 5^12, 5^18, 5^24,... semuanya merupakan 1(mod7). Jadi ambilah 5^6=15625 dan 5^18=3814697265625
dan 5^18-5^6 = 3814697250000 = 544956750000 x 7 sehingga 5^18=5^6(mod 7) dan kita lihat j=18 dan i=6 sehingga j=i(mod 6), di sini 6 merupakan order kelas kongruensi modulo 7 terhadap 6.
Lebih lanjut lemma ini juga menjamin bahwa jika x^i=x^j(mod m) maka x^i dan x^j berada pada kelas yang sama. Karena untuk semua x bilangan bulat positif di bawah m relatif prima terhadap m jika m prima, maka berarti kelas kongruensi modulo 7 - nya berlain-lainan (distinct)

Ketiga :
"Jika p bilangan prima serta x dan y bilangan positif bulat yang keduanya relatif prima dengan p serta jika keduanya mempunyai order yang sama untuk kelas kongruensi modulo p, katakanlah ordernya d, maka ada bilangan bulat k yang relatif prima terhadap d sehingga y=x^k(mod p)."

Kita ganti simbol m menjadi p untuk mulai memastikan bahwa kita bekerja pada bilangan prima. Kita ambil contoh p=7 serta x dan y masing-masing 5^6=15625 dan 5^18=3814697265625 dan keduanya ini kita tahu relatif prima terhadap 7 (bisa dibuktikan dengan induksi bahwa jika x relatif prima terhadap p maka x^n relatif prima terhadap p). Keduanya berorder d=6 atas kelas kongruensi modulo 7. Maka kita lihat 5^18=5^6(mod 7) ==> 5^18=(5^6)^5(mod 7), disini k=5 relatif prima terhadap d=6. Bisa dihitung bahwa 5^30-5^18 = 931322574615478515625-3814697265625 = 931322570800781250000 = 133046081542968750000 x 7.

Sebaiknya juga kutuliskan bukti Little Fermat Theorem berikut :

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 sebagai pendahuluannya :
Lemma :
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.

Ternyata memang belum ada yang begitu berminat atau terlalu susah dipahami yaa, tapi saya rasa orang2 matematika terutama yang master atau yang pernah belajar kriptografi pernah membacanya kalo ada di forum ini.
Disini untuk memahami bukti lemma ketiga dibutuhkan prasyarat lebih terutama pemahaman tentang penyelesaian suku banyak kongruensi modulo n. Saya belum menemukan cara yang mangkus untuk membuatnya jadi jelas. Melangkah dari konkrit ke abstrak memang membutuhkan energi pikiran.

Salam saudara mkukuh, topik ini adalah pada teori bilangan elementer yaitu tentang primitive root, senang bisa berdialog. Saya bukan dosen dari suatu institusi, hanya seorang praktisi komputer berlatar belakang matematika. Karena melihat teori bilangan bermain disini maka saya ublek2.