5 Gauss Lemması ve 2’nin Karesel Karakteri

Legendre sembolünün değerini hesaplamak için her zaman Euler kriterine başvurmak zorunda değiliz. Carl Friedrich Gauss, modüler sistemin yalnızca yarısını —$1$’den $\tfrac{p-1}{2}$’ye kadar olan kısmı— inceleyerek sembolün değerini veren son derece zarif bir sayma yöntemi ispatlamıştır.

5.1 1. Gauss Lemması

Teorem 5.1 (Gauss Lemması) $p$ bir tek asal sayı, $a$ bir tam sayı ve $\gcd(a, p) = 1$ olsun.

$a,\ 2a,\ 3a,\ \dots,\ \left(\tfrac{p-1}{2}\right)a$ tam sayılarını $p$ ile bölüp kalanları bulalım. Eğer $\tfrac{p}{2}$’den büyük olan kalanların sayısı $n$ ise:

\[\left( \frac{a}{p} \right) = (-1)^n\]

İspat

$a, 2a, \dots, \tfrac{p-1}{2}a$ tam sayılarını $p$ ile bölüp kalanları bulalım ve bu kalanları büyüklüklerine göre ikiye ayıralım:

$\tfrac{p}{2}$’den büyük olan kalanların sayısı $n$ olsun; bunları $r_1, \dots, r_n$ ile gösterelim.
$\tfrac{p}{2}$’den küçük olan kalanların sayısı $k$ olsun; bunları $s_1, \dots, s_k$ ile gösterelim.

Başlangıçtaki sayılar $\gcd(a, p) = 1$ olduğundan modülo $p$’de birbirine denk olamaz; dolayısıyla elde edilen tüm kalanlar birbirinden farklıdır ve

\[n + k = \frac{p-1}{2}\]

Kalanların sınırları şöyledir:

\[0 < s_1, \dots, s_k \leq \frac{p-1}{2} < \frac{p}{2}\] \[\frac{p}{2} < \frac{p+1}{2} \leq r_1, \dots, r_n < p\]

Şimdi büyük kalanları modül değerinden çıkararak yeni bir küme oluşturalım: $p - r_1, \dots, p - r_n$. Bu sayılar da birbirinden farklıdır ve $0 < p - r_i < \tfrac{p}{2}$ aralığına düşerler.

Kritik soru: Herhangi bir $p - r_i$ değeri, küçük kalanlardan bir $s_j$ değerine eşit olabilir mi?

Aksini varsayalım ve $p - r_i = s_j$ olsun. Modüler aritmetiğe geçersek:

\[p - r_i \equiv s_j \pmod p \implies r_i + s_j \equiv 0 \pmod p\]

Tanımımız gereği $r_i \equiv t_1 a$ ve $s_j \equiv t_2 a \pmod p$ olacak şekilde $1 \leq t_1, t_2 \leq \tfrac{p-1}{2}$ tam sayıları vardır:

\[(t_1 + t_2)a \equiv 0 \pmod p\]

$\gcd(a, p) = 1$ olduğundan sadeleştirme yapabiliriz:

\[t_1 + t_2 \equiv 0 \pmod p\]

Ancak $1 \leq t_1, t_2 \leq \tfrac{p-1}{2}$ olduğundan toplamları en fazla $p - 1$ olabilir. $0 < t_1 + t_2 < p$ iken bu toplam modülo $p$’de sıfıra denk olamaz — çelişki.

Demek ki $\{p-r_1, \dots, p-r_n\}$ ile $\{s_1, \dots, s_k\}$ kümelerinin ortak elemanı yoktur. Her iki kümenin elemanları toplam $\tfrac{p-1}{2}$ adettir ve hepsi $1$ ile $\tfrac{p-1}{2}$ arasındadır. O hâlde birleşimleri tam olarak şu kümedir:

\[\{p-r_1, \dots, p-r_n\} \cup \{s_1, \dots, s_k\} = \left\{1, 2, \dots, \frac{p-1}{2}\right\}\]

Tüm elemanları çarpalım:

\[(p-r_1)\cdots(p-r_n) \cdot s_1 \cdots s_k = \left(\frac{p-1}{2}\right)!\]

Bu eşitliğin modülo $p$’deki durumuna bakalım ($p \equiv 0$ olduğundan $p - r_i \equiv -r_i$):

