Teorema Fermat

Teorema Fermat memegang peranan penting dalam kriptografi kunci publik (Public Key). Adapun bunyi teorema Fermat adalah sebagai berikut :

Jika p adalah bilangan prima dan a adalah bilangan bulat positif yang tidak dapat dibagi oleh p  maka berlaku a^(p-1)≡1(mod p)

Pembuktian teorema Fermat adalah sebagai berikut:

Tentukan himpunan bilangan bulat positif yang lebih kecil dari p yaitu:

p:{1,2,3,…,p-1} dan kalikan masing-masing elemen tersebut dengan a, modulo p untuk mendapatkan himpunan bilangan X∶ {a mod p,2a mod p,3a mod p,…,(p-1)a mod p} maka tidak ada satupun elemen dari himpunan X yang sama dengan 0. Bahkan tidak ada diantara bilangan tersebut sama. Untuk membuktikannya asumsikan bahwa ja ≡ka(mod p) , dimana 1≤j<k≤p-1. Karena a relatif prima dengan p, kita dapat menghilangkan a dari kedua sisi persamaan tersebut sehingga  menghasilkan j ≡k(mod p). Persamaan ini tidak mungkin karena kita tahu bahwa j dan k adalah bilangan bulat positif. Oleh sebab itu kita tahu bahwa semua elemen (p-1) dari X adalah bilangan bulat positif yang semua elemennya tidak ada yang sama. Kita dapat menyimpulkan bahwa X terdiri dari himpunan bilangan bulat {1, 2, …, p-1} dengan urutan yang berbeda. Mengalikan bilangan-bilangan dalam himpunan p dan X dan di-modulo p akan menghasilkan:

a x 2a x…x (p-1)a≡[(1 x 2 x…x (p-1))](mod p)

a^(p-1) (p-1)! ≡(p-1)!(mod p)

Kita dapat menghilangkan (p-1) karena relatif prima dengan p maka akan menghasilkan 

persamaan sebagai berikut : a^(p-1)≡1(mod p). (Terbukti)

Bentuk lain dari teorema Fermat yang juga sangat berguna adalah :

a^p≡a(mod p)