21 Euler Teoremi
Fermat teoremi yalnızca asal modüllerde işe yarıyordu: \(p\) asalken \(a^{p-1} \equiv 1 \pmod p\) idi. Modül asal olmadığında \(p - 1\) üssünün yerini ne alacak? Cevap, geçen bölümde tanıdığımız \(\phi(n)\) sayısıdır. Bu bölümde Fermat teoremini bütün modüllere genişleteceğiz.
21.1 İndirgenmiş Kalan Sistemleri
Fermat teoremini ispatlarken \(1, 2, \dots, p-1\) sayılarını kullanmıştık; bunlar modülo \(p\) tersi olan bütün sınıfların temsilcileriydi. Genel modülde bu rolü aşağıdaki kavram üstlenir.
Tanım 21.1 (İndirgenmiş Kalan Sistemi) \(1 < n \in \mathbb{Z}\) olsun. \(\left\{ r_1, r_2, \dots, r_{\phi(n)} \right\}\) tam sayı kümesi
- her \(i\) için \(\gcd\left( r_i, n \right) = 1\) ve
- \(i \neq j\) için \(r_i \not\equiv r_j \pmod n\)
koşullarını sağlıyorsa bu kümeye modülo \(n\) indirgenmiş kalan sistemi denir.
Tanım 13.1’ndeki tam kalan sistemi \(\mathbb{Z}_n\)’nin bütün sınıflarından birer temsilci içeriyordu ve \(n\) elemanlıydı.
İndirgenmiş kalan sistemi ise yalnızca birim sınıflardan birer temsilci içerir; yani \(U(\mathbb{Z}_n)\) grubunun bir temsilci listesidir ve \(\phi(n)\) elemanlıdır.
En doğal örnek, bir tam kalan sisteminden \(n\) ile aralarında asal olmayanları atmakla elde edilir. Örneğin \(n = 10\) için \(\{0,1,\dots,9\}\) kümesinden geriye \(\{1, 3, 7, 9\}\) kalır ve \(\phi(10) = 4\)’tür.
Teorem 21.1 (İndirgenmiş Sistemi Bir Birimle Çarpmak) \(1 < n\) ve \(\gcd(a, n) = 1\) olsun. \(\left\{ r_1, \dots, r_{\phi(n)} \right\}\) modülo \(n\) bir indirgenmiş kalan sistemi ise
\[\left\{ a r_1, \ a r_2, \ \dots, \ a r_{\phi(n)} \right\}\]
kümesi de modülo \(n\) bir indirgenmiş kalan sistemidir.
İspat
İki koşulu doğrulayalım.
1. Her eleman \(n\) ile aralarında asaldır. \(\gcd(a,n) = 1\) ve \(\gcd\left( r_i, n \right) = 1\) olduğundan Teorem 5.3 gereği
\[\gcd\left( a r_i, \, n \right) = 1\]
2. Elemanlar ikişer ikişer kongrü değildir. \(i \neq j\) için
\[a r_i \equiv a r_j \pmod n\]
olduğunu varsayalım. \(\gcd(a,n) = 1\) olduğundan Teorem 12.3 gereği \(a\) sadeleştirilebilir:
\[r_i \equiv r_j \pmod n\]
Bu, \(\left\{ r_i \right\}\) kümesinin indirgenmiş kalan sistemi olmasıyla çelişir.
Küme \(\phi(n)\) elemanlıdır ve iki koşulu da sağladığından bir indirgenmiş kalan sistemidir.
\(\blacksquare\)
Teorem 21.1’in söylediği şey şudur: \(a\) ile çarpmak, birim sınıfları kendi aralarında karıştırır. Hiçbiri kaybolmaz, hiçbiri iki kez ortaya çıkmaz; yalnızca sıraları değişir.
Bu, Teorem 17.1’nun bir yansımasıdır: bir grupta sabit bir elemanla çarpmak daima birebir ve örtendir.
21.2 Euler Teoremi
Teorem 21.2 (Euler Teoremi) \(1 < n \in \mathbb{Z}\), \(a \in \mathbb{Z}\) ve \(\gcd(a, n) = 1\) olsun. Bu durumda
\[a^{\phi(n)} \equiv 1 \pmod n\]
İspat
\(\left\{ r_1, r_2, \dots, r_{\phi(n)} \right\}\) modülo \(n\) bir indirgenmiş kalan sistemi olsun.
Teorem 21.1 gereği
\[\left\{ a r_1, \ a r_2, \ \dots, \ a r_{\phi(n)} \right\}\]
kümesi de bir indirgenmiş kalan sistemidir. İki sistem de \(U(\mathbb{Z}_n)\) grubunun bütün sınıflarından birer temsilci içerdiğinden, ikinci listenin elemanları birinci listenin elemanlarına — belki farklı bir sırayla — kongrüdür.
O hâlde iki listenin çarpımları birbirine kongrüdür:
\[\left( a r_1 \right)\left( a r_2 \right) \cdots \left( a r_{\phi(n)} \right) \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod n\]
Sol taraftaki \(a\) çarpanlarını toplayalım; toplam \(\phi(n)\) tanedir:
\[a^{\phi(n)} \, r_1 r_2 \cdots r_{\phi(n)} \equiv r_1 r_2 \cdots r_{\phi(n)} \pmod n\]
Şimdi \(R := r_1 r_2 \cdots r_{\phi(n)}\) yazalım. Her \(r_i\) için \(\gcd\left( r_i, n \right) = 1\) olduğundan Teorem 5.3’in tekrarlı uygulanmasıyla
\[\gcd(R, n) = 1\]
O hâlde Teorem 12.3 gereği \(R\) sadeleştirilebilir:
\[a^{\phi(n)} \equiv 1 \pmod n\]
\(\blacksquare\)
Sonuç 21.1 (Fermat Teoremi Euler Teoreminin Özel Hâlidir) \(p\) bir asal sayı ve \(p \nmid a\) olsun. Önerme 20.1 gereği \(\phi(p) = p - 1\)’dir; Teorem 21.2 bu durumda
\[a^{p-1} \equiv 1 \pmod p\]
verir. Bu tam olarak Teorem 18.1’dır.
Teorem 18.1’nın ispatında \(1, 2, \dots, p-1\) sayılarını \(a\) ile çarpıp kalanların bir permütasyon olduğunu göstermiştik. Teorem 21.2’in ispatı da birebir aynı fikri kullanır; tek fark, listenin \(\{1, \dots, p-1\}\) yerine bir indirgenmiş kalan sistemi olmasıdır.
Fermat teoremini önce görmemizin nedeni, bu fikrin en sade hâlini oradaki somut listede tanımaktı.
21.3 Kuvvet Hesaplarına Uygulama
\(a^{N} \bmod n\) hesabı için:
- \(\gcd(a, n) = 1\) olduğunu doğrula. (Değilse aşağıdaki Örnek 21.2’e bakınız.)
- \(\phi(n)\) değerini Teorem 20.3 ile hesapla.
- Üssü \(\phi(n)\)’ye böl: \(N = \phi(n) \, q + r\).
- \(a^{N} = \left( a^{\phi(n)} \right)^{q} a^{r} \equiv a^{r} \pmod n\) yaz ve \(a^{r}\)’yi hesapla.
Örnek 21.1 (\(3^{100}\) Sayısının Son İki Rakamı) \(3^{100}\) sayısının son iki rakamını bulunuz.
Çözüm
Son iki rakamı bulmak, sayının \(100\) ile bölümünden kalanını bulmaktır.
1. Aralarında asallık. \(\gcd(3, 100) = 1\)’dir; Teorem 21.2 uygulanabilir.
2. \(\phi(100)\). \(100 = 2^{2} \cdot 5^{2}\) olduğundan Teorem 20.3 gereği
\[\phi(100) = 100 \left( 1 - \frac{1}{2} \right)\left( 1 - \frac{1}{5} \right) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40\]
O hâlde \(3^{40} \equiv 1 \pmod{100}\)’dür.
3. Üssü indirgeme. \(100 = 40 \cdot 2 + 20\) olduğundan
\[3^{100} = \left( 3^{40} \right)^{2} \cdot 3^{20} \equiv 3^{20} \pmod{100}\]
4. \(3^{20}\) hesabı. Kareler alarak ilerleyelim:
\[3^{4} = 81, \qquad 3^{5} = 243 \equiv 43 \pmod{100}\]
\[3^{10} = \left( 3^{5} \right)^{2} \equiv 43^{2} = 1849 \equiv 49 \pmod{100}\]
\[3^{20} = \left( 3^{10} \right)^{2} \equiv 49^{2} = 2401 \equiv 1 \pmod{100}\]
O hâlde
\[3^{100} \equiv 1 \pmod{100}\]
Son iki rakam \(01\)’dir.
\(\blacksquare\)
Örnek 21.2 (Aralarında Asal Olmadığında Ne Yapılır?) \(2^{1000}\) sayısının son iki rakamını bulunuz.
Çözüm
\(\gcd(2, 100) = 2 \neq 1\) olduğundan Teorem 21.2 doğrudan uygulanamaz. Bunun yerine \(100 = 4 \cdot 25\) ayrışmasını kullanıp iki parçada çalışacağız.
Modülo \(4\). \(1000 \geq 2\) olduğundan \(4 = 2^{2}\) sayısı \(2^{1000}\)’i böler:
\[2^{1000} \equiv 0 \pmod 4\]
Modülo \(25\). \(\gcd(2, 25) = 1\)’dir. Teorem 20.1 gereği
\[\phi(25) = 25 - 5 = 20\]
\(1000 = 20 \cdot 50\) olduğundan Teorem 21.2 gereği
\[2^{1000} = \left( 2^{20} \right)^{50} \equiv 1^{50} = 1 \pmod{25}\]
Birleştirme. \(\gcd(4, 25) = 1\) olduğundan Teorem 16.1 uygulanabilir:
\[x \equiv 0 \pmod 4, \qquad x \equiv 1 \pmod{25}\]
\(x = 25k + 1\) yazıp birinci denklemde yerine koyalım:
\[25k + 1 \equiv 0 \pmod 4 \implies k + 1 \equiv 0 \pmod 4 \implies k \equiv 3 \pmod 4\]
(Burada \(25 \equiv 1 \pmod 4\) olmasını kullandık.) \(k = 3\) için
\[x = 75 + 1 = 76\]
O hâlde \(2^{1000} \equiv 76 \pmod{100}\)’dür; son iki rakam \(76\)’dır.
\(\blacksquare\)
Örnek 21.3 (\(855 \mid n^{72} - 1\) Bölünebilmesi) \(\gcd(n, 855) = 1\) koşulunu sağlayan her \(n\) tam sayısı için
\[n^{72} \equiv 1 \pmod{855}\]
olduğunu gösteriniz.
Çözüm
\(855 = 3^{2} \cdot 5 \cdot 19\)’dur. Bu üç asal kuvvet ikişer ikişer aralarında asal olduğundan, Teorem 5.2 gereği
\[9 \mid n^{72} - 1, \qquad 5 \mid n^{72} - 1, \qquad 19 \mid n^{72} - 1\]
olduğunu ayrı ayrı göstermek yeterlidir. Her üçünde de \(\gcd(n, 855) = 1\) olması ilgili modülle aralarında asallığı garanti eder.
Modülo \(9\). \(\phi(9) = 6\)’dır; Teorem 21.2 gereği \(n^{6} \equiv 1 \pmod 9\)’dur. \(72 = 6 \cdot 12\) olduğundan
\[n^{72} = \left( n^{6} \right)^{12} \equiv 1 \pmod 9\]
Modülo \(5\). \(\phi(5) = 4\)’tür; \(n^{4} \equiv 1 \pmod 5\)’tir. \(72 = 4 \cdot 18\) olduğundan
\[n^{72} = \left( n^{4} \right)^{18} \equiv 1 \pmod 5\]
Modülo \(19\). \(\phi(19) = 18\)’dir; \(n^{18} \equiv 1 \pmod{19}\)’dur. \(72 = 18 \cdot 4\) olduğundan
\[n^{72} = \left( n^{18} \right)^{4} \equiv 1 \pmod{19}\]
Birleştirme. Üç modül de \(n^{72} - 1\) sayısını böler ve ikişer ikişer aralarında asaldır; o hâlde çarpımları da böler:
\[855 = 9 \cdot 5 \cdot 19 \ \mid \ n^{72} - 1\]
\(\blacksquare\)
Teorem 21.2 doğrudan \(n^{432} \equiv 1 \pmod{855}\) verirdi (\(\phi(855) = 6 \cdot 4 \cdot 18 = 432\)). Ama biz çok daha küçük bir üs bulduk.
Nedeni şudur: her modül için ayrı ayrı çalışırken üssün her birinin \(\phi\) değerine bölünmesi yeterlidir; hepsinin çarpımına değil. Aranan en küçük üs
\[\operatorname{lcm}\left( \phi(9), \phi(5), \phi(19) \right) = \operatorname{lcm}(6, 4, 18) = 36\]
olur — nitekim \(72 = 2 \cdot 36\) de işe yarar. Bu, Euler teoreminin verdiğinden daha iyi bir üstür ve pratikte sık kullanılır.
21.4 Mertebe Kavramına Bir Bakış
Yukarıdaki gözlem doğal bir soruya götürür: \(a^{k} \equiv 1 \pmod n\) eşitliğini sağlayan en küçük \(k\) nedir?
Teorem 21.2 bize \(k = \phi(n)\) değerinin daima işe yaradığını söylüyor. Ama bu, en küçük değer olmak zorunda değildir: Örnek 21.1’de \(3^{20} \equiv 1 \pmod{100}\) bulmuştuk, oysa \(\phi(100) = 40\)’tır. Benzer biçimde Örnek 21.3’te \(\phi(855) = 432\) iken \(72\) üssünün yettiğini gördük.
\(a^{k} \equiv 1 \pmod n\) eşitliğini sağlayan en küçük pozitif \(k\) değerine, \(a\) sayısının modülo \(n\) mertebesi denir. Mertebenin daima \(\phi(n)\)’yi böldüğü gösterilebilir; bu da mertebe ararken yalnızca \(\phi(n)\)’nin bölenlerini denemenin yeterli olduğu anlamına gelir.
Mertebe, kuvvet kongrüanslarının ve primitif köklerin anahtar kavramıdır. Sayılar Teorisi 2 dersinde ayrı bir bölümde ayrıntılı olarak ele alınmaktadır.
21.5 Euler Teoremiyle Ters Bulma
Sonuç 21.2 (Çarpımsal Tersin Kapalı Formülü) \(1 < n\) ve \(\gcd(a, n) = 1\) olsun. Bu durumda \(a\)’nın modülo \(n\) çarpımsal tersi
\[a^{-1} \equiv a^{\phi(n) - 1} \pmod n\]
ile verilir.
Gerçekten de Teorem 21.2 gereği
\[a \cdot a^{\phi(n) - 1} = a^{\phi(n)} \equiv 1 \pmod n\]
olur; Tanım 15.2 gereği bu, \(a^{\phi(n)-1}\) sayısının \(a\)’nın tersi olduğunu söyler.
Örnek 21.4 (\(7\) Sayısının Modülo \(30\) Tersi) \(7\) tam sayısının modülo \(30\) çarpımsal tersini Sonuç 21.2 ile bulunuz.
Çözüm
\(30 = 2 \cdot 3 \cdot 5\) olduğundan
\[\phi(30) = 30 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 8\]
\(\gcd(7, 30) = 1\) olduğundan Sonuç 21.2 uygulanabilir:
\[7^{-1} \equiv 7^{8 - 1} = 7^{7} \pmod{30}\]
Şimdi \(7^{7}\) değerini adım adım hesaplayalım:
\[7^{2} = 49 \equiv 19 \pmod{30}\]
\[7^{4} = \left( 7^{2} \right)^{2} \equiv 19^{2} = 361 \equiv 1 \pmod{30}\]
(Burada \(\phi(30) = 8\) üssüne hiç ulaşmadan \(1\)’e vardık; bu, yukarıda mertebe üzerine söylediklerimizin bir örneğidir.)
\[7^{7} = 7^{4} \cdot 7^{2} \cdot 7 \equiv 1 \cdot 19 \cdot 7 = 133 \equiv 13 \pmod{30}\]
O hâlde \(7\)’nin modülo \(30\) tersi \(13\)’tür.
(Sağlama: \(7 \cdot 13 = 91 = 3 \cdot 30 + 1\) ✓)
\(\blacksquare\)
Ters bulmanın iki yolunu gördük:
- Öklid algoritması (Örnek 15.5): \(\phi(n)\) bilinmese de çalışır ve hızlıdır.
- Euler teoremi (Sonuç 21.2): kapalı bir formül verir, ama \(\phi(n)\)’yi — dolayısıyla \(n\)’nin asal çarpanlarını — bilmeyi gerektirir.
Büyük sayılarda çarpanlara ayırmak çok zor olduğundan pratikte birinci yol kullanılır. İkinci yolun değeri teoriktir: tersin varlığını ve biçimini tek satırda açıklar.
21.6 Çalışma Problemleri
Alıştırma 21.1 (Euler Teoremiyle Kalan Hesapları) Aşağıdaki kalanları bulunuz.
a) \(7^{1000}\) sayısının \(24\) ile bölümünden kalan.
b) \(9^{794}\) sayısının \(100\) ile bölümünden kalan.
c) \(5^{2000}\) sayısının \(63\) ile bölümünden kalan.
d) \(3^{1000}\) sayısının son üç rakamı.
Alıştırma 21.2 (Euler Teoremiyle Bölünebilme) Aşağıdakileri ispatlayınız.
a) \(\gcd(n, 100) = 1\) olan her \(n\) için \(100 \mid n^{20} - 1\).
b) \(\gcd(n, 65) = 1\) olan her \(n\) için \(65 \mid n^{12} - 1\).
c) Her \(n\) tam sayısı için \(\gcd(n, 1729) = 1\) ise \(1729 \mid n^{36} - 1\).
İpucu (c): \(1729 = 7 \cdot 13 \cdot 19\)’dur.
Alıştırma 21.3 (İndirgenmiş Kalan Sistemleri) a) Modülo \(18\) bir indirgenmiş kalan sistemi yazınız ve eleman sayısının \(\phi(18)\) ile uyuştuğunu doğrulayınız.
b) \(\{1, 5, 7, 11\}\) kümesinin modülo \(12\) bir indirgenmiş kalan sistemi olduğunu gösteriniz. Her elemanı \(5\) ile çarpıp sonucu modülo \(12\) indirgeyiniz ve Teorem 21.1’in söylediğini doğrulayınız.
c) \(2 < n\) ve \(\left\{ r_1, \dots, r_{\phi(n)} ight\}\) modülo \(n\) bir indirgenmiş kalan sistemi olsun.
\[r_1 + r_2 + \cdots + r_{\phi(n)} \equiv 0 \pmod n\]
olduğunu gösteriniz.
İpucu (c): \(\gcd(r, n) = 1\) ise \(\gcd(n - r, n) = 1\)’dir; elemanları \(r\) ile \(n-r\) biçiminde ikişerli eşleştiriniz ve \(2 < n\) iken \(r eq n - r\) olduğunu gözlemleyiniz.
Alıştırma 21.4 (Euler Teoreminin Bir Genellemesi) \(m, n\) pozitif tam sayıları ve \(\gcd(a, mn) = 1\) olsun.
a) \(a^{\operatorname{lcm}\left( \phi(m), \phi(n) \right)} \equiv 1 \pmod{mn}\) olduğunu gösteriniz (\(\gcd(m,n) = 1\) varsayarak).
b) Bu üssün, Teorem 21.2’in verdiği \(\phi(mn) = \phi(m)\phi(n)\) üssünden küçük olabileceğini bir örnekle gösteriniz.
İpucu (b): \(m = 8\), \(n = 5\) deneyiniz.