\[(-1)^n \big(r_1 \cdots r_n \cdot s_1 \cdots s_k\big) \equiv \left(\frac{p-1}{2}\right)! \pmod p\]

$r_i$ ve $s_j$’lerin orijinal hâlleri $1a, 2a, \dots, \tfrac{p-1}{2}a$’nın kalanlarıydı; yerlerine koyarsak:

\[(-1)^n \cdot a^{(p-1)/2} \cdot \left(1 \cdot 2 \cdots \frac{p-1}{2}\right) \equiv \left(\frac{p-1}{2}\right)! \pmod p\]

\[(-1)^n \cdot a^{(p-1)/2} \cdot \left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)! \pmod p\]

Faktöriyelli ifade $p$ ile aralarında asal olduğu için her iki taraftan sadeleştirebiliriz:

\[(-1)^n \cdot a^{(p-1)/2} \equiv 1 \pmod p\]

Her iki tarafı $(-1)^n$ ile çarparsak (çünkü $(-1)^n \cdot (-1)^n = 1$):

\[a^{(p-1)/2} \equiv (-1)^n \pmod p\]

Euler kriterinden $\left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod p$ olduğunu biliyoruz; öyleyse

\[\left( \frac{a}{p} \right) \equiv (-1)^n \pmod p\]

Her iki taraf da yalnızca $\pm 1$ olabileceği ve $p > 2$ olduğu için denklik doğrudan eşitliğe dönüşür.

$\blacksquare$

Gauss lemması, tek başına bir hesaplama yönteminden ziyade arkasından gelecek büyük teoremleri kanıtlamak için bir köprüdür. Aşağıdaki teorem, Gauss lemmasını kullanarak $a$’nın ve özel olarak $2$’nin karesel durumunu çok daha pratik bir formüle bağlar.

5.2 2. Legendre Sembolü İçin Genel Formül ve 2’nin Karesel Karakteri

Teorem 5.2 (Karesel Karakterlerin Hesabı) $p$ bir tek asal sayı ve $\gcd(a, 2p) = 1$ olsun (yani $a$ tek bir tam sayı ve $p$ ile aralarında asal). Bu durumda:

$t = \displaystyle\sum_{j=1}^{(p-1)/2} \left\lfloor \frac{ja}{p} \right\rfloor$ olmak üzere $\left( \frac{a}{p} \right) = (-1)^t$’dir.
$\left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8}$’dir.

Burada $\lfloor x \rfloor$ sembolü $x$’in tam kısmını ifade eder.

İspat

1) Birinci kısmın ispatı.

$j \in \{1, \dots, \tfrac{p-1}{2}\}$ olmak üzere $ja$ sayılarına $p$ modülünde bölme algoritmasını uygulayalım:

\[ja = q_j \cdot p + \ell_j, \qquad 0 < \ell_j < p\]

Burada bölüm $q_j = \left\lfloor \tfrac{ja}{p} \right\rfloor$ şeklinde ifade edilebilir. Bu eşitliği $j = 1$’den $\tfrac{p-1}{2}$’ye kadar toplayalım:

\[a \sum j = p \sum \left\lfloor \frac{ja}{p} \right\rfloor + \sum \ell_j\]

Kalanlar dizisi $\ell_j$, Gauss lemması ispatındaki $r_i$ (büyük kalanlar) ve $s_j$ (küçük kalanlar) dizilerinin ta kendisidir:

\[a \sum j = p \sum \left\lfloor \frac{ja}{p} \right\rfloor + \sum r_j + \sum s_j \tag{$*$}\]

Öte yandan Gauss lemması ispatında $1$’den $\tfrac{p-1}{2}$’ye kadar olan sayıların toplamını iki parçaya ayırmıştık:

\[\sum j = \sum_{j=1}^n (p - r_j) + \sum_{j=1}^k s_j = np - \sum r_j + \sum s_j \tag{$**$}\]

$(*)$ denkleminden $(**)$ denklemini taraf tarafa çıkaralım; $\sum s_j$ terimleri birbirini götürür:

\[(a-1)\sum j = p \sum \left\lfloor \frac{ja}{p} \right\rfloor - np + 2\sum r_j\]

Ardışık sayıların toplam formülünden $\sum j = \dfrac{\frac{p-1}{2}\left(\frac{p-1}{2}+1\right)}{2} = \dfrac{p^2-1}{8}$’dir. Yerine yazarsak:

