6 Kuadratik Resiprosite (Karesel Karşılıklılık) Teoremi
Şu ana kadar Legendre sembolünün özelliklerini, Euler kriterini ve Gauss lemmasını kullanarak sayıların karesel karakterlerini belirledik. Ancak asallar büyüdükçe (örneğin \(\left(\frac{7}{61}\right)\) gibi ifadelerde) üs alma işlemleri veya Gauss saymaları bile hantallaşır.
Gauss’un “altın teorem” adını verdiği kuadratik resiprosite teoremi, iki farklı tek asal sayının birbirine göre karesel durumlarının doğrudan bağlantılı olduğunu kanıtlar. Bu teorem, büyük modüller altındaki denklemlerin çözülebilirliğini çok kısa sürede tespit etmemizi sağlar.
6.1 1. Teorem ve Kafes (Lattice) İspatı
Teorem 6.1 (Kuadratik Resiprosite Teoremi) \(p\) ve \(q\) birbirinden farklı iki tek asal sayı olsun. Bu durumda
\[\left( \frac{p}{q} \right) \cdot \left( \frac{q}{p} \right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\]
eşitliği sağlanır.
Bu ispat, kartezyen koordinat sistemindeki tam sayı koordinatlı noktaların (kafes noktalarının) sayılması mantığına dayanır.
İlk olarak, birinci bölgede yer alan ve sınırları belirli bir \(K\) dikdörtgensel tam sayı kümesi tanımlayalım:
\[K = \left\{ (x, y) \;:\; 1 \leq x \leq \frac{p-1}{2}, \quad 1 \leq y \leq \frac{q-1}{2}, \quad x, y \in \mathbb{Z} \right\}\]
Bu kümenin eleman sayısı, \(x\) ve \(y\)’nin alabileceği değerlerin çarpımı kadardır:
\[s(K) = \frac{p-1}{2} \cdot \frac{q-1}{2}\]
Şimdi \(K\) kümesini \(qx = py\) doğrusu yardımıyla iki alt kümeye ayıralım:
- Doğrunun bir tarafında kalanlar: \(K_1 = \{(x, y) \in K : qx > py\}\)
- Diğer tarafında kalanlar: \(K_2 = \{(x, y) \in K : qx < py\}\)
Kritik ayrıntı. \(K\) kümesindeki hiçbir nokta tam olarak \(qx = py\) doğrusunun üzerinde olamaz. Çünkü \(\gcd(p, q) = 1\) olduğundan bu eşitliğin sağlanması için \(p \mid x\) ve \(q \mid y\) olması gerekirdi; oysa kümemizin sınırlarında \(x \leq \tfrac{p-1}{2} < p\) ve \(y \leq \tfrac{q-1}{2} < q\)’dur.
Dolayısıyla \(K_1 \cap K_2 = \emptyset\) ve \(K_1 \cup K_2 = K\)’dır:
\[s(K_1) + s(K_2) = \frac{p-1}{2} \cdot \frac{q-1}{2}\]
Şimdi \(K_1\) kümesinin eleman sayısını sütun sütun bulalım:
\[K_1 = \bigcup_{x=1}^{(p-1)/2} \left\{ (x, y) \;:\; 1 \leq y < \frac{qx}{p}, \; y \in \mathbb{Z} \right\}\]
Bu birleşime giren kümeler ikişer ikişer ayrıktır. Belirli bir \(x\) değeri için \(1 \leq y < \tfrac{qx}{p}\) şartını sağlayan \(y\) tam sayılarının adedi, \(\left\lfloor \tfrac{qx}{p} \right\rfloor\) sayısına eşittir. O hâlde:
\[s(K_1) = \sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor\]
Tamamen simetrik bir düşünceyle \(K_2\) kümesinin eleman sayısı da \(y\) ekseni üzerinden toplanarak bulunur:
\[s(K_2) = \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor\]
Bu değerleri toplam denkleminde yerine yazalım:
\[\sum_{x=1}^{(p-1)/2} \left\lfloor \frac{qx}{p} \right\rfloor + \sum_{y=1}^{(q-1)/2} \left\lfloor \frac{py}{q} \right\rfloor = \frac{p-1}{2} \cdot \frac{q-1}{2}\]
Eşitliğin her iki tarafını \((-1)\)’in üssü olarak yazalım:
\[(-1)^{\sum \lfloor qx/p \rfloor} \cdot (-1)^{\sum \lfloor py/q \rfloor} = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\]
Bir önceki bölümde Gauss lemması üzerinden kanıtladığımız \(t\)-toplam formülü gereği
\[\left( \frac{q}{p} \right) = (-1)^{\sum \lfloor qx/p \rfloor}, \qquad \left( \frac{p}{q} \right) = (-1)^{\sum \lfloor py/q \rfloor}\]
olduğunu biliyoruz. Bu değerleri yerine yazdığımızda ispat tamamlanır.
\(\blacksquare\)
Kuadratik resiprosite teoremi aslında şunu söyler: \(\left( \frac{p}{q} \right)\) sembolünü hesaplamak zorsa, onu ters çevirip \(\left( \frac{q}{p} \right)\) sembolünü hesaplayabilirsiniz.
- Eğer \(p\) ve \(q\) asallarından en az biri \(4k+1\) formundaysa, sembol işaret değiştirmeden aynen ters çevrilir: \[\left( \frac{p}{q} \right) = \left( \frac{q}{p} \right)\]
- Eğer \(p\) ve \(q\) asallarının her ikisi de \(4k+3\) formundaysa, sembol ters çevrildiğinde eksi işareti alır: \[\left( \frac{p}{q} \right) = -\left( \frac{q}{p} \right)\]
Kuadratik resiprosite teoreminde hesapladığımız şey iki sembolün çarpımıdır. Peki bu çarpımdan asıl aradığımız sembolü tek başına nasıl çekiyoruz?
Legendre sembolleri yalnızca \(1\) veya \(-1\) değerini alabilir; dolayısıyla iki senaryo vardır.
1. senaryo (çarpım \(1\) ise). İki sayı ya \((1 \cdot 1)\) ya da \(((-1) \cdot (-1))\) olmak zorundadır. Her iki durumda da semboller birbirine eşittir: \[\left( \frac{p}{q} \right) = \left( \frac{q}{p} \right)\]
2. senaryo (çarpım \(-1\) ise). Sayılardan biri \(1\) iken diğeri zorunlu olarak \(-1\)’dir; yani semboller birbirinin zıt işaretlisidir: \[\left( \frac{p}{q} \right) = -\left( \frac{q}{p} \right)\]
İşte bu basit işaret mantığı sayesinde, üstteki büyük sayıyı aşağıya atıp modüler indirgemeyle küçültme işlemine devam edebiliriz.
6.2 2. Çözümlü Uygulamalar
Resiprosite teoreminin gücü, çok büyük sayılar içeren kongrüansları basit modüler indirgemeler ve sembolü sürekli ters çevirme (“takla attırma”) yoluyla çok küçük sayılara düşürmesinde yatar.
Örnek 6.1 \(x^2 \equiv -42 \pmod{61}\) kongrüansının çözülebilir olup olmadığını araştırınız.
Problemi çözmek için \(\left( \frac{-42}{61} \right)\) değerini hesaplamalıyız (\(61\) bir asal sayıdır). İlk adım olarak \(-42\) sayısını çarpanlarına ayırıp Legendre’nin çarpımsallık kuralını uygulayalım:
\[\left( \frac{-42}{61} \right) = \left( \frac{-1}{61} \right) \cdot \left( \frac{2}{61} \right) \cdot \left( \frac{3}{61} \right) \cdot \left( \frac{7}{61} \right)\]
1. parça — \(\left( \frac{-1}{61} \right)\): \[\left( \frac{-1}{61} \right) = (-1)^{\frac{61-1}{2}} = (-1)^{30} = 1\]
2. parça — \(\left( \frac{2}{61} \right)\): \[\left( \frac{2}{61} \right) = (-1)^{\frac{61^2-1}{8}} = (-1)^{465} = -1\]
3. parça — \(\left( \frac{3}{61} \right)\): Her iki sayı da tek asaldır; resiprosite formülünü uygulayalım. \[\left( \frac{3}{61} \right) \cdot \left( \frac{61}{3} \right) = (-1)^{\frac{3-1}{2} \cdot \frac{61-1}{2}} = (-1)^{1 \cdot 30} = 1\]
Çarpımları \(1\) olduğu için semboller eşittir. Şimdi \(61\)’i modülo \(3\)’te indirgeyelim (\(61 \equiv 1 \pmod 3\)):
\[\left( \frac{3}{61} \right) = \left( \frac{61}{3} \right) = \left( \frac{1}{3} \right) = 1\]
4. parça — \(\left( \frac{7}{61} \right)\): \[\left( \frac{7}{61} \right) \cdot \left( \frac{61}{7} \right) = (-1)^{\frac{7-1}{2} \cdot \frac{61-1}{2}} = (-1)^{3 \cdot 30} = (-1)^{90} = 1\]
Yine çarpımları \(1\) çıktığından sembol işaretsiz çevrilir. Modülo \(7\)’ye indirgeyelim (\(61 \equiv 5 \pmod 7\)):
\[\left( \frac{7}{61} \right) = \left( \frac{61}{7} \right) = \left( \frac{5}{7} \right)\]
Karşımıza yine iki tek asal çıktı; teoremi bir kez daha uygulayıp “takla” attıralım:
\[\left( \frac{5}{7} \right) \cdot \left( \frac{7}{5} \right) = (-1)^{\frac{5-1}{2} \cdot \frac{7-1}{2}} = (-1)^{2 \cdot 3} = 1 \implies \left( \frac{5}{7} \right) = \left( \frac{7}{5} \right)\]
\(7\)’yi modülo \(5\)’e indirgeyelim (\(7 \equiv 2 \pmod 5\)):
\[\left( \frac{7}{5} \right) = \left( \frac{2}{5} \right) = (-1)^{\frac{5^2-1}{8}} = (-1)^3 = -1\]
Zincirleme geriye dönersek:
\[\left( \frac{7}{61} \right) = \left( \frac{61}{7} \right) = \left( \frac{5}{7} \right) = \left( \frac{7}{5} \right) = \left( \frac{2}{5} \right) = -1\]
Sonuçların birleştirilmesi.
\[\left( \frac{-42}{61} \right) = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1\]
Genel sonuç \(1\) çıktığı için \(-42\) sayısı modülo \(61\)’e göre bir kuadratik rezidüdür ve \(x^2 \equiv -42 \pmod{61}\) kongrüansı kesin olarak çözülebilirdir.
\(\blacksquare\)
Örnek 6.2 Hangi \(p\) tek asal sayıları için \(3\), modülo \(p\)’ye göre bir kuadratik rezidüdür? Yani \(x^2 \equiv 3 \pmod p\) kongrüansı hangi asallarda çözülebilirdir?
Soru bizden \(\left( \frac{3}{p} \right) = 1\) koşulunu sağlayan tüm \(p\) tek asallarını bulmamızı istiyor. Kuadratik resiprosite teoreminden faydalanalım:
\[\left( \frac{3}{p} \right) \cdot \left( \frac{p}{3} \right) = (-1)^{\frac{3-1}{2} \cdot \frac{p-1}{2}} = (-1)^{\frac{p-1}{2}}\]
Denklemi düzenlersek:
\[\left( \frac{3}{p} \right) = \left( \frac{p}{3} \right) \cdot (-1)^{\frac{p-1}{2}}\]
Sonucun \(1\) çıkması için iki çarpanın da \(1\) ya da ikisinin de \(-1\) olması gerekir; böylece iki durum ortaya çıkar.
Durum 1: \(\left( \frac{p}{3} \right) = 1\) ve \((-1)^{\frac{p-1}{2}} = 1\)
- \((-1)^{\frac{p-1}{2}} = 1 \implies \tfrac{p-1}{2}\) çift \(\implies p \equiv 1 \pmod 4\)
- \(\left( \frac{p}{3} \right) = 1 \implies p\), mod \(3\)’e göre bir KR’dir. Modülo \(3\)’te kareler yalnızca \(\{1\}\) olduğundan \(\implies p \equiv 1 \pmod 3\)
Durum 2: \(\left( \frac{p}{3} \right) = -1\) ve \((-1)^{\frac{p-1}{2}} = -1\)
- \((-1)^{\frac{p-1}{2}} = -1 \implies \tfrac{p-1}{2}\) tek \(\implies p \equiv 3 \pmod 4\)
- \(\left( \frac{p}{3} \right) = -1 \implies p\), mod \(3\)’e göre bir KNR’dir \(\implies p \equiv 2 \pmod 3\)
Aradığımız asallar şu iki kongrüans sisteminden birini sağlamalıdır:
- \(p \equiv 1 \pmod 3\) ve \(p \equiv 1 \pmod 4\)
- \(p \equiv 2 \pmod 3\) ve \(p \equiv 3 \pmod 4\)
Şimdi Çin kalan teoreminden yararlanarak bu sistemleri çözelim.
1. sistemin çözümü. \(p \equiv 1 \pmod 3 \implies p = 1 + 3y\). Bunu ikinci denklemde yerine koyalım:
\[1 + 3y \equiv 1 \pmod 4 \implies 3y \equiv 0 \pmod 4 \implies y \equiv 0 \pmod 4 \implies y = 4z\]
Başa dönersek \(p = 1 + 12z\), yani \(p \equiv 1 \pmod{12}\).
2. sistemin çözümü. \(p \equiv 2 \pmod 3 \implies p = 2 + 3y\). İkinci denklemde yerine koyalım:
\[2 + 3y \equiv 3 \pmod 4 \implies 3y \equiv 1 \pmod 4\]
Modüler bölme için sağ tarafa \(8\) ekleyelim (\(9\), \(3\)’e tam bölünür):
\[3y \equiv 9 \pmod 4 \implies y \equiv 3 \pmod 4 \implies y = 3 + 4z\]
Başa dönersek \(p = 2 + 3(3 + 4z) = 11 + 12z\), yani \(p \equiv 11 \pmod{12}\).
Genel sonuç. \(\left( \frac{3}{p} \right) = 1\) olması için \(p\) tek asalının modülo \(12\)’ye göre \(1\) veya \(11\) kalanını vermesi gerekir; kısaca \(p \equiv \pm 1 \pmod{12}\).
Kontrol: Bir önceki örnekte \(\left( \frac{3}{61} \right) = 1\) bulmuştuk. Gerçekten de \(61 = 5 \cdot 12 + 1 \equiv 1 \pmod{12}\)’dir.
\(\blacksquare\)