teori fermat
PEMBAHASAN A. Teorema Fermat Menguji keprimaan suatu bilangan bulat n dengan cara membaginya dengan sejumlah bilangan prima yang tentu kurang efektif untuk n yang besar, karena kita harus menentukan terlebih dahulu semua bilangan prima yang lebih kecil dari . Terdapat metode lain yang dapat digunakan untuk menguji keprimaan suatu bilangan bulat yang dikenal dengan nama teorema Fermat (biasanya disebut dengan Fermat’s little theorem ). Sebelum teorema Fermat dijelaskan, teorema berikut perlu diperhatikan. Teorema 1 Jika (a,m)=1 maka sisaan terkecil suatu mod m barisan: a, 2a, 3a,..., (m-1)a adalah suatu permutasi dari 1,2,3,...,(m-1) Dengan perkataan lain, berdasarkan teorema 1 dapat dikatakan bahwa jika (a,m)=1 maka tiap bilangan bulat kongruen modulo m dengan tepat satu dari 0, a, 2a,..., (m-1)a. Perlu diingat bahwa himpunan tiap bilangan bulat akan kongruen modulo m dengan tepat satu dari 0,1,2,3,..., (m-1). Bukti: · Pe