p asal bir sayi olsun. Fermat'in kucuk teoremi geregi (a,p)=1 tam sayilari icin a^{p-1}\equiv 1 \mod p saglanir.
p asal oldugundan (Dogan Donmez'in de dedigi gibi) x^2\equiv 1 \mod p cozumleri x\equiv 1 \mod p \ \ \ \text{ ya da } \ \ \ x \equiv -1 \mod p olur. (Bunun basit sayilar teorisinden ispati mevcut).
Bu da (a,p)=1 tam sayilari icin a^{\frac{p-1}{2}}\equiv 1 \mod p \ \ \ \text{ ya da } \ \ \ a^{\frac{p-1}{2}} \equiv -1 \mod p olur.
_______________________________________
Eger a tam sayisi \mod p altinda bir kare ise a^{\frac{p-1}{2}}\equiv 1 \mod p bir kare degilse de a^{\frac{p-1}{2}}\equiv -1 \mod p saglanir. Bu ilgi cekici ve bircok yerde karsimiz cikan bir durum. \mod p altinda bir sayinin tam kare olup olmadigini test etmek uzere algoritmalar vardir. Detayli bilgi icin [1]deki ilgili bolume bakabilirsiniz.
Eger sayi \mod p altinda bir sayinin tam kare olup olmamasini \left(\frac{a}{p}\right) ile belirtip kare ise 1 kare degilse -1 diyecegiz. Kisacasi a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right) \mod p saglanir.
_______________________________________
Bu soru icin kullanacagimiz ve genel konsepte dekullanisli olan bir esitlik var: p ve q tek asallar olmak uzere \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}} esitligi saglanir.
Bu aslinda sayilari kucultmek icin kullaniliyor. \left(\frac{7}{977}\right) yerine \left(\frac{997}{7}\right)=\left(\frac{3}{7}\right) degerine bakmak, hatta (cok gerekmese de) \left(\frac{7}{3}\right)=\left(\frac{1}{3}\right) degerine bakmak daha kolaydir.
Gordugunun gibi 7^{498} \mod 977 denkliginin 1 ya da -1 degerlerinden hangisini alacagini bulmak icin tek tek kuvvet almak ya da iki tabanli kuvvet algoritmalarina benzer bir algoritma kullanmak durumunda degiliz. Bunun yerine su basit soru cevabi veriyor: 1 tam sayisi \mod 3 altinda tam kare mi? Evet 1^2=1 zaten.
Elimide \left(\frac{7}{977}\right)=\left(\frac{977}{7}\right)=\left(\frac{3}{7}\right)=-\left(\frac{7}{3}\right)=-\left(\frac{1}{3}\right)=-1 var. Bu da 7^{498} \equiv -1 \mod 977 oldugunu verir.
_____________________________________
Peki 7nin daha kucuk bir (pozitif) kuvveti \mod 977 altinda -1 olabilir mi?
Ek kaynaklar:
[1] Neal Koblitz, A Course in Number Theory and Cryptography, (web baglantisi)