Loading [MathJax]/jax/element/mml/optable/MathOperators.js
Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
1.5k kez görüntülendi

7x49(mod997) saglayan x degerini varsa bulunuz.


997 asal oldugundan ve 997 oldugundan, Fermat'in Kucuk Teoremi sunu soyler.


7^{997}\equiv7\;(\mod 997)  veya 7^{996}\equiv1\;(\mod 997). Devaminda birsey getiremedim.


Bu arada cevap x=500 dur.


Lisans Matematik kategorisinde (2.9k puan) tarafından  | 1.5k kez görüntülendi

7^{ 996} \equiv 1. Yani 7^{498} \equiv \pm1. Bu da bir başlangıç olabilir. 

Bir de quadratic reciprocity kullanınca iş çözülür. 

Neden 7^{ 996} \equiv 1\implies7^{ 498} \equiv \pm1, boyle bir kural mi var?

(7^{498})^2\equiv1 ve \mathbb{Z}_{997} bir cisim (x^2-1 in kökleri \pm1) olduğundan 7^{498}\equiv\pm1 olmak zorundadır.

Anladim ama notasyon kafa karistiriyor. 7^{ 498} \equiv 1 veya 7^{ 498} \equiv -1 olmali, aksi halde her ikisi de saglanir gibi algiladim..

İkisi aynı anda sadece mod2de denk olabilir. Standart bir kullanım. Mesela ikinci dereden polinomların kökleri için \frac{-b\pm\sqrt\Delta}{2a} yazmak gibi...

1 cevap

1 beğenilme 0 beğenilmeme
En İyi Cevap

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)

(25.6k puan) tarafından 
tarafından seçilmiş

Quadratic reciprocity'nin kaç tane kanıtını biliyorsun?

Neden mod 3? Ledengre gosterimlerine bakmam lazim.

@Ozgur, birkac, cok degil ama. 

@Okkes, `Bu aslinda sayilari kucultmek icin kullaniliyor.'  dedigim paragrafin oncesi ve sonrasinda birkac kere aciklamis oluyorum aslinda. 

247ye bi Ozgur&Sercan mi eklesek :)

Bu arada link icin tesekkurler. 

20,312 soru
21,868 cevap
73,589 yorum
2,859,617 kullanıcı