19 Wilson Teoremi
Fermat teoremi bir sayının asal olmadığını göstermeye yarıyordu, ama asal olduğunu kanıtlamıyordu; sözde-asallar tam olarak bu boşluktan doğuyordu. Wilson teoremi ise bu boşluğu kapatır: asallığı, tek bir kongrüansla — istisnasız — karakterize eder.
19.1 Hazırlık: Kendi Tersi Olan Sınıflar
Wilson teoreminin ispatı, \(1\) ile \(p-1\) arasındaki sayıları çarpımsal tersleriyle eşleştirmeye dayanır. Bu eşleştirmenin işe yaraması için önce kendi tersi olan sayıları belirlememiz gerekir.
Lemma 19.1 (\(x^2 \equiv 1\) Denkleminin Çözümleri) \(p\) bir asal sayı olsun.
\[x^{2} \equiv 1 \pmod p\]
denkleminin çözümleri tam olarak \(x \equiv 1\) ve \(x \equiv -1 \pmod p\)’dir.
İspat
\(x^2 \equiv 1 \pmod p\) olsun. Bu, \(p \mid x^2 - 1\), yani
\[p \ \mid \ (x-1)(x+1)\]
demektir. \(p\) asal olduğundan Teorem 9.1 gereği \(p \mid x - 1\) veya \(p \mid x + 1\)’dir; yani
\[x \equiv 1 \pmod p \qquad \text{veya} \qquad x \equiv -1 \pmod p\]
Tersine, bu iki sınıfın her ikisi de denklemi sağlar: \(1^2 = 1\) ve \((-1)^2 = 1\)’dir.
\(\blacksquare\)
\(p\) asallığı vazgeçilmezdir. Örneğin \(n = 8\) için Örnek 17.4’nda gördüğümüz gibi
\[1^{2} \equiv 3^{2} \equiv 5^{2} \equiv 7^{2} \equiv 1 \pmod 8\]
olur; denklemin dört çözümü vardır. Örnek 15.5’teki \(49^2 \equiv 1 \pmod{120}\) eşitliği de aynı olgunun bir örneğidir.
19.2 Wilson Teoremi
Teorem 19.1 (Wilson Teoremi) \(p\) bir asal sayı olsun. Bu durumda
\[(p-1)! \equiv -1 \pmod p\]
İspat
Küçük durumlar. \(p = 2\) için \((2-1)! = 1\) ve \(1 \equiv -1 \pmod 2\)’dir ✓. \(p = 3\) için \((3-1)! = 2\) ve \(2 \equiv -1 \pmod 3\)’tür ✓.
Bundan sonra \(p \geq 5\) varsayalım.
1. Her sayının tek bir eşi vardır. \(a \in \{1, 2, \dots, p-1\}\) olsun. \(p\) asal ve \(p \nmid a\) olduğundan \(\gcd(a,p) = 1\)’dir; Önerme 15.1 gereği
\[a a' \equiv 1 \pmod p\]
olacak biçimde tek türlü belirli bir \(a' \in \{1, 2, \dots, p-1\}\) vardır. Bu \(a'\) sayısına \(a\)’nın eşi diyelim. Eşlik karşılıklıdır: \(a\)’nın eşi \(a'\) ise \(a'\)’nün eşi de \(a\)’dır.
2. Yalnızca \(1\) ve \(p-1\) kendi eşidir. \(a = a'\) olması \(a^2 \equiv 1 \pmod p\) demektir. Lemma 19.1 gereği bu ancak
\[a \equiv 1 \qquad \text{veya} \qquad a \equiv -1 \pmod p\]
hâlinde olur. \(1 \leq a \leq p-1\) aralığında bu iki sınıfın temsilcileri sırasıyla \(a = 1\) ve \(a = p-1\)’dir.
3. Ortadaki sayılar ikişerli gruplanır. Geriye
\[\{ 2, 3, \dots, p-2 \}\]
kümesi kalır; bu kümede \(p - 3\) eleman vardır ve hiçbiri kendi eşi değildir. Her elemanın eşi yine bu kümededir (çünkü \(1\) ile \(p-1\) zaten kendi eşleridir ve eşlik tek türlü belirlidir). O hâlde bu küme, çarpımı \(\equiv 1\) olan
\[\frac{p-3}{2}\]
tane ikiliye ayrılır. (\(p \geq 5\) tek olduğundan \(p-3\) çifttir.) Bütün ikilileri çarparsak
\[2 \cdot 3 \cdots (p-2) \equiv \underbrace{1 \cdot 1 \cdots 1}_{\frac{p-3}{2} \text{ tane}} = 1 \pmod p\]
4. Sonuç. Şimdi eksik kalan iki çarpanı ekleyelim:
\[(p-1)! = 1 \cdot \big( 2 \cdot 3 \cdots (p-2) \big) \cdot (p-1) \equiv 1 \cdot 1 \cdot (p-1) \pmod p\]
\(p - 1 \equiv -1 \pmod p\) olduğundan
\[(p-1)! \equiv -1 \pmod p\]
\(\blacksquare\)
Örnek 19.1 (Küçük Asallarda Doğrulama)
| \(p\) | \((p-1)!\) | \((p-1)! \bmod p\) |
|---|---|---|
| \(2\) | \(1\) | \(1 \equiv -1\) |
| \(3\) | \(2\) | \(2 \equiv -1\) |
| \(5\) | \(24\) | \(4 \equiv -1\) |
| \(7\) | \(720\) | \(6 \equiv -1\) |
| \(11\) | \(3\,628\,800\) | \(10 \equiv -1\) |
Örneğin \(p = 7\) için ispattaki eşleştirme şöyledir: \(\{2, 4\}\) (\(2 \cdot 4 = 8 \equiv 1\)) ve \(\{3, 5\}\) (\(3 \cdot 5 = 15 \equiv 1\)). Kendi eşi olanlar \(1\) ile \(6\)’dır ve \(6! \equiv 1 \cdot 1 \cdot 6 = 6 \equiv -1 \pmod 7\)’dir.
19.3 Teoremin Tersi
Fermat teoreminin tersi yanlıştı. Wilson teoreminin tersi ise doğrudur — üstelik ispatı çok kısadır.
Teorem 19.2 (Wilson Teoreminin Tersi) \(1 < n \in \mathbb{Z}\) olsun. Eğer
\[(n-1)! \equiv -1 \pmod n\]
ise \(n\) asaldır.
İspat
Karşıt tersini ispatlayalım: \(n\) asal değilse \((n-1)! \not\equiv -1 \pmod n\) olduğunu gösterelim.
\(n\) asal olmasın. O hâlde \(n\)’nin
\[1 < a < n\]
koşulunu sağlayan bir \(a\) böleni vardır.
\(a\) sayısı \(1 \leq a \leq n-1\) aralığında olduğundan \((n-1)!\) çarpımının çarpanlarından biridir; dolayısıyla
\[a \ \mid \ (n-1)!\]
Şimdi \((n-1)! \equiv -1 \pmod n\) olduğunu varsayalım. Bu, \(n \mid (n-1)! + 1\) demektir. \(a \mid n\) olduğundan Teorem 3.1 gereği
\[a \ \mid \ (n-1)! + 1\]
\(a\) hem \((n-1)!\) sayısını hem de \((n-1)! + 1\) sayısını böldüğünden farklarını da böler:
\[a \ \mid \ \big( (n-1)! + 1 \big) - (n-1)! = 1\]
Buradan \(a = 1\) çıkar; oysa \(a > 1\) idi. Çelişki.
O hâlde \(n\) asal değilse \((n-1)! \not\equiv -1 \pmod n\)’dir.
\(\blacksquare\)
Teorem 19.1 ile Teorem 19.2 birlikte şunu verir: \(1 < n\) için
\[n \text{ asaldır} \iff (n-1)! \equiv -1 \pmod n\]
Bu, asallığın istisnasız bir ölçütüdür — Fermat testindeki gibi bir “sözde-asal” boşluğu yoktur.
Buna karşılık pratik bir test değildir: \((n-1)!\) sayısını hesaplamak, \(n\)’yi çarpanlarına ayırmaktan çok daha pahalıdır. Wilson teoreminin değeri hesapta değil, ispatlardadır.
19.4 Bileşik Sayılarda \((n-1)!\)
Teorem 19.2’nin ispatı \(n\) bileşikken \((n-1)! \equiv -1\) olamayacağını gösterdi. Peki \((n-1)!\) o zaman neye kongrüdür? Cevap neredeyse her zaman \(0\)’dır.
Teorem 19.3 (Bileşik Sayılarda Faktöriyel) \(4 \neq n\) bileşik bir tam sayı olsun (yani \(1 < n\) ve \(n\) asal değil). Bu durumda
\[(n-1)! \equiv 0 \pmod n\]
İspat
\(n\) bileşik olduğundan \(n = ab\) olacak biçimde \(1 < a \leq b < n\) tam sayıları vardır. İki duruma ayıralım.
Durum 1: \(a < b\). Bu durumda \(a\) ile \(b\) farklı sayılardır ve her ikisi de \(1 \leq a < b \leq n-1\) aralığındadır. O hâlde her ikisi de \((n-1)!\) çarpımında ayrı çarpanlar olarak görünür:
\[(n-1)! = 1 \cdots a \cdots b \cdots (n-1)\]
Buradan \(ab = n\) sayısı \((n-1)!\) değerini böler.
Durum 2: \(a = b\), yani \(n = a^{2}\). Bu durumda \(a > 1\)’dir ve \(n \neq 4\) olduğundan \(a \geq 3\)’tür.
\(a \geq 3\) olduğundan
\[2a < a \cdot a = n \implies 2a \leq n - 1\]
Demek ki \(a\) ile \(2a\) sayılarının ikisi de \(1\) ile \(n-1\) arasındadır ve birbirinden farklıdır. Her ikisi de \((n-1)!\) çarpımında ayrı çarpanlar olarak görünür; dolayısıyla
\[a \cdot 2a = 2a^{2} = 2n \ \mid \ (n-1)!\]
Özel olarak \(n \mid (n-1)!\)’dir.
Her iki durumda da \(n \mid (n-1)!\), yani \((n-1)! \equiv 0 \pmod n\)’dir.
\(\blacksquare\)
\(n = 4\) için \((4-1)! = 6\) ve
\[6 \equiv 2 \pmod 4\]
olur; ne \(-1\)’dir ne de \(0\). İspattaki Durum 2 tam olarak burada tıkanır: \(a = 2\) için \(2a = 4 = n\) olur ve \(2a\) sayısı artık \(n-1\) aralığına girmez.
\(4\), \((n-1)!\) değerinin \(0\)’a kongrü olmadığı tek bileşik sayıdır.
Sonuç 19.1 (\((n-2)!\) ile Asallık Ölçütü) \(1 < n \in \mathbb{Z}\) olsun. Bu durumda
\[n \text{ asaldır} \iff (n-2)! \equiv 1 \pmod n\]
Gerçekten de \((n-1)! = (n-1) \cdot (n-2)!\) ve \(n - 1 \equiv -1 \pmod n\) olduğundan
\[(n-1)! \equiv -(n-2)! \pmod n\]
yazılabilir. O hâlde \((n-1)! \equiv -1\) olması ile \((n-2)! \equiv 1\) olması aynı koşuldur; Teorem 19.1 ve Teorem 19.2 bunu asallığa denk kılar.
19.5 Faktöriyel İçeren Kongrüanslar
Wilson teoreminin asıl kullanım biçimi, büyük faktöriyellerin kalanlarını hesaplamaktır. Yöntem daima aynıdır: hedefteki faktöriyeli \((p-1)!\) ile ilişkilendirmek ve aradaki çarpanları modül cinsinden negatif temsilcilerle yazmak.
Örnek 19.2 (\(18! \equiv -1 \pmod{437}\)) \(18! \equiv -1 \pmod{437}\) olduğunu gösteriniz.
Çözüm
\(437 = 19 \cdot 23\)’tür ve \(19\) ile \(23\) farklı asallardır. Teorem 5.2 gereği
\[19 \mid 18! + 1 \qquad \text{ve} \qquad 23 \mid 18! + 1\]
olduğunu ayrı ayrı göstermek yeterlidir.
Modülo \(19\). \(19\) asal olduğundan Teorem 19.1 doğrudan uygulanır:
\[18! = (19-1)! \equiv -1 \pmod{19}\]
Modülo \(23\). \(23\) asal olduğundan Teorem 19.1 gereği
\[22! \equiv -1 \pmod{23}\]
Şimdi \(22!\) ile \(18!\) arasındaki farkı yazalım:
\[22! = 22 \cdot 21 \cdot 20 \cdot 19 \cdot 18!\]
Baştaki dört çarpanı negatif temsilcilerle yazalım:
\[22 \equiv -1, \quad 21 \equiv -2, \quad 20 \equiv -3, \quad 19 \equiv -4 \pmod{23}\]
Çarpımları:
\[22 \cdot 21 \cdot 20 \cdot 19 \equiv (-1)(-2)(-3)(-4) = 24 \equiv 1 \pmod{23}\]
O hâlde
\[-1 \equiv 22! \equiv 1 \cdot 18! = 18! \pmod{23}\]
Birleştirme. \(19 \mid 18! + 1\) ve \(23 \mid 18! + 1\) olduğundan, \(\gcd(19,23) = 1\) olması nedeniyle
\[437 = 19 \cdot 23 \ \mid \ 18! + 1 \qquad \text{yani} \qquad 18! \equiv -1 \pmod{437}\]
\(\blacksquare\)
Örnek 19.3 (\(97!\) Sayısının Modülo \(103\) Tersi) \(97!\) tam sayısının modülo \(103\) çarpımsal tersini bulunuz.
Çözüm
\(103\) asaldır; Teorem 19.1 gereği
\[102! \equiv -1 \pmod{103}\]
\(102!\) ile \(97!\) arasındaki çarpanları ayıralım:
\[102! = 102 \cdot 101 \cdot 100 \cdot 99 \cdot 98 \cdot 97!\]
Bu beş çarpanı negatif temsilcilerle yazalım:
\[102 \equiv -1, \quad 101 \equiv -2, \quad 100 \equiv -3, \quad 99 \equiv -4, \quad 98 \equiv -5 \pmod{103}\]
Çarpımları:
\[(-1)(-2)(-3)(-4)(-5) = -120\]
\(-120 + 103 = -17\) olduğundan \(-120 \equiv -17 \pmod{103}\)’tür. O hâlde
\[-1 \equiv 102! \equiv (-17) \cdot 97! \pmod{103}\]
Her iki tarafı \(-1\) ile çarpalım:
\[17 \cdot 97! \equiv 1 \pmod{103}\]
Tanım 15.2 gereği bu tam olarak aradığımız şeydir: \(97!\) sayısının modülo \(103\) tersi \(17\)’dir.
\(\blacksquare\)
Örnek 19.4 (\(14 \cdot 35!\) Sayısının \(41\) ile Bölümünden Kalan) \(14 \cdot (35!)\) tam sayısının \(41\) ile bölünmesinden elde edilen kalanı bulunuz.
Çözüm
\(41\) asaldır; Teorem 19.1 gereği
\[40! \equiv -1 \pmod{41}\]
Aradaki çarpanları ayıralım:
\[40! = 40 \cdot 39 \cdot 38 \cdot 37 \cdot 36 \cdot 35!\]
Negatif temsilciler:
\[40 \equiv -1, \quad 39 \equiv -2, \quad 38 \equiv -3, \quad 37 \equiv -4, \quad 36 \equiv -5 \pmod{41}\]
Çarpımları \(-120\)’dir ve \(-120 + 123 = 3\) olduğundan \(-120 \equiv 3 \pmod{41}\)’dir. O hâlde
\[-1 \equiv 40! \equiv 3 \cdot 35! \pmod{41}\]
Şimdi her iki tarafı \(14\) ile çarpalım — bu çarpanı seçmemizin nedeni \(3 \cdot 14 = 42 \equiv 1 \pmod{41}\) olmasıdır:
\[14 \cdot (-1) \equiv 42 \cdot 35! \equiv 35! \pmod{41}\]
Yani
\[35! \equiv -14 \pmod{41}\]
Aradığımız değer ise \(14 \cdot 35!\)’dir:
\[14 \cdot 35! \equiv 14 \cdot (-14) = -196 \pmod{41}\]
\(-196 + 5 \cdot 41 = -196 + 205 = 9\) olduğundan
\[14 \cdot 35! \equiv 9 \pmod{41}\]
Aranan kalan \(9\)’dur.
\(\blacksquare\)
Örnek 19.5 (İkiz Asallar İçin Bir Kongrüans) \(p\) ile \(p+2\) sayılarının ikisi de asal olsun (böyle çiftlere ikiz asallar denir). Bu durumda
\[4\big( (p-1)! + 1 \big) + p \equiv 0 \pmod{p(p+2)}\]
olduğunu gösteriniz.
Çözüm
\(q := p + 2\) yazalım. İfadeyi \(N := 4\big( (p-1)! + 1 \big) + p\) ile gösterelim. \(p \mid N\) ve \(q \mid N\) olduğunu ayrı ayrı göstereceğiz.
Modülo \(p\). \(p\) asal olduğundan Teorem 19.1 gereği \((p-1)! \equiv -1 \pmod p\)’dir. Buradan
\[N = 4\big( (p-1)! + 1 \big) + p \equiv 4(-1 + 1) + 0 = 0 \pmod p\]
Modülo \(q = p+2\). \(q\) asal olduğundan Teorem 19.1 gereği
\[(q-1)! = (p+1)! \equiv -1 \pmod q\]
\((p+1)!\) ifadesini \((p-1)!\) cinsinden yazalım:
\[(p+1)! = (p+1) \cdot p \cdot (p-1)!\]
Baştaki iki çarpanı modülo \(q = p+2\) negatif temsilcilerle yazalım:
\[p + 1 \equiv -1 \pmod q, \qquad p \equiv -2 \pmod q\]
O hâlde
\[-1 \equiv (p+1)! \equiv (-1)(-2)(p-1)! = 2 \, (p-1)! \pmod q\]
Her iki tarafı \(2\) ile çarparsak
\[4 \, (p-1)! \equiv -2 \pmod q\]
Şimdi \(N\) ifadesini hesaplayalım:
\[N = 4\,(p-1)! + 4 + p \equiv -2 + 4 + p = p + 2 = q \equiv 0 \pmod q\]
Birleştirme. \(p \mid N\) ve \(q \mid N\)’dir. \(p\) ile \(q = p+2\) farklı asallar olduğundan Sonuç 9.1 gereği \(\gcd(p, q) = 1\)’dir; Teorem 5.2 gereği
\[p(p+2) \ \mid \ N\]
(Sağlama: \(p = 3\), \(q = 5\) için \(N = 4(2! + 1) + 3 = 4 \cdot 3 + 3 = 15\) ve \(p(p+2) = 15\) ✓)
\(\blacksquare\)
19.6 Çalışma Problemleri
Alıştırma 19.1 (Faktöriyel Kalanları) Aşağıdaki kalanları bulunuz.
a) \(15!\) sayısının \(17\) ile bölümünden kalan.
b) \((p-2)!\) sayısının \(p\) ile bölümünden kalan (\(p\) asal).
c) \(2 \cdot (26!)\) sayısının \(29\) ile bölümünden kalan.
Alıştırma 19.2 (Wilson Teoreminin Uygulamaları) a) \(p\) tek bir asal sayı olmak üzere
\[\left( \frac{p-1}{2} \right)! \cdot \left( \frac{p-1}{2} \right)! \equiv (-1)^{\frac{p+1}{2}} \pmod p\]
olduğunu gösteriniz.
İpucu: \((p-1)!\) çarpımındaki \(\frac{p+1}{2}, \dots, p-1\) çarpanlarını \(-1\) ile \(-\frac{p-1}{2}\) arasındaki temsilcilerle yazınız.
b) \(p\) asal ve \(0 \leq k \leq p-1\) olmak üzere
\[k! \, (p-1-k)! \equiv (-1)^{k+1} \pmod p\]
olduğunu gösteriniz.
Alıştırma 19.3 (Bileşik Sayılarda Faktöriyel) a) \((n-1)! \equiv 0 \pmod n\) eşitliğinin sağlanmadığı bütün \(1 < n\) tam sayılarını belirleyiniz.
b) \(n \geq 6\) bileşik ise \(n \mid (n-1)!\) olduğunu, üstelik \(n^{2} \mid (n-1)!\) olduğunu gösteriniz.
İpucu (b): Teorem 19.3’in ispatındaki iki durumu \(n \geq 6\) koşulu altında yeniden inceleyiniz.
Alıştırma 19.4 (İki Teoremi Birlikte Kullanma) \(p\) bir asal sayı olsun. Aşağıdakileri ispatlayınız.
a) \(p \equiv 1 \pmod 4\) ise \(x^{2} \equiv -1 \pmod p\) denkleminin bir çözümü vardır.
İpucu: \(x = \left( \frac{p-1}{2} \right)!\) alınız ve Alıştırma 19.2 (a)’yı kullanınız.
b) \(p \equiv 3 \pmod 4\) ise \(x^{2} \equiv -1 \pmod p\) denkleminin hiç çözümü yoktur.
İpucu: Böyle bir \(x\) olsaydı \(x^{p-1} = \left( x^{2} \right)^{\frac{p-1}{2}}\) değerini hesaplayıp Teorem 18.1 ile çelişkiye varınız.