\[(a-1)\frac{p^2-1}{8} = p\left( \sum \left\lfloor \frac{ja}{p} \right\rfloor - n \right) + 2\sum r_j \tag{$*{*}*$}\]

Bu denklemi modülo 2’de inceleyelim. $p$ tek asal olduğundan $p \equiv 1 \pmod 2$; $a$ tek kabul edildiği için $(a-1)$ çifttir. Denklem şu hâle gelir:

\[0 \equiv \sum \left\lfloor \frac{ja}{p} \right\rfloor - n \pmod 2 \implies n \equiv \sum \left\lfloor \frac{ja}{p} \right\rfloor \pmod 2\]

$t = \sum \left\lfloor \tfrac{ja}{p} \right\rfloor$ dersek $n \equiv t \pmod 2$ bulunur. Gauss lemması gereği $\left( \frac{a}{p} \right) = (-1)^n$ olduğundan ve üslerin mod $2$’deki denkliği işareti değiştirmeyeceğinden:

\[\left( \frac{a}{p} \right) = (-1)^t\]

2) İkinci kısmın ispatı — 2’nin karesel karakteri.

$(*{*}*)$ denkleminde $a = 2$ alalım. Önce toplamı inceleyelim:

\[t = \sum_{j=1}^{(p-1)/2} \left\lfloor \frac{2j}{p} \right\rfloor\]

$j$’nin alabileceği en büyük değer $\tfrac{p-1}{2}$ olduğundan $2j$’nin en büyük değeri $p-1$’dir. $2j < p$ olduğu için $\tfrac{2j}{p}$ kesri daima $1$’den küçüktür ve tam kısmı sıfırdır:

\[\left\lfloor \frac{2j}{p} \right\rfloor = 0 \implies t = 0\]

Şimdi $(*{*}*)$ denkleminde $a = 2$ ve toplam yerine $0$ yazalım:

\[(2-1)\frac{p^2-1}{8} = p(0 - n) + 2\sum r_j \implies \frac{p^2-1}{8} = -pn + 2\sum r_j\]

Bu denklemi yine modülo 2’de okuyalım; $p$ tek olduğundan $-p \equiv 1 \pmod 2$:

\[\frac{p^2-1}{8} \equiv n \pmod 2\]

Gauss lemmasına dönersek $\left( \frac{2}{p} \right) = (-1)^n$ olduğunu biliyoruz. Mod $2$’deki denklik üslerde işareti etkilemediğinden:

\[\left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8}\]

$\blacksquare$

5.3 3. Çözümlü Uygulamalar

İspatladığımız bu soyut teoremlerin, modüler aritmetikteki sayıların karesel karakterini bulmak için nasıl güçlü bir araca dönüştüğünü aşağıdaki örneklerle inceleyelim.

Örnek 5.1 $x^2 \equiv 22 \pmod{41}$ kongrüansının çözümünün olup olmadığını Gauss lemması ve Euler kriteri olmak üzere iki farklı yolla inceleyiniz.

💡 Çözümü göster / gizle

Burada $p = 41$ (tek asal) ve $a = 22$’dir; $\gcd(22, 41) = 1$ sağlanmaktadır.

1. yol — Gauss lemması.

$\tfrac{p-1}{2} = 20$’dir. $22$’nin $1$’den $20$’ye kadar olan katlarının modülo $41$’deki kalanlarını yazalım:

$j$	1	2	3	4	5	6	7	8	9	10
$22j \bmod 41$	22	3	25	6	28	9	31	12	34	15

$j$	11	12	13	14	15	16	17	18	19	20
$22j \bmod 41$	37	18	40	21	2	24	5	27	8	30

Koyu yazılan değerler $\tfrac{p}{2} = 20{,}5$’ten büyük olanlardır: $22, 25, 28, 31, 34, 37, 40, 21, 24, 27, 30$ — toplam $n = 11$ adet.

Gauss lemmasına göre:

\[\left( \frac{22}{41} \right) = (-1)^{11} = -1\]

Sonuç $-1$ çıktığı için $22$ bir KNR’dir ve denklemin çözümü yoktur.

2. yol — Euler kriteri.

$\left( \frac{22}{41} \right) \equiv 22^{20} \pmod{41}$ olmalıdır:

\[ \begin{aligned} 22^2 &= 484 = 41 \cdot 11 + 33 \equiv 33 \equiv -8 \pmod{41} \\ 22^4 &\equiv (-8)^2 = 64 \equiv 23 \equiv -18 \pmod{41} \\ 22^8 &\equiv (-18)^2 = 324 = 41 \cdot 7 + 37 \equiv 37 \equiv -4 \pmod{41} \\ 22^{16} &\equiv (-4)^2 = 16 \pmod{41} \end{aligned} \]

$20 = 16 + 4$ olduğundan:

\[22^{20} = 22^{16} \cdot 22^4 \equiv 16 \cdot (-18) = -288 \pmod{41}\]

$41 \cdot 8 = 328$ olduğundan $-288 + 328 = 40 \equiv -1 \pmod{41}$.

Sonuç yine $-1$ (KNR) olarak bulunur; iki yöntem birbirini doğrulamaktadır.

$\blacksquare$

Örnek 5.2 Euler kriteriyle bulduğumuz $\left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}$ özel değer formülünün doğruluğunu Gauss lemmasını kullanarak ispatlayınız.

💡 Çözümü göster / gizle

$a = -1$ alalım. Gauss lemması gereği $-1$’in katlarını yazarsak:

\[-1, \quad 2(-1), \quad \dots, \quad \frac{p-1}{2}(-1)\]

Bu negatif sayıların modülo $p$’deki asıl kalanlarını (modül ekleyerek) bulalım:

\[p-1, \quad p-2, \quad \dots, \quad p - \frac{p-1}{2} = \frac{p+1}{2}\]

Bu dizideki en küçük eleman olan $\tfrac{p+1}{2}$ bile $\tfrac{p}{2}$ değerinden büyüktür; yani kalanların hepsi $\tfrac{p}{2}$’den büyüktür. Dolayısıyla büyük kalanların sayısı doğrudan dizinin eleman sayısına eşittir:

\[n = \frac{p-1}{2}\]

Gauss lemmasına göre $\left( \frac{a}{p} \right) = (-1)^n$ olduğundan ispat tamamlanır:

\[\left( \frac{-1}{p} \right) = (-1)^{(p-1)/2}\]

$\blacksquare$

Örnek 5.3 $x^2 \equiv 3 \pmod{17}$ kongrüansının çözülebilirliğini $t$-toplam formülü ve Gauss lemması olmak üzere iki yolla analiz ediniz.

💡 Çözümü göster / gizle

Verilenler: $p = 17$, $a = 3$ ve $\tfrac{p-1}{2} = 8$.

1. yol — $t$-toplam formülü.

\[t = \sum_{j=1}^{8} \left\lfloor \frac{3j}{17} \right\rfloor\]

Tam kısımları tek tek hesaplayalım:

$j$	1	2	3	4	5	6	7	8
$3j$	3	6	9	12	15	18	21	24
$\left\lfloor 3j/17 \right\rfloor$	0	0	0	0	0	1	1	1

Toplam $t = 3$’tür. Buradan:

\[\left( \frac{3}{17} \right) = (-1)^3 = -1 \quad \text{(çözüm yok)}\]

2. yol — Gauss lemması.

$3$’ün ilk sekiz katının modülo $17$’deki değerleri:

\[3,\ 6,\ 9,\ 12,\ 15,\ 1,\ 4,\ 7\]

Bu sayılardan $\tfrac{p}{2} = 8{,}5$’ten büyük olanlar yalnızca $9, 12, 15$’tir; yani $n = 3$. Yine

\[\left( \frac{3}{17} \right) = (-1)^3 = -1\]

bulunur. Nitekim modülo $17$’deki kareler kümesi $\{1, 2, 4, 8, 9, 13, 15, 16\}$ olup $3$ bu kümede yer almaz.

$\blacksquare$

Örnek 5.4 Legendre sembolünün özelliklerini kullanarak $x^2 \equiv -2 \pmod{61}$ kongrüansının çözümünün olup olmadığını bulunuz.

💡 Çözümü göster / gizle

$p = 61$ ve $a = -2$’dir. Legendre sembolünün çarpımsallık özelliğini kullanarak sayıyı parçalayalım:

\[\left( \frac{-2}{61} \right) = \left( \frac{-1}{61} \right) \cdot \left( \frac{2}{61} \right)\]

Özel değer formüllerinden her iki parçayı ayrı ayrı hesaplayalım:

$\left( \frac{-1}{61} \right) = (-1)^{(61-1)/2} = (-1)^{30} = 1$
$\left( \frac{2}{61} \right) = (-1)^{(61^2-1)/8}$. Üssü hesaplayalım: $\tfrac{3721 - 1}{8} = 465$. Bu tek bir sayı olduğundan $(-1)^{465} = -1$.

Bu iki sonucu çarptığımızda:

\[\left( \frac{-2}{61} \right) = 1 \cdot (-1) = -1\]

Sonuç $-1$ (KNR) olduğundan denklemin çözümü yoktur.

Kontrol: $61 \equiv 5 \pmod 8$ olduğundan, bir sonraki örnekte göreceğimiz kural gereği $2$ modülo $61$’de bir non-rezidüdür — bulduğumuz sonuçla tutarlıdır.

$\blacksquare$

Örnek 5.5 $p$ tek asal sayı olmak üzere, $x^2 \equiv 2 \pmod p$ denkleminin çözülebilir olması için gerek ve yeter koşul nedir?

💡 Çözümü göster / gizle

Denklemin çözülebilmesi için $2$’nin KR olması, yani $\left( \frac{2}{p} \right) = 1$ olması zorunludur. $2$’nin karesel karakter formülünü hatırlayalım:

\[\left( \frac{2}{p} \right) = (-1)^{(p^2-1)/8} = 1\]

Bu eşitliğin sağlanabilmesi için üs olan $\tfrac{p^2-1}{8}$ ifadesinin çift olması gerekir:

\[\frac{p^2-1}{8} = 2k \implies p^2 - 1 = 16k \implies p^2 \equiv 1 \pmod{16}\]

Tek asalları mod $8$’e göre inceleyelim:

$p \bmod 8$	$p^2 \bmod 16$	$\tfrac{p^2-1}{8}$	$\left( \frac{2}{p} \right)$
$1$	$1$	çift	$+1$
$3$	$9$	tek	$-1$
$5$	$9$	tek	$-1$
$7$	$1$	çift	$+1$

Sonuç: $x^2 \equiv 2 \pmod p$ denklemi ancak ve ancak $p \equiv \pm 1 \pmod 8$, yani $p \equiv 1$ veya $p \equiv 7 \pmod 8$ olduğunda çözülebilirdir.

$\blacksquare$

Örnek 5.6 $m \geq 2$ bir tam sayı ve $\gcd(r, m) = 1$ olsun. Eğer $r$, modülo $m$’ye göre bir kuadratik rezidü ise, $r^{\phi(m)/2} \equiv 1 \pmod m$ olduğunu gösteriniz.

💡 Çözümü göster / gizle

$r$ bir KR olduğundan $x^2 \equiv r \pmod m$ denklemini sağlayan en az bir $a$ tam sayısı vardır:

\[a^2 \equiv r \pmod m\]

$\gcd(r, m) = 1$ olduğundan $\gcd(a^2, m) = 1$ ve dolayısıyla $a$ da modülle aralarında asaldır.

Kongrüansın her iki tarafının $\tfrac{\phi(m)}{2}$. kuvvetini alalım:

\[r^{\phi(m)/2} \equiv (a^2)^{\phi(m)/2} \equiv a^{\phi(m)} \pmod m\]

$a$ ve $m$ aralarında asal olduğu için Euler teoremi devreye girer ve $a^{\phi(m)} \equiv 1 \pmod m$ olur. Yerine yazdığımızda ispat tamamlanır:

\[r^{\phi(m)/2} \equiv 1 \pmod m\]

Bu sonuç, Euler kriterinin asal olmayan modüllere yönelik bir genellemesidir; ancak dikkat: tersi doğru değildir — $r^{\phi(m)/2} \equiv 1$ olması $r$’nin KR olmasını garanti etmez.

$\blacksquare$

\(p \bmod 8\)	\(p^2 \bmod 16\)	\(\tfrac{p^2-1}{8}\)	\(\left( \frac{2}{p} \right)\)
\(1\)	\(1\)	çift	\(+1\)
\(3\)	\(9\)	tek	\(-1\)
\(5\)	\(9\)	tek	\(-1\)
\(7\)	\(1\)	çift	\(+1\)

\(j\)	1	2	3	4	5	6	7	8
\(3j\)	3	6	9	12	15	18	21	24
\(\left\lfloor 3j/17 \right\rfloor\)	0	0	0	0	0	1	1	1