Herhangi bir $p$ modunda kaç tane ardışık karekalan vardır?

Question

$p$ tek asal sayısı için $\mathbb{Z}^*_p=\{1,2,\dots,p-1\}$ olsun. $$Q_p=\{i\in \mathbb{Z}^*_p ~\big|~\exists x_i\in \mathbb{Z}^*_p , x_i^2\equiv i\pmod{p} \}$$ olarak tanımlayalım (Başka bir deyişle $Q_p$ kümesi; $p$ modunda, $p$'den küçük, pozitif karekalan tamsayılar kümesidir). $a\in Q_p$ ve $a+1\in Q_p$ olacak şekilde kaç tane $a$ tamsayısı vardır?  (Metin Can Aydemir)

Örnek: $p=11$ asal sayısı için $Q_{11}=\{1,3,4,5,9\}$ olur, sadece $a=3$ ve $a=4$ istenilen şartı sağlar. Yani $p=11$ için $2$ tane $a$ tamsayısı vardır.

Not: Bu soruyu yazarken herhangi bir kaynaktan faydalanmadım ama sayılar teorisi ile ilgili ileri seviye kaynaklarda bu veya buna benzer bir soru olabilir. 

Answer 1

$Q_p$ kümesinde bu şartı sağlayan $a$'ların kümesine $Q'_p$ kümesi diyelim (Sorudaki örnek için $Q'_{11}=\{3,4\}$'dür). Herhangi bir $a\in Q'_{p}$ için $a\in Q_p$ ve $a+1\in Q_p$ olduğundan $x^2\equiv a\pmod{p}$ ve $y^2\equiv a+1\pmod{p}$ olacak şekilde $x,y\in \mathbb{Z}_p$ vardır. $y^2-x^2\equiv 1\pmod{p}$ olacaktır. $$y^2-x^2\equiv 1\pmod{p}\Longrightarrow (y-x)(y+x)\equiv 1\pmod{p}$$ olur. $x\neq y$ ve $x\neq p-y$ olduğu barizdir. Dolayısıyla $y+x\equiv m\pmod{p}$ ve $y-x\equiv \dfrac{1}{m}\pmod{p}$ olacak şekilde $m\in \mathbb{Z}_p$ vardır. Buradan $y\equiv \dfrac{m^2+1}{2m}\pmod{p}$ ve $x\equiv \dfrac{m^2-1}{2m}\pmod{p}$ olarak bulunur. $x$ ve $y$, $0$'dan farklı olduğundan $m\neq 1$ ve $m\neq p-1$'dir. Ayrıca eğer $p$, $4k+1$ formatında ise $m^2+1\equiv 0\pmod{p}$ olacak şekilde tam olarak $2$ tane $m$ olacağından (bu değerlerin $1$ ve $p-1$'den farklı olacağı barizdir). Sonuç olarak $p=4k+1$ formatında ise $m$'nin alabileceği $p-5$ değer, eğer $p=4k+3$ formatında ise $p-3$ değer vardır. Lakin bazı değerler için $m\neq n$ olmasına rağmen $\left (\dfrac{m^2-1}{2m}\right )^2\equiv \left (\dfrac{n^2-1}{2n}\right )^2$ olabilir. Bu durumları incelemeliyiz. Sadece $\left (\dfrac{m^2-1}{2m}\right )^2\equiv \left (\dfrac{n^2-1}{2n}\right )^2$ durumunu incelememiz yeterlidir.

$\left (\dfrac{m^2-1}{2m}\right )^2\equiv \left (\dfrac{n^2-1}{2n}\right )^2 \Longleftrightarrow \left (\dfrac{m^2+1}{2m}\right )^2\equiv \left (\dfrac{n^2+1}{2n}\right )^2$ olduğunun ispatını okuyucuya bırakıyorum.

İfadeyi düzenlersek $$\dfrac{(m+n)(m-n)(mn+1)(mn-1)}{mn}\equiv 0\pmod{p}$$ elde edilir. Yani her $m$ için $m$, $-m$, $\dfrac{1}{m}$ ve $-\dfrac{1}{m}$ sayılarından ($p$ modundaki denklerinden) aynı sayıyı elde ederiz. Dolayısıyla şartı sağlayan $a$'ların sayısı seçebileceğimiz $m$ sayısının $4$'te biridir (bu dört sayının birbirinden farklı olduğu görülebilir). Dolayısıyla $Q'_p$ kümesinin eleman sayısı veya başka bir deyişle şartı sağlayan $a$ sayısı $p=4k+1$ formatında ise $\dfrac{p-5}{4}$, eğer $p=4k+3$ formatında ise $\dfrac{p-3}{4}$ tanedir. Bu ifadeleri birleştirerek $\left \lfloor \dfrac{p-3}{4}\right \rfloor $ gibi kapalı form elde edebiliriz. Örnekteki $p=11$ için $\dfrac{11-3}{4}=2$ olduğu görülebilir.

Not: Çözümde, bazı yerlerde mod belirtmeden denktir "$\equiv$" işaretini kullandım. Bu durumdaki kısımlarda eşitlik değil, $p$ modunda denklik kastedilmiştir.

Answer 2

Mathematica ile ilk $30$ asal sayi icin $a$ degerleri.

ClearAll["Global`*"]
ardisikKareKalan[p_] := Module[{},
  var = Array[x, p - 1];
  eq = Thread[var^2 == Range[p - 1]];
  sol = Length /@ (Solve[#1, #2, Modulus -> p] & @@@ Transpose@{eq, var}) // Unitize;
  Table[If[sol[[i]] != 0 && sol[[i]] == sol[[i + 1]], i, Nothing], {i,Length@sol - 1}]]
prime = Prime[Range[2, 30]];
TableForm[Transpose@{prime, Length /@ ardisikKareKalan /@ prime}, 
 TableHeadings -> {None, {"p", "a"}}]

 

$p\ge19$ icin $\Big\lfloor\dfrac pa\Big\rfloor=4$ veriyor gibi (en azindan $19\le p\le 1223$ icin boyle)

 

$\Big\lfloor\dfrac pa\Big\rfloor=4$  esitligini $a$ icin cozersek $a=1+c_1+c_2$ verir oyle ki $c_1,c_2\in\mathbb{Z^{\ge0}}$, $p\ge19$,  $p=4 + 5c_1+ 4c_2$ denkleminin cozumleri.

 

veya butun $p$'le icin

 

$\Big\lfloor\dfrac {p-3}a\Big\rfloor=4$  esitligini $a$ icin cozersek $a=1+c_1+c_2$ verir oyle ki $c_1,c_2\in\mathbb{Z^{\ge0}}$,   $p=7+ 5c_1+ 4c_2$ denkleminin cozumleri.

 

Bu arada $a=\Big\lfloor\dfrac {p-2}4\Big\rfloor$ dogru degerleri verir..

 

$\begin{array}{cc}
 \text{p} & \text{a} \\\hline
 3 & 0 \\
 5 & 0 \\
 7 & 1 \\
 11 & 2 \\
 13 & 2 \\
 17 & 3 \\
 19 & 4 \\
 23 & 5 \\
 29 & 6 \\
 31 & 7 \\
 37 & 8 \\
 41 & 9 \\
 43 & 10 \\
 47 & 11 \\
 53 & 12 \\
 59 & 14 \\
 61 & 14 \\
 67 & 16 \\
 71 & 17 \\
 73 & 17 \\
 79 & 19 \\
 83 & 20 \\
 89 & 21 \\
 97 & 23 \\
 101 & 24 \\
 103 & 25 \\
 107 & 26 \\
 109 & 26 \\
 113 & 27 \\
\end{array}$

Comments

Hah!

Bu sayıların artan bir dizi oluşturabileceklerini hiç tahmin etmezdim.

Bu arada OEIS'te baktığım kadarıyla bu diziye başka bir yerde rastlanmamış.

---

Ben karekalanlarla çalışırken $0$'ı genellikle hariç tuttuğum için ben de ilk başta OEIS'te diziyi bulamamıştım. Lakin sizin yorumunuzdan sonra aklıma geldi ve $0$ durumunu da ekleyerek arattım. Bu durumda A024698 kodlu dizi var. Fakat çözümümdekine benzer bir yöntemle aralarındaki farkın $i$ olduğu karekalan sayısını veren diziyi de bulabiliriz. Tabii $i$ arttıkça incelenmesi gereken durum da artacaktır, orası ayrı.