Ardışık Karekalanlar

[Metin Can Aydemir]

(Metin Can Aydemir) $p$ asal sayısı için $\mathbb{Z}_p^*=\{1,2,\dots,p-1\}$ olarak tanımlanır. $a\in \mathbb{Z}_p^*$ için $x^2\equiv a\pmod{p}$ denkliğinin $p$-modunda çözümü varsa $a$'ya karekalan (QR - quadratic residue), eğer çözümü yoksa $a$'ya QNR (quadratic non-residue) denir (bildiğim kadarıyla türkçede bu terimin bir karşılığı yok, sadece karekalan değildir deniliyor).

Yukarıdaki karekalan tanımına göre,

i) $p\geq 7$ ise $p$-modunda en az bir ardışık karekalan çifti vardır. Yani $a$ ve $a+1$ karekalan olacak şekilde bir $a$ vardır.

ii) $p\geq 19$ ise $p$-modunda en az bir ardışık karekalan üçlüsü vardır. Yani $a$, $a+1$ ve $a+2$ karekalan olacak şekilde bir $a$ vardır.

iii) $p\geq 59$ ise $p$-modunda en az bir ardışık karekalan dörtlüsü vardır. Yani $a$, $a+1$, $a+2$ ve $a+3$ karekalan olacak şekilde bir $a$ vardır.

iv) $f(p)$ ile $p$-modundaki en uzun ardışık karekalan dizisinin uzunluğunu belirtelim. Buna göre $f(p)$'nin ıraksadığını gösteriniz.

Not: Normalde karekalan tanımı yukarıdaki gibi değil, bazı kaynaklarda $a$'nın $p$ ile aralarında asal bir tamsayı olması yeterken bazıları bu şartı da koymayıp $0$'ı da karekalan kabul edebiliyor. Ben yukarıdaki sorular bozulmasın diye $a$ üzerinde yukarıdaki gibi bir sınırlama koydum.

[Metin Can Aydemir]

i) $p\geq 7$ ise $p$ tektir ve $(p,4)=1$ olur. Bu yüzden, $4$'ün $p$ modunda tersi vardır. $4$'ün $p$ modundaki tersini $4^{-1}$ ile gösterirsek, $3\cdot 4^{-1}$ ve $5\cdot 4^{-1}$ sayıları $p$ modunda $0$'a denk olamaz çünkü $(p,3)=(p,5)=1$'dir. Dolayısıyla bu sayıların kareleri de $0$'a denk olamaz. Yani $\left(3\cdot 4^{-1}\right)^2$ ve $\left(5\cdot 4^{-1}\right)^2$ sayılarının $p$ modundaki değerleri karekalandır. Bu iki karekalanın arasındaki farkın $1$'e denk olduğunu göstermemiz yeterlidir. $$\left(5\cdot 4^{-1}\right)^2-\left(3\cdot 4^{-1}\right)^2\equiv \left(5\cdot 4^{-1}+3\cdot 4^{-1}\right)\left(5\cdot 4^{-1}-3\cdot 4^{-1}\right)\equiv 8\cdot 4^{-1}\cdot 2\cdot 4^{-1}\equiv 1\pmod{p}$$ Dolayısıyla $p\geq 7$ ise ardışık bir karekalan çifti bulunabilir.

Alternatif Çözüm: $p\geq 7$ olduğundan $(2,p)=(5,p)=(10,p)=1$ olacaktır. Ayrıca $2$, $5$ ve $10$ sayılarından en az biri karekalan olmalıdır çünkü $2$ ve $5$ karekalan değilse $10$ karekalandır. Dolayısıyla $(1,2)$, $(4,5)$ ve $(9,10)$ çiftlerinden en az bir tanesi ($p$ modundaki değerleri) karekalan çifti olmalıdır.

Ayrıca buradaki gönderide $p$ modundaki ardışık karekalan çifti sayısı $\left\lfloor\dfrac{p-3}{4}\right \rfloor$ olarak bulunmuştu. Bu ifadenin $p\geq 7$ için $1$'den büyük veya eşit olacağı görülebilir.

iv) Bu fonksiyonun ıraksadığını göstermek için her $n$ doğal sayısı için $f(p)\geq n$ olacak şekilde bir $p$ asalı olduğunu göstermek yeterlidir. Soruyu daha daraltarak şöyle bir $p$ asalı bulmaya çalışalım, $1,2,\dots ,n$ sayılarının karekalan olmasını sağlayan bir $p$ asal sayısı var mıdır? Eğer olduğunu gösterirsek $f(p)\geq n$ olacaktır.

Bunun için de $n$'den küçük veya eşit asalların karekalan olmasını sağlamak yeterlidir çünkü $a$ ve $b$ karekalansa $ab$ de karekalan olacaktır ($p$ modundaki değeri). Bu asallar $2=p_0\leq p_1\leq \cdots \leq p_m$ olmak üzere, Eğer $p$'yi özel olarak $8k+1$ seçersek $p_0=2$ karekalan olacaktır. $i\geq 1$ için $p_i$ karekalan ise $$\left ( \dfrac{p}{p_i}\right)\left(\dfrac{p_i}{p}\right)=(-1)^{\frac{(p-1)(p_i-1)}{4}}=1$$ olacağından $$\left ( \dfrac{p}{p_i}\right)=\left(\dfrac{p_i}{p}\right)$$ olacaktır. Yani $p_i$'nin $p$ modunda karekalan olması için $p$'nin $p_i$ modunda karekalan olması gerekir. Mesela $p\equiv 1\pmod{p_i}$ seçebiliriz. Dolayısıyla $p\equiv 1\pmod{8p_1p_2\cdots p_m}$ seçersek $p_0,p_1,\dots,p_m$ asalları $p$ modunda karekalan olur ve dolayısıyla $1$'den $n$'ye kadar olan tüm sayılar karekalan olur.

Dirichlet teoremi der ki $a,b$ aralarında asal pozitif tamsayılar ise $an+b$ formatında sonsuz tane asal sayı vardır. Dolayısıyla $p\equiv 1\pmod{8p_1p_2\cdots p_m}$ olacak şekilde bir $p$ asalı vardır. Yani bu $p$ asalı için $f(p)\geq n$ olur. $f(p)$ ıraksar.

[Metin Can Aydemir]

ii) Bu soru ve 3. sorunun çözümünde benim bulabildiğim tek tam çözüm, durum incelemesi yapmak. Farklı birkaç yöntemle de çözmeye çalıştım ama sonuç elde edemedim. Edersem farklı çözüm olarak eklerim.

$p\geq 19$ ise $\{1,2,\dots,18\}\subseteq \mathbb{Z}_p^*$ olacaktır. Dolayısıyla bizim $\{1,2,\dots, 18\}$ kümesini kullanarak ardışık karekalan üçlüsü bulmamız yeterlidir. $p\geq 19$ olup ardışık karekalan üçlüsü barındırmayan bir asal olduğunu varsayalım. Bu $p$ asal sayısı üzerinden çelişki bulmaya çalışacağız. Sayıları karekalansa kırmızı ile, değilse mavi ile, bilmiyorsak siyah ile göstereceğiz. Her durumda $1,4,9,16$ sayıları karekalandır.

1) $2$ karekalansa, $8$ ve $18$ sayıları da karekalandır fakat $3$, $7$, $10$ ve $17$ sayıları karekalan olamaz çünkü $(1,2,3)$, $(7,8,9)$, $(8,9,10)$ veya $(16,17,18)$ üçlüleri ortaya çıkar. $10$ karekalan olmadığından fakat $2$ olduğundan $5$ karekalan olamaz.

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18

$(p,7)$ olduğundan $7$'nin $p$ modunda çarpmaya göre tersi vardır, bunu $7^{-1}$ ile gösterirsek, $7^{-1}$ de karekalan olmayacaktır çünkü $7\cdot 7^{-1}\equiv 1\pmod{p}$ olur ve $1$ karekalan iken $7$ değildir. Dolayısıyla $\left(3\cdot 7^{-1},10\cdot 7^{-1},17\cdot 7^{-1}\right)$ üçlüsü karekalan üçlüsü olur, ayrıca aralarındaki fark $1$'dir çünkü $(a+7)\cdot 7^{-1}-a\cdot 7^{-1}\equiv 7\cdot 7^{-1}\equiv 1\pmod{p}$ olur. Bu bir çelişkidir çünkü biz böyle bir üçlü olmadığını varsaymıştık (bu sayıların $0$'a denk olmayacağını biliyoruz, ayrıca $p$'den büyük olsalar da $p$ modundaki kalanları üçlü oluşturur).

2) $2$ ve $3$ karekalan değilse $6$ karekalan olur fakat $8$, $12$ ve $18$ karekalan olmaz. Bu durumda $5$ de karekalan değildir çünkü aksi takdirde $(4,5,6)$ karekalan üçlüsü olurdu. Bu durumda da $\left (2\cdot 3^{-1},5\cdot 3^{-1},8\cdot 3^{-1}\right)$ üçlüsü kesin olarak karekalan üçlüsü olurdu. Bu da bir çelişkidir.

3) Eğer $2$ karekalan değil fakat $3$ karekalan ise $6$, $8$, $18$ karekalan olmayacak fakar $12$ karekalan olacaktır.  $(3,4,5)$ üçlüsünün karekalan üçlüsü olmaması için $5$ karekalan olmamalıdır. Dolayısıyla $10$ karekalan olacaktır fakat $15$ olmayacaktır. $9$ ve $10$ karekalan olduğundan $11$ karekalan olamaz.

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18

$7$ karekalansa $\left(3^{-1},4\cdot 3^{-1}, 7\cdot 3^{-1}\right)$ karekalan üçlüsü olurdu. Dolayısıyla $7$ karekalan değildir. Buradan $14$'ün karekalan olacağını buluruz. $12$ ve $14$ karekalan olduğundan $13$ karekalan değildir.

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18

Yine de bu durumda $\left(8\cdot 5^{-1},13\cdot 5^{-1},18\cdot 5^{-1}\right)$ karekalan üçlüsü olurdu. Çelişki

Tüm durumlarda çelişki bulduğumuzdan $p\geq 19$ olup ardışık karekalan üçlüsü içermeyen bir asal yoktur.