Euler-Fermat teoreminin bir uygulaması

Daha önce bu blogda bölünebilme kurallarından bahsederken Fermat'nın küçük teoremine de değinmiştik. Euler, bu teoremi genelleştirmiş ve daha kullanışlı şu forma getirmiştir.

Euler-Fermat teoremi: obeb$(a,n)=1$ ise, o zaman $a^{\phi(n)}\equiv 1({\rm mod}\ n)$.

Burada Euler fonksiyonu $\phi(n)$ şöyle tanımlanıyor: $1 \leq m \leq n$ olmak üzere, obeb$(m,n)=1$ olan $m$ sayılarının adedi $\phi(n)$ değerini verir. Teoremin bizzat kendisi çok şaşırtıcı zaten ama daha şaşırtıcı olan Euler fonksiyonu için kapalı bir formülümüzün olması. $n=p_{1}^{a_{1}} \cdots p_{k}^{a_{k}}$ biçiminde asal çarpanlarına ayrılıyorsa, o zaman

$$\begin{equation} \phi(n) = n \left( 1 - \frac{1}{p_{1}} \right) \cdots \left( 1 - \frac{1}{p_{k}} \right) \end{equation}$$ formülüyle kolayca hesaplanıyor. Ne Euler-Fermat teoremini ne de yukarıdaki denklemi ispatlayacağım. Bunlara sayılar teorisi üzerine yazılmış standart metinlerden ulaşabilirsiniz. Bugün son zamanlarda sayfaları arasında gezindiğim temel seviyede yazılmış bir sayılar teorisi kitabında gördüğüm bir soruya yaptığım çözümü paylaşacağım.

Problem: $7^{9999}$ sayısının son üç hanesini bulunuz.

Son üç hane demek, sayının 1000 ile bölümünden kalan demektir. Aslında soruyu hazırlayanlar bizden $7^{9999}\equiv x ({\rm mod} \ 1000)$ değerini hesaplamamızı istiyorlar. Bölünebilme kuralları için yaptığımız çalışmada anahtar basamak $10^{k} \equiv \pm 1({\rm mod} \ n)$ değerini veren bir $k$ kuvvetini bulmaktı. Böyle bir kuvveti bulana kadar ya da periyodik bir davranış yakalayana kadar $10^{k}({\rm mod} \ n)$ hesaplamıştık. Burada obeb$(7,1000)=1$ olduğundan Euler-Fermat teoremi $7^{\phi(1000)}\equiv 1({\rm mod} \ 1000)$ olacağını garanti ediyor. Ama $1000=10^{3}=2^{3}5^{3}$ olduğundan

$$\begin{equation} \phi(1000) = 1000 \left( 1 - \frac{1}{2} \right)\left( 1 - \frac{1}{5} \right) = 400 \end{equation}$$ olduğu kolayca hesaplanabilir. Demek ki $7^{400}\equiv 1({\rm mod \ 1000})$ imiş.

Şimdi 9999'a en yakın 400'ün katı 10000'dir. O zaman $1 \equiv 7^{10000} \equiv 7 \cdot 7^{9999} \equiv 7x({\rm mod} \ 1000)$ olduğunu gözleyebiliriz. Dolayısıyla çözmemiz gerekli denklem aşağıdaki gibidir.

$$\begin{equation} 7x \equiv 1({\rm mod} \ 1000) \label{k1} \end{equation}$$ Lineer kongruens denklemlerinde yapılan en yaygın hilelerden birisi ($\ref{k1}$) nolu denklemi her $x$ değeri için doğru olan aşağıdaki denklemle beraber düşünmektir. $$\begin{equation} 1000x \equiv 0 ({\rm mod} \ 1000) \label{k2} \end{equation}$$ 7'nin 1000'e en yakın katı 994'tür: $7 \times 142 = 994$. O zaman ($\ref{k1}$) nolu denklemi 142 ile çarpıp ($\ref{k2}$) nolu denklemden çıkartalım. $$\begin{equation} 6x \equiv -142 ({\rm mod}\ 1000) \label{k3} \end{equation}$$ Çilemiz bitmedi. ($\ref{k3}$) nolu denklemi bir kere daha ($\ref{k1}$) nolu denklemden çıkartırsak, o zaman $$\begin{equation} x \equiv 143({\rm mod}\ 1000) \end{equation}$$ sonucuna ulaşır ve çözümü bitiririz.

Sayılar teorisinde tamsayılar, cebirde ise polinomlar adına halka (ring) denilen bir yapı oluştururlar. Halka yapısında taraf tarafa toplama, çıkartma ve çarpma yapılabilir ama bölme sorunludur. (Bu yüzden $7x \equiv 1({\rm mod}\ 1000)$ denklemini çözerken kırk takla atmamız gerekti.)