Karekalanların toplamı

[Metin Can Aydemir]

$p\geq 5$ tek bir asal sayı olsun. $\{1,2,\dots,p-1\}$ kümesini karekalanlar ($Q$) ve karekalan olmayanlar ($N$) olarak ayıralım. $S(A)$ ile $A$ kümesinin elemanlarının toplamını gösterelim.

$(a)$ $p\mid S(Q)$ ve $p\mid S(N)$ olduğunu gösteriniz.
$(b)$ $S(Q)=S(N)$ ancak ve ancak $p\equiv 1\pmod{4}$ olduğunu gösteriniz.

[Lokman Gökçe]

Çözüm [Lokman Gökçe]:

$(a)$ $A = \{1,2,\dots,p-1\}$ diyelim. $S(A) = 1 + 2 + \cdots + (p-1) = \dfrac{p(p-1)}{2}$ olup $p\mid S(A)$ dır.

Şimdi $Q$ kümesinden bir $r$ elemanını göz önüne alalım. Yani $r$, modülo $p$'de bir kare kalandır. $x^2 \equiv r \pmod{p}$ olacak şekilde bir $x$ tam sayısı vardır. Şimdi de $p - r$ sayısını göz önüne alalım. $y^2 \equiv p-r \equiv -r \pmod{p}$ olacak şekilde bir $y$ tam sayısı olup olmadığını araştıralım. Eğer $p\equiv 1 \pmod{4}$ ise, $-1$ modülo $p$'de bir kare kalandır; $p\equiv 3 \pmod{4}$ ise, $-1$ modülo $p$'de bir kare kalan değildir. (İspatı için 4n+1 asal konusuna bakınız.) Dolayısıyla $p\equiv 1 \pmod{4}$ ise $p-r$ bir kare kalandır, $p-r \in Q$ olur. Şayet $p\equiv 3 \pmod{4}$ ise $p-r$ bir kare kalan değildir, $p-r \in N$ olur.

Şimdi $p\equiv 1 \pmod{4}$ durumuna bakalım. $r, p-r \in Q$ olup $r + (p-r) = p$'dir. $p$ tek sayı olduğundan $r\neq p-r$'dir. Dolayısıyla $Q$ daki elemanları bu şekilde ikişerli gruplar halinde toplarsak, bu ikililerin toplamı $p$ olduğundan $S(Q)$ da $p$'nin bir tam katı olur. $p\mid S(Q)$ elde edilir. $S(N) = S(A) - S(Q)$ olduğundan $p\mid S(N)$ bulunur.

Şimdi de  $p\equiv 3 \pmod{4}$ durumuna bakalım. Bu halde $p-r\in N$'dir. Bu yolla $Q$ ve $N$ kümeleri arasında bire bir eşleme kurabiliyoruz. Yani bu kümeler eşit sayıda eleman içeriyorlar. Her bir kümede $k=\dfrac{p-1}{2}$ tane eleman vardır. $Q = \{ r_1, r_2, \dots, r_k\}$ olsun. $N = \{ p - r_1, p - r_2, \dots, p - r_k\}$ olur. $Q$ ve $N$'deki tüm elemanların toplamına bakalım:
$$ \sum_{i=1}^k r_i + \sum_{i=1}^k (p - r_i) = S(A) = \dfrac{p(p-1)}{2} = pk$$

olur. Bu da bildiğimiz bir şey ve işe yarar bir sonuç çıkmadı. Hımm... O zaman $x_i^2 \equiv r_i \pmod{p}$ denkliğinin çözümlerine bakalım. Birbirine denk olmayan iki çözüm vardır ve bunlar $x_i, -x_i$'dir. Tüm $r_i$'lerden gelecek $\mp x_i$ çözümlerinin kümesi tam olarak $2\cdot\dfrac{p-1}{2} = p-1$ elemanlı olur. Yani bu $x_i$ lerin kümesi bize modülo $p$'de, $0$'ın atılmasıyla elde edilmiş kalan sınıfını verir. $-x_i$ yerine buna denk olan $p-x_i$ sayısını aldığımızda, bu küme $A$ kümesiyle aynı olur. Sanki buradan bir şey gelecek gibi. Devam edelim...

$$ \sum_{i=1}^k 2r_i = \sum_{i=1}^k (x_i^2 + (p-x_i)^2)) = A\text{ kümesinin elemanlarının karelerinin toplamı} = \dfrac{p(p-1)(2p-1)}{6}$$

olduğundan

$$ \sum_{i=1}^k r_i = \dfrac{p(p-1)(2p-1)}{12}$$

elde edilir. Özel olarak $S(Q) = \dfrac{p(p-1)(2p-1)}{12}$ sonucuna ulaşırız. Bu halde de $p\mid S(Q)$ olmaktadır. Yine, $S(N) = S(A) - S(Q)$ kullanılarak $p\mid S(N)$ bulunur.

Bir dakika! Yeterince büyük $p$ asalları için kübik formüle sahip $S(Q)$, karesel formüle sahip $S(A)$ dan daha büyük olur. Bu ise $S(Q)<S(A)$ gerçeği ile çelişir. Bir yerde kötü bir hata yapıyorum. Vakit geç olduğu için, yazdıklarımı da silmeden paylaşmış olayım. Müsait vakitte hatamı düzeltmeye çalışayım. Hatamın ne olduğunu gördüyseniz paylaşabilirsiniz, teşekkürler. 

[Metin Can Aydemir]

Bir dakika! Yeterince büyük $p$ asalları için kübik formüle sahip $S(Q)$, karesel formüle sahip $S(A)$ dan daha büyük olur. Bu ise $S(Q)<S(A)$ gerçeği ile çelişir. Bir yerde kötü bir hata yapıyorum. Vakit geç olduğu için, yazdıklarımı da silmeden paylaşmış olayım. Müsait vakitte hatamı düzeltmeye çalışayım. Hatamın ne olduğunu gördüyseniz paylaşabilirsiniz, teşekkürler. 

Aslında çözümünüz bitmiş sadece çok ufak bir yerde hata yapmışsınız hocam. $2r_i$'ler ile $x_i^2+(p-x_i)^2$ terimleri birbirine eşit değil ancak $p$ modunda denkler. Dolayısıyla, $$\sum_{i=1}^k2r_i\equiv \sum_{i=1}^k(x_i^2+(p-x_i)^2)=\frac{p(p-1)(2p-1)}{6}\equiv 0\pmod{p}\implies p\left\lvert\sum_{i=1}^kr_i=S(Q)\right.$$ bulunur. $4k+3$ formatındaki asallar için $S(Q)$'nun $p$ cinsinden kapalı bir formülü var mı bilmiyorum ancak $4k+1$ formatında, $b$ şıkkında da dediği gibi $S(Q)=S(N)=\frac{p(p-1)}{4}$ olacaktır.

[geo]

$(b)$
$S(Q)+S(N)=\dfrac{(p-1)p}{2}$ olduğu için $S(Q)=S(N)$ olması için $S(Q)=\dfrac{(p-1)p}{4}$ olması gerekir. $(p,4)=1$ olduğu için $4\mid p-1$ olması gerekir. Bu da $p\equiv 1 \pmod 4$ demektir. Yani $p \equiv 3 \pmod 4$ asallarından hiçbirisi için $S(Q)=S(N)$ olamaz.

Peki her $p\equiv 1 \pmod 4$ asal sayısı için $S(Q)=S(N)$ midir?
$-1$ in karekalan olduğunu biliyoruz. Bu durumda $a$ bir karekalan ise $p-a$ da bir karekalan olacaktır.
$0$ hariç $\dfrac{p-1}{2}$ karekalan var. Bunlar toplamları $p$ olan $\dfrac{p-1}{4}$ karekalan çifti oluşturur. Bunların toplamı da $S(Q)=\dfrac{p-1}{4}\cdot p$ dir. $\blacksquare$

[geo]

$(a)$
$S(Q)+S(N)=1+2+\ldots + (p-1) = \dfrac{(p-1)p}{2} \equiv 0 \pmod p$ olduğu için $S(Q)\equiv 0 \pmod p$ olduğunu gösterirsek $S(N)\equiv 0\pmod p$ olacaktır.

$x^2\equiv y^2\pmod p$ ise $(x-y)(x+y)\equiv 0 \pmod p$, yani $x\equiv y \pmod p$ veya $x\equiv -y\pmod p$ dir.
Bu durumda tüm karekalanlar $\bmod p$ de $\left \{1^2, 2^2, \ldots, \left ( \dfrac{p-1}2\right )^2\right \}$ kümesine denk olacaktır.
$S(Q) \equiv \displaystyle \sum_{n=1}^{(p-1)/2} n^2\equiv \dfrac{\dfrac{p-1}2 \cdot \dfrac{p+1}2 \cdot p }{6}\equiv \dfrac{(p-1)p(p+1)}{24} \pmod p$

$p>3$ ise $(p,24)=1$ olacağı için $S(Q) \equiv \dfrac{(p-1)p(p+1)}{24} \equiv 0 \pmod p$

$p=3$ ise $S(Q)=1$ ve $S(N)=2$ olacaktır.
Soru, $p>3$ asal sayılar şeklinde değiştirilmeli.

[Metin Can Aydemir]

geo hocamın düzeltmesiyle soruyu $p\geq 5$ olarak değiştirdim. $(a)$ için kendi çözümümü vereyim, $(b)$ için benim çözümüm de geo hocamla aynı.

$G=\sum\limits_{n=1}^{p-1}n\left(\frac{n}{p}\right)$ toplamına bakalım. Legendre sembolü karekalanlarda $1$, karekalan olmayanlarda $-1$ sonucu verdiğinden $G=S(Q)-S(N)$ olacaktır. $S(N)+S(Q)=\frac{p(p-1)}{2}\equiv 0\pmod{p}$ olduğundan $p\mid G$ olduğunu göstermek, $p\mid S(Q),S(N)$ olduğunu göstermek için yeterlidir. $(a,p)=1$ olmak üzere $$a\left(\frac{a}{p}\right)G=\sum_{n=1}^{p-1}(an)\left(\frac{an}{p}\right)$$ toplamını elde ederiz. $\{1,2,\dots, (p-1)\}$ ile $\{a,2a,\dots, (p-1)a\}$ kümeleri $p$ modunda birbirlerine eşittir çünkü ikinci kümedeki herhangi iki eleman birbirine eşit değildir ve hepsi $p$ ile aralarında asaldır. Dolayısıyla $a\left(\frac{a}{p}\right)G$ toplamına $p$ modunda bakarsak, $$\sum_{n=1}^{p-1}an\left(\frac{an}{p}\right)\equiv \sum_{m=1}^{p-1}m\left(\frac{m}{p}\right)=G\pmod{p}$$ elde edilir. Yani, $$a\left(\frac{a}{p}\right)G\equiv G\pmod{p}\implies p\mid G\left(a\left(\frac{a}{p}\right)-1\right)$$ elde edilir. $p\geq 5$ olduğundan $a=2$ seçersek, $2\left(\frac{2}{p}\right)-1=1$ veya $-3$ olacaktır. İki durumda da $p$ ile aralarında asaldır. Sonuç olarak $p\mid G$ bulunur ve ispat biter.