18 Fermat Teoremi ve Sözde-Asal Sayılar
Elimizde artık büyük kuvvetlerin kalanlarını hesaplamak için bir yöntem var: modülde \(1\) veya \(-1\) veren bir kuvvet aramak. Ama bu arama deneme yanılmaya dayanıyordu. Fermat’nın küçük teoremi, modül asal olduğunda böyle bir kuvvetin nerede olduğunu doğrudan söyler ve aramaya son verir.
18.1 Fermat Teoremi
Teorem 18.1 (Fermat’nın Küçük Teoremi) \(p\) bir asal sayı ve \(a \in \mathbb{Z}\) olsun. Eğer \(p \nmid a\) ise
\[a^{p-1} \equiv 1 \pmod p\]
İspat
\(p \nmid a\) olduğundan Önerme 9.1 gereği \(\gcd(a, p) = 1\)’dir.
Şimdi şu \(p-1\) sayıyı göz önüne alalım:
\[a \cdot 1, \quad a \cdot 2, \quad \dots, \quad a \cdot (p-1)\]
1. Hiçbiri \(p\) ile bölünmez. \(1 \leq i \leq p-1\) olsun. \(p \nmid a\) ve \(p \nmid i\)’dir (çünkü \(0 < i < p\)). Teorem 9.1 gereği bir asal, bölmediği iki sayının çarpımını da bölemez; o hâlde \(p \nmid ai\)’dir.
2. İkişer ikişer kongrü değildirler. \(1 \leq i < j \leq p-1\) için
\[ai \equiv aj \pmod p\]
olduğunu varsayalım. \(\gcd(a,p) = 1\) olduğundan Sonuç 12.1 (1) gereği \(a\) sadeleştirilebilir:
\[i \equiv j \pmod p\]
Ama \(0 < j - i < p\) olduğundan \(p \nmid j - i\)’dir — çelişki.
3. Sonuç: kalanlar bir permütasyondur. Her \(ai\) sayısının modülo \(p\) kalanı, \(1\) ile \(p-1\) arasındadır (1. adım gereği \(0\) olamaz). Bu \(p-1\) kalan ikişer ikişer farklı olduğundan (2. adım), \(\{1, 2, \dots, p-1\}\) kümesinin elemanlarını bir sırayla verirler.
Şimdi bütün bu sayıları çarpalım. Sol taraf ile sağ taraf aynı kalanları — belki farklı sırada — içerdiğinden
\[(a \cdot 1)(a \cdot 2) \cdots \big( a (p-1) \big) \equiv 1 \cdot 2 \cdots (p-1) \pmod p\]
Sol taraftaki \(a\) çarpanlarını toplayalım:
\[a^{p-1} \, (p-1)! \equiv (p-1)! \pmod p\]
4. Sadeleştirme. \((p-1)!\) sayısı \(1, 2, \dots, p-1\) çarpanlarından oluşur ve hiçbiri \(p\) ile bölünmez; Sonuç 9.2 gereği \(p \nmid (p-1)!\)’dir. O hâlde Sonuç 12.1 (2) gereği \((p-1)!\) sadeleştirilebilir:
\[a^{p-1} \equiv 1 \pmod p\]
\(\blacksquare\)
Sonuç 18.1 (Fermat Teoreminin Kısıtsız Biçimi) \(p\) bir asal sayı olmak üzere, her \(a \in \mathbb{Z}\) için
\[a^{p} \equiv a \pmod p\]
Gerçekten de iki durum vardır. \(p \mid a\) ise her iki taraf da \(\equiv 0 \pmod p\)’dir. \(p \nmid a\) ise Teorem 18.1 gereği \(a^{p-1} \equiv 1\)’dir; her iki tarafı \(a\) ile çarparsak \(a^{p} \equiv a\) bulunur.
İki biçim arasındaki fark önemlidir:
- \(a^{p-1} \equiv 1 \pmod p\) — kullanışlı olan budur, ama \(p \nmid a\) koşulunu gerektirir.
- \(a^{p} \equiv a \pmod p\) — koşulsuzdur, ama sadeleştirilmiş bilgi taşımaz.
Kalan hesaplarında birincisi, teorik ispatlarda çoğunlukla ikincisi kullanılır.
18.2 Kuvvet Hesaplarına Uygulama
\(a^{N} \bmod p\) hesabı artık üç adımdır:
- \(\gcd(a, p) = 1\) olduğunu doğrula.
- Üssü \(p-1\)’e böl: \(N = (p-1)q + r\).
- \(a^{N} = \left( a^{p-1} \right)^{q} a^{r} \equiv a^{r} \pmod p\) yaz ve küçük olan \(a^r\)’yi hesapla.
Örnek 18.1 (\(8^{138}\) Sayısının \(13\) ile Bölümünden Kalan) \(8^{138}\) tam sayısının \(13\) ile bölünmesinden elde edilen kalanı bulunuz.
Çözüm
\(13\) asaldır ve \(13 \nmid 8\)’dir; Teorem 18.1 uygulanabilir:
\[8^{12} \equiv 1 \pmod{13}\]
Üssü \(12\)’ye bölelim:
\[138 = 12 \cdot 11 + 6\]
Buradan
\[8^{138} = \left( 8^{12} \right)^{11} \cdot 8^{6} \equiv 1^{11} \cdot 8^{6} = 8^{6} \pmod{13}\]
Geriye \(8^6\)’yı hesaplamak kaldı. Küçük adımlarla ilerleyelim:
\[8^2 = 64 = 4 \cdot 13 + 12 \equiv 12 \equiv -1 \pmod{13}\]
O hâlde
\[8^{6} = \left( 8^{2} \right)^{3} \equiv (-1)^{3} = -1 \equiv 12 \pmod{13}\]
\(0 \leq 12 < 13\) olduğundan aranan kalan \(12\)’dir.
\(\blacksquare\)
Örnek 18.2 (Bir Bölünebilme İddiası) \(\gcd(n, 35) = 1\) koşulunu sağlayan her \(n\) tam sayısı için
\[n^{12} \equiv 1 \pmod{35}\]
olduğunu gösteriniz.
Çözüm
\(35 = 5 \cdot 7\) ve \(\gcd(5,7) = 1\)’dir. Teorem 5.2 gereği \(5 \mid n^{12} - 1\) ve \(7 \mid n^{12} - 1\) olduğunu ayrı ayrı göstermek yeterlidir.
Modülo \(5\). \(\gcd(n,35) = 1\) olduğundan \(5 \nmid n\)’dir. Teorem 18.1 gereği
\[n^{4} \equiv 1 \pmod 5\]
Her iki tarafın küpünü alalım:
\[n^{12} = \left( n^{4} \right)^{3} \equiv 1 \pmod 5\]
Modülo \(7\). Benzer biçimde \(7 \nmid n\)’dir ve Teorem 18.1 gereği
\[n^{6} \equiv 1 \pmod 7 \implies n^{12} = \left( n^{6} \right)^{2} \equiv 1 \pmod 7\]
Birleştirme. \(5 \mid n^{12} - 1\), \(7 \mid n^{12} - 1\) ve \(\gcd(5,7) = 1\) olduğundan
\[35 \ \mid \ n^{12} - 1 \qquad \text{yani} \qquad n^{12} \equiv 1 \pmod{35}\]
\(\blacksquare\)
18.3 Asallık Testi Olarak Fermat
Sonuç 18.1’in karşıt tersi, bir sayının asal olmadığını göstermenin pratik bir yolunu verir: eğer \(a^n \not\equiv a \pmod n\) olacak bir \(a\) bulunursa, \(n\) asal olamaz — ve bunun için \(n\)’yi çarpanlarına ayırmaya hiç gerek yoktur.
Örnek 18.3 (\(117\) Asal mıdır?) \(2^{117} \equiv 44 \pmod{117}\) olduğunu gösteriniz ve buradan \(117\) sayısının asal olmadığı sonucunu çıkarınız.
Çözüm
\(117 = 9 \cdot 13\) olduğunu kullanacağız (bu bilgi yalnızca hesabı kolaylaştırmak içindir; testin kendisi çarpanlara ayırma gerektirmez).
Modülo \(9\). \(2\)’nin kuvvetlerini hesaplayalım:
\[2^1 \equiv 2, \quad 2^2 \equiv 4, \quad 2^3 \equiv 8, \quad 2^4 \equiv 7, \quad 2^5 \equiv 5, \quad 2^6 \equiv 1 \pmod 9\]
\(117 = 6 \cdot 19 + 3\) olduğundan
\[2^{117} = \left( 2^{6} \right)^{19} \cdot 2^{3} \equiv 2^{3} = 8 \pmod 9\]
Modülo \(13\). \(13\) asal ve \(13 \nmid 2\) olduğundan Teorem 18.1 gereği \(2^{12} \equiv 1 \pmod{13}\)’tür. \(117 = 12 \cdot 9 + 9\) olduğundan
\[2^{117} \equiv 2^{9} \pmod{13}\]
\(2^9 = 512 = 39 \cdot 13 + 5\) olduğundan
\[2^{117} \equiv 5 \pmod{13}\]
Birleştirme (Çin kalan teoremi). Sistem şudur:
\[x \equiv 8 \pmod 9, \qquad x \equiv 5 \pmod{13}\]
\(x = 8 + 9k\) yazıp ikinci denklemde yerine koyalım:
\[8 + 9k \equiv 5 \pmod{13} \implies 9k \equiv -3 \equiv 10 \pmod{13}\]
\(9 \cdot 3 = 27 \equiv 1 \pmod{13}\) olduğundan \(9\)’un tersi \(3\)’tür; her iki tarafı \(3\) ile çarpalım:
\[k \equiv 30 \equiv 4 \pmod{13}\]
\(k = 4\) için \(x = 8 + 36 = 44\) bulunur:
\[2^{117} \equiv 44 \pmod{117}\]
Sonuç. \(117\) asal olsaydı Sonuç 18.1 gereği \(2^{117} \equiv 2 \pmod{117}\) olması gerekirdi. Oysa
\[44 \not\equiv 2 \pmod{117}\]
O hâlde \(117\) asal değildir.
(Nitekim \(117 = 9 \cdot 13\)’tür.)
\(\blacksquare\)
18.4 Testin Tersi Neden Çalışmaz?
Fermat testinin bir sayının asal olmadığını gösterdiğini gördük. Peki test geçilirse sayı asal mıdır? Yani
\[n \mid 2^{n} - 2 \implies n \text{ asaldır}\]
önermesi doğru mudur? Cevap hayırdır ve karşı örnek şaşırtıcı biçimde küçüktür.
Lemma 18.1 (İki Asalın Çarpımına Geçiş) \(a \in \mathbb{Z}\) ve \(p \neq q\) iki farklı asal sayı olsun. Eğer
\[a^{p} \equiv a \pmod q \qquad \text{ve} \qquad a^{q} \equiv a \pmod p\]
ise
\[a^{pq} \equiv a \pmod{pq}\]
İspat
Modülo \(q\). Hipotez gereği \(a^p \equiv a \pmod q\)’dur. Her iki tarafın \(q\)’uncu kuvvetini alalım:
\[a^{pq} = \left( a^{p} \right)^{q} \equiv a^{q} \pmod q\]
Öte yandan \(q\) asal olduğundan Sonuç 18.1 gereği \(a^{q} \equiv a \pmod q\)’dur. Geçişme ile
\[a^{pq} \equiv a \pmod q\]
Modülo \(p\). Simetrik biçimde, hipotezdeki \(a^q \equiv a \pmod p\) eşitliğinin \(p\)’inci kuvvetini alalım:
\[a^{pq} = \left( a^{q} \right)^{p} \equiv a^{p} \pmod p\]
ve Sonuç 18.1 gereği \(a^p \equiv a \pmod p\) olduğundan
\[a^{pq} \equiv a \pmod p\]
Birleştirme. \(p \mid a^{pq} - a\) ve \(q \mid a^{pq} - a\)’dır. \(p \neq q\) farklı asallar olduğundan Sonuç 9.1 gereği \(\gcd(p,q) = 1\)’dir; Teorem 5.2 gereği
\[pq \ \mid \ a^{pq} - a \qquad \text{yani} \qquad a^{pq} \equiv a \pmod{pq}\]
\(\blacksquare\)
Örnek 18.4 (\(341\) Testi Geçer Ama Asal Değildir) \(341 = 11 \cdot 31\) olduğunu ve buna rağmen
\[2^{341} \equiv 2 \pmod{341}\]
olduğunu gösteriniz.
Çözüm
Lemma 18.1’ü \(p = 11\), \(q = 31\) ve \(a = 2\) ile uygulayacağız. İki koşulu doğrulamalıyız.
Koşul 1: \(2^{11} \equiv 2 \pmod{31}\).
\[2^{5} = 32 \equiv 1 \pmod{31}\]
olduğundan
\[2^{11} = 2 \cdot \left( 2^{5} \right)^{2} \equiv 2 \cdot 1 = 2 \pmod{31}\]
Koşul 2: \(2^{31} \equiv 2 \pmod{11}\).
\(11\) asal ve \(11 \nmid 2\) olduğundan Teorem 18.1 gereği \(2^{10} \equiv 1 \pmod{11}\)’dir. Buradan
\[2^{31} = 2 \cdot \left( 2^{10} \right)^{3} \equiv 2 \cdot 1 = 2 \pmod{11}\]
Sonuç. Lemma 18.1 gereği
\[2^{341} = 2^{11 \cdot 31} \equiv 2 \pmod{11 \cdot 31} = \pmod{341}\]
Yani \(341 \mid 2^{341} - 2\)’dir. Buna rağmen \(341 = 11 \cdot 31\) olduğundan \(341\) asal değildir.
\(\blacksquare\)
Tanım 18.1 (Sözde-Asal Sayı) \(1 < n\) asal olmayan bir tam sayı olsun. Eğer
\[n \mid 2^{n} - 2\]
ise \(n\) sayısına bir sözde-asal sayı denir.
Örnek 18.5 (İlk Sözde-Asal) Örnek 18.4 gereği \(341\) bir sözde-asal sayıdır. Bu, en küçük sözde-asal sayıdır.
18.5 Sözde-Asallar Sonsuzdur
Sözde-asallar birkaç istisna olsaydı Fermat testi pratikte yine de güvenilir olurdu. Ne yazık ki durum böyle değildir.
Teorem 18.2 (Sonsuz Çoklukta Sözde-Asal Vardır) Sonsuz sayıda sözde-asal sayı vardır.
İspat
Aşağıdaki iddiayı ispatlarsak sonuç gelir.
İddia. \(n\) bir tek sözde-asal sayı ise, \(M_n := 2^{n} - 1\) sayısı da \(n\)’den büyük bir tek sözde-asal sayıdır.
1. \(M_n\) tektir. \(2^n\) çift olduğundan \(2^n - 1\) tektir.
2. \(M_n\) asal değildir. \(n\) sözde-asal olduğundan asal değildir; o hâlde
\[n = r \cdot s, \qquad 1 < r \leq s < n\]
olacak biçimde \(r, s\) tam sayıları vardır. \(r \mid n\) olduğundan Örnek 3.7 gereği
\[2^{r} - 1 \ \mid \ 2^{n} - 1 = M_n\]
Ayrıca \(1 < r < n\) olduğundan
\[1 < 2^{r} - 1 < 2^{n} - 1 = M_n\]
Demek ki \(M_n\) sayısının \(1\) ile kendisinden farklı bir pozitif böleni vardır; asal değildir.
3. \(M_n \mid 2^{M_n} - 2\). \(n\) sözde-asal olduğundan \(n \mid 2^n - 2\)’dir; yani
\[2^{n} - 2 = n k\]
olacak biçimde bir \(k\) pozitif tam sayısı vardır. Şimdi \(2^{M_n - 1}\) ifadesini hesaplayalım:
\[2^{M_n - 1} = 2^{\left( 2^{n} - 1 \right) - 1} = 2^{2^{n} - 2} = 2^{nk} = \left( 2^{n} \right)^{k}\]
Buradan
\[2^{M_n - 1} - 1 = \left( 2^{n} \right)^{k} - 1\]
olur. Çarpanlara ayırma özdeşliği gereği (bkz. Alıştırma 1.2)
\[\left( 2^{n} \right)^{k} - 1 = \left( 2^{n} - 1 \right)\left( \left( 2^{n} \right)^{k-1} + \cdots + 2^{n} + 1 \right)\]
Sağ taraftaki ilk çarpan tam olarak \(M_n\)’dir. O hâlde
\[M_n \ \mid \ 2^{M_n - 1} - 1\]
Her iki tarafı \(2\) ile çarparsak
\[M_n \ \mid \ 2^{M_n} - 2\]
bulunur. (Burada \(M_n\) tek olduğundan \(2\) ile çarpmak bölünebilmeyi bozmaz; daha doğrusu \(2^{M_n} - 2 = 2\left( 2^{M_n-1} - 1 \right)\) eşitliğini kullandık.)
4. \(M_n > n\). Alıştırma 1.3 gereği her \(2 < n\) için \(n + 1 < 2^{n}\)’dir; buradan
\[n < 2^{n} - 1 = M_n\]
İddia ispatlandı.
Sonuç. \(341\) bir tek sözde-asal sayıdır (Örnek 18.4). İddiayı tekrar tekrar uygularsak
\[341 < M_{341} < M_{M_{341}} < \cdots\]
biçiminde, kesin artan sonsuz bir tek sözde-asal sayı dizisi elde ederiz. O hâlde sözde-asal sayılar sonsuzdur.
\(\blacksquare\)
Sözde-asalların sonsuz olması testi işe yaramaz kılmaz. Bunun iki nedeni vardır:
- Sözde-asallar seyrektir: \(10^{10}\)’a kadar yaklaşık \(455\) milyon asal varken, yalnızca \(14884\) sözde-asal vardır.
- Taban değiştirilebilir. \(341\) sayısı \(2\) tabanında testi geçer ama \(3\) tabanında geçmez: \(3^{341} \not\equiv 3 \pmod{341}\)’dir. Birden çok tabanla test etmek yanılma olasılığını hızla düşürür.
Modern asallık testlerinin çekirdeğinde hâlâ bu fikir vardır.
18.6 Çalışma Problemleri
Alıştırma 18.1 (Fermat ile Kalan Hesapları) Aşağıdaki kalanları bulunuz.
a) \(5^{100}\) sayısının \(17\) ile bölümünden kalan.
b) \(7^{222}\) sayısının \(11\) ile bölümünden kalan.
c) \(2^{1000}\) sayısının \(23\) ile bölümünden kalan.
Alıştırma 18.2 (Fermat ile Bölünebilme) Aşağıdakileri ispatlayınız.
a) \(\gcd(n, 42) = 1\) olan her \(n\) tam sayısı için \(168 \mid n^{6} - 1\).
b) \(\gcd(n, 133) = \gcd(m, 133) = 1\) olan her \(n, m\) tam sayısı için \(133 \mid n^{18} - m^{18}\).
c) Her \(n\) tam sayısı için \(30 \mid n^{5} - n\).
İpucu (a): \(168 = 8 \cdot 3 \cdot 7\)’dir; modülo \(8\) için \(n\)’nin tek olduğunu ve Örnek 2.3’i kullanınız.
Alıştırma 18.3 (Kuvvetlerin Kongrüansı) \(p\) bir asal sayı ve \(a, b \in \mathbb{Z}\) olsun.
a) \(a^{p} \equiv b^{p} \pmod p\) ise \(a \equiv b \pmod p\) olduğunu gösteriniz.
b) \(a^{p} \equiv b^{p} \pmod p\) ise \(a^{p} \equiv b^{p} \pmod{p^{2}}\) olduğunu gösteriniz.
İpucu (b): (a) şıkkından \(a = b + kp\) yazınız ve \(a^p\) ifadesini binom açılımıyla açıp \(p^2\) ile bölünmeyen terimleri toplayınız.
Alıştırma 18.4 (Kuvvet Toplamları) \(p\) bir tek asal sayı olmak üzere aşağıdakileri ispatlayınız.
a) \(1^{p-1} + 2^{p-1} + \cdots + (p-1)^{p-1} \equiv -1 \pmod p\)
b) \(1^{p} + 2^{p} + \cdots + (p-1)^{p} \equiv 0 \pmod p\)
İpucu (a): Her terime Teorem 18.1’yı uygulayınız. (b): Her terime Sonuç 18.1’i uygulayıp Örnek 1.1’daki toplam formülünü kullanınız.
Alıştırma 18.5 (Farklı Bir İspat) Sonuç 18.1’i, yani her \(a\) tam sayısı ve her \(p\) asalı için \(a^{p} \equiv a \pmod p\) olduğunu, \(a\) üzerinden tümevarımla ispatlayınız.
İpucu: Başlangıç adımı \(a = 1\)’dir. Tümevarım adımında \((a+1)^p\) ifadesini binom açılımıyla açıp Alıştırma 9.2’u kullanınız; negatif \(a\) değerleri için önce \(a \equiv a + p\) olduğunu gözlemleyiniz.