$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 $7$nin 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)