Jelaskan Bukti dari Teorema kecil Fermat

Beberapa bukti teorema kecil Fermat diketahui. Ini sering dibuktikan hasil sampingan/langsung (corollary) dari Teorema Euler.

Teorema Euler adalah generalisasi dari teorema kecil Fermat: untuk modulus  dan bilangan bulat apa pun  koprima hingga , adalah

dimana  menunjukkan Fungsi total Euler (yang menghitung bilangan bulat dari 1 hingga  yang koprima hingga ). Teorema kecil Fermat kasus khusus, karena jika  adalah bilangan prima, maka .

Teorema Euler adalah: untuk setiap bilangan bulat positif , jika bilangan bulat  adalah koprime dengan  maka

untuk bilangan bulat  dan .

Ini mengikuti dari teorema Euler, karena, jika , sehingga  untuk beberapa bilangan bulat , dan satu memiliki

Jika  adalah bilangan prima, ini juga merupakan akibat wajar dari teorema kecil Fermat. Ini banyak digunakan dalam aritmetika modular, karena ini memungkinkan pengurangan eksponen modular dengan eksponen besar menjadi eksponen yang lebih kecil dari .

Jika  bukan bilangan prima, ini digunakan di kriptografi kunci publik, biasanya di kriptografi RSA dengan cara berikut: jika

dari nilai  dan  jika  Faktanya, algoritme Euklides memungkinkan komputasi modular invers dari  modulo  itu adalah bilangan bulat  maka

Di sisi lain, jika  adalah hasil kali dari dua bilangan prima yang berbeda, maka  Dalam kasus ini, menemukan  dari  dan  diketahui  (ini tidak terbukti, tetapi tidak ada algoritme yang diketahui untuk menghitung  tanpa mengetahui ). Jika  dan  faktor  dan  mudah untuk disimpulkan, karena seseorang mengetahui hasil kali  dan jumlahnya  Ide dasar dari kriptosistem RSA adalah: jika pesan  dienkripsi sebagai  menggunakan nilai publik dari  dan , kemudian, dengan pengetahuan saat ini, ia tidak dapat didekripsi tanpa menemukan faktor (rahasia)  dan  dari .

Teorema kecil Fermat juga terkait dengan Fungsi Carmichael dan Teorema Carmichael, serta Teorema Lagrange dalam teori grup.