Wilson Teoremi: Faktöriyel, Asal Sayıların Parmak İzi

"Bir sayı asal mı?" sorusunun zarif bir cevabı

Sıradan bir sayı için "asal mı değil mi?" diye sormanın en bilinen yolu deneme bölmesi. Ama bu çirkin — $n$'in karekökü kadar denemek gerekir. Daha zarif bir test arar mıydınız?

1770'te İngiliz matematikçi John Wilson (henüz öğrenci) çok güzel bir formül ileri sürdü:

$p > 1$ tam sayısı asaldır ⟺ $(p-1)! + 1$, $p$ ile tam bölünür.

Modüler aritmetik dilinde: $p$ asal ⟺ $(p-1)! \equiv -1 \pmod{p}$.

Wilson kanıt yapamadı; Lagrange 1771'de tam ispatladı. Adı yine yanlış kişiye yapıştı — ama bu sefer adaletli bir biçimde: Wilson'un tahmini bu güzel sonucu görmekti, Lagrange'ın katkısı ise ispat.

Küçük örneklerle test

• $p = 2$: $(2-1)! = 1$, $1 \equiv -1 \pmod{2}$ ✓
• $p = 3$: $2! = 2 \equiv -1 \pmod{3}$ ✓
• $p = 5$: $4! = 24 \equiv -1 \pmod{5}$ ✓ (24 = 5·5 − 1)
• $p = 7$: $6! = 720 \equiv -1 \pmod{7}$ ✓ (720 = 7·103 − 1)

Şimdi bileşik bir sayı için test edelim:

• $n = 4$: $3! = 6 \equiv 2 \pmod{4}$. ($-1 \neq 2$) ✓ (asal değil olduğu için $-1$'e eşit olmamalı)
• $n = 6$: $5! = 120 \equiv 0 \pmod{6}$. ✓
• $n = 8$: $7! = 5040 \equiv 0 \pmod{8}$. ✓
• $n = 9$: $8! = 40320 \equiv 0 \pmod{9}$. ✓

İlginç bir gözlem: $n > 4$ bileşik için $(n-1)! \equiv 0 \pmod{n}$. Çünkü $n = ab$ (her ikisi $< n$) yazılınca hem $a$ hem $b$, $(n-1)!$ çarpımında yer alır. Yani test sadece $n = 4$ istisnası dışında, asal olmayanlar için $0 \bmod n$ verir.

Wilson'un sezgisel anlamı

Modüler aritmetik dilinde Wilson teoremi şunu söyler: $\mathbb{Z}/p\mathbb{Z}$ cisminin sıfırdan farklı tüm elemanlarının çarpımı $-1$'e eşittir.

$\prod_{k=1}^{p-1} k = (p-1)! \equiv -1 \pmod{p}$

Niçin? Çünkü her elemanın modüler tersi vardır (cisim olduğu için), ve eleman ile tersi birbirini götürür:

$1 \cdot 2 \cdot 3 \cdots (p-1) = ?$

Çoğu $k$ kendi tersine eşit değildir ($k \neq k^{-1}$), o yüzden eşleştirilebilir: $k \cdot k^{-1} = 1$. Geriye sadece kendi tersine eşit elemanlar kalır. $k = k^{-1}$ koşulu $k^2 = 1 \pmod p$, yani $k = 1$ veya $k = p - 1 = -1$.

Bu iki eleman dışındakiler çift çift götürür. Geriye:
$1 \cdot (p-1) = -1 \pmod{p}$

İşte ispat. Üç satırda. Bu kanıtın güzelliği Wilson teoremini ünlü yapan şeydir.

Asal testi olarak — neden kullanılmaz?

Wilson teoremi teorik olarak mükemmel bir asallık testi: tam olarak asalları karakterize eder, hata yapmaz. Ama pratik olarak korkunç yavaş:

• $p = 1000003$ (asal) için $1000002!$ hesaplamak gerekir. Bu yaklaşık $5.5 \times 10^{5\,565\,704}$ basamaklı bir sayı. Hafıza yetmez.
• Modüler hesap yapsanız bile, $p - 2$ tane çarpma gerekir → $O(p)$ adım.
• Deneme bölmesi $O(\sqrt{p})$.
• Modern probabilistik testler (Miller-Rabin) $O((\log p)^k)$.

Wilson teoremi şıklık abidesi ama pratik tornavida değil. Matematik tarihinde böyle pek çok teorem vardır: bilgi açısından harika, hesap açısından berbat.

Genelleştirmeler

Gauss'un Wilson genelleştirmesi

Hangi modüler aritmetiklerde $(n-1)$ alt grubu $-1$'e eşittir? Gauss cevapladı:

$(n-1)!_{n\text{-asal}} \equiv -1 \pmod{n}$ ⟺ $n = 1, 2, 4, p^k, 2p^k$ ($p$ tek asal).

Burada $(n-1)!_{n\text{-asal}}$ = $n$ ile aralarında asal olan, $n$'den küçük pozitif sayıların çarpımı. Yani Wilson teoremi sadece asalları değil, belirli bir grup yapısına sahip modülleri ayırt eder.

Wilson-Lagrange polinom ispatı

Bir başka güzel ispat: $f(x) = (x-1)(x-2)\cdots(x-(p-1)) - (x^{p-1} - 1)$ polinomu derecesi $p-1$'den küçüktür. Fermat'nın küçük teoremi der ki $x^{p-1} \equiv 1$ her sıfırdan farklı $x$ için. Yani $f(x) \equiv 0$, $p-1$ tane kök var. Bir polinomun derecesinden fazla kökü olamaz; o halde $f$ özdeş olarak sıfırdır. $x = 0$ koyun:

$(-1)(-2)\cdots(-(p-1)) - (-1) = 0 \Rightarrow (-1)^{p-1}(p-1)! = -1 \pmod{p}$

$p$ tek asal için $(-1)^{p-1} = 1$, sonuç: $(p-1)! \equiv -1$. $p = 2$ trivial.

Bu ispat zarif çünkü Fermat'nın küçük teoreminin duali gibi görünür: Fermat üs hakkında, Wilson çarpım hakkında.

Wilson asalları

$p$ asal ve $(p-1)! \equiv -1 \pmod{p^2}$ ise $p$'ye Wilson asalı denir. Bilinen sadece 3 tane: $5, 13, 563$. Başka var mı? $2 \times 10^{13}$'e kadar arandı, bulunamadı. Sonsuz var mı? Açık.

Matematik bu tür "yakaladığım üçü dışında hiç bulamadım" sorularıyla dolu.

John Wilson kim?

John Wilson (1741-1793) İngiliz öğrenci. Cambridge Trinity Hall'da matematik okudu. Kendisi pek de matematikçi değildi — hayatının çoğunu avukat ve hakim olarak geçirdi. Teoremi öğrenciliğindeyken hocası Edward Waring'e söyledi (1770). Waring kitabında "Wilson teoremi" diye yayımladı.

Tarihsel gerçek: bu teorem aslında Ibn al-Haytham (~1000 MS, Mısır) tarafından çok önce bilinen bir gözlem olabilir. Ortaçağ İslam matematik literatüründe izleri var. Ama Avrupa'da Wilson adıyla geçti.

İlginç bir not: Lagrange, ispatından sonra Wilson'a krediyi içtenlikle verdi. Bir önceki yazımızda gördüğümüz Gauss-Legendre tartışmalarının aksine, Wilson-Lagrange ilişkisi medeniydi.

Mirası

Wilson teoremi pratikte kullanılmaz, ama:

• Sayı teorisi giriş derslerinde kullanılan standart örnek: faktöriyel, modüler aritmetik, eleman-ters eşleştirme.
• Olimpiyat matematiğinde sık çıkan klasik.
• Bilgisayar biliminde modüler hesaplamanın algoritmik karşıtlığını öğretir: zariflik vs verimlilik.
• Soyut cebirde "bir cismin tüm sıfır olmayan elemanlarının çarpımı" kavramının somut bir örneği.

Wilson teoremi bir parmak izidir — asallar gerçekten "her bir asal, $(p-1)!$ çarpımında eşsiz bir iz bırakır" şeklinde karakterize edilir.

Eğer matematik tarihinden bir teorem öğrenmek istiyorsanız, Wilson teoremi mükemmel başlangıç. Cebirsel sezgilerinizi keskinleştirir, ispat zarafetini öğretir, ve asal sayılara karşı daha derin bir saygıyla çıkarsınız.