Modüler Aritmetik

Question

$2017^{2001}$ sayısının sondan üç basamağı nedir?

Bu sayının $mod1000$'e göre değerini bulacağımı farkettim.

Daha sonra $17^{2001}=x(mod1000)$ eşitliğine geldim.

Sonra $17$'nin kuvvetlerini yazmaya başladım, çok büyük çıkınca hesap makinesine baktım ,15-20 değer sonra kalanlar döngüye giriyor.

Kullanabileceğim pratik bir yol yok mudur acaba?

Answer 1

Bu sorunun belki daha kısa sayılabilecek çözümü için aşağıdaki bilgilerin bilinmesinde fayda var.

$1\leq i\leq k$  için  $p_i$ ' ler asal sayı ve , $r_i$ sayıları doğal sayılar olmak üzere; $n>1$ sayısının asal çarpanlara ayrılmış biçimi ;  $n=p_1^{r_1}.p_2^{r_2}.p_3^{r_3}...p_k^{r_k}$ olsun.

$\varphi(n)=(p_1^{r_1}-p_1^{r_1-1})(p_2^{r_2}-p_2^{r_2-1})(p_3^{r_3}-p_3^{r_3-1})...(p_k^{r_k}-p_k^{r_k-1})$ şeklinde tanımlanan fonksiyona Euler Fonksiyonu denir. $\varphi(n)$ sayısı; $n$ den küçük olan ve $n$ ile aralarında asal olan doğal sayıların sayısıdır. Euler fonksiyonunun tanımından $\varphi(1)=1$   olduğu ve $p$  asal bir sayı ise $\varphi(p)=p-1$ olduğu açıktır.

Euler Teoremi: $OBEB(a,n)=1$ ise $a^{\varphi(n)}=1(modn)$ dir.  

 Yukarıdaki bilgiler ışığında soruyu çözmeye çalışalım.

$2017^{2001}=17^{2001}\equiv x(mod1000)$ olup,

$OBEB(17,1000)=1$ ve $\varphi(1000)=\varphi(2^3.5^3)=(2^3-2^2)(5^3-5^2)=400$ olduğu için;  $17^{400}=1(mod1000)\Rightarrow 17^{2000}=1(mod1000)\Rightarrow 17^{2001}=17(mod1000)$ olacaktır. 

Comments

Teşekkür ederim Mehmet hocam.

Öğrenmesi biraz ayrıntı (mı acaba, bilmiyorum) gibi gözükse de öğrenince çoğu mod sorusunda kullanılabilecek bir teknikmiş.

---

Bence hiç ayrıntı değil. Büyük kolaylık. Ayrıca $p$ asal olmak üzere $EBOB(a,p)=1$   olmak üzere $a^{p-1}=1(modp)$ şeklindeki Fermat teoremi de  zaten bunun bir sonucudur. Modüler aritmetik sorularının çözümü için bu teoremleri bilmende fayda var.

---

Evet hocam.Fermat teoreminin de nereden gelmiş olduğunu gördüm (sürekli kullanıyordum zaten,iyi oldu)

Öyle sorular var ki sadece bu kurallar üzerine kurulmuş,bilinmeden hiçbir türlü yapılamıyor.Kurallar üzerine çalışmak sizin de dediğiniz gibi çok fayda getirecektir.Cevabınız için teşekkür ederim.

---

Evet. Ben de zaten onları düşünerek bu teoremleri bilmenin sana çok yardımcı olacağını söylemek istedim. Önemli değil. Kolaylıklar ve iyi çalışmalar dilerim.