Ardışık Karekalanlar

[Metin Can Aydemir]

• Tweet

(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]

• Tweet

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]

• Tweet

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.