Ayyıldız2 | 2008 TR Yapısı • 1-99 Orta Emek Destan • Oto Avsız • 10 Temmuz 21:00 HEMEN TIKLA!
Fermat'nın küçük teoremi
asalı ve
nin bölmediği bir
tamsayısı için
denkliğinin doğru olduğunu belirtir.
Her
mesajı için (me)d
m
denkliğinin doğru olduğunu göstermek istiyoruz.
olduğunu biliyoruz. Yani negatif olmayan bir
tamsayısı için
yazabiliriz. Eğer med
m mod p ve med
m mod qolduğunu gösterirsek Çin Kalan Teoreminden med
m mod pq olduğunu ispatlamış oluruz.
med
m mod p olduğunu göstermek için m
0 mod p ve m
0 mod p durumlarına bakalım. İlk durumda med, p 'nin katı olduğundan med
0
m mod p. İkinci durumda da mp-1' in Fermatnın küçük teoreminden dolayı 1e denk olmasını kullanarak ispatı yapabiliriz:
.med
m mod q olduğunu da benzer şekilde gösterip algoritmanın doğruluğunu ispatlamış oluruz.
Her
med
