Kare Kalan'ın Öfkesi

Question

Soru:  Her $i\in \{1,2,\dots , 10\}$ için $x_i^2\equiv i\pmod{p}$ olacak şekilde $x_i$ tam sayıları olmasını sağlayan en küçük $p\geq 11$ asal sayısı kaçtır?

 

Kanyak: Bilkent Ünv. Matematik Bölümü (şu anda) 2. sınıf öğrencisi olan Metin Can Aydemir'in sorusudur.

 

Comments

Bu tarz araştırmalar var, 60lara dayanıyor geneli. Ben de şu ara biraz bakıyordum.

---

Asallarla ilgilenmek yeterli. Burada da tablosu var: wiki

---

Ayrıca koşul $p>2$ olarak ya da $p$ tek asal olarak değiştirilebilir. Bu durumlarda direkt cisimler gelecek ve içerisinde kare olmayan elemanlar olacak.

---

Soruyu tam anlamadim ama $p=311$ olabilir mi acaba?

$x_1= 1,x_2=66,x_3= 25,x_4=2,x_5= 117,x_6=95,x_7=140,x_8= 132,x_9= 3,x_{10}=    53$

---

Evet, sorunun yanıtı $311$ dir Ökkeş hocam.

---

ClearAll["Global`*"]
n = 10;
var = Array[x, n];
eq = Thread[var^2 == Range@n];
FirstPosition[Length /@ Table[Solve[eq, var, Modulus -> Prime[p]], {p, 5, 100}], _? Positive] + 4 // First // Prime

$p=311$

Answer 1

Yanıt $\boxed{311}$.

Öncelikle $x_2^2 \equiv 2 \pmod{p}$ denkliğine bakalım. Eğer uygun bir $x_2$ tam sayısı varsa bu durumu Legendre sembolü ile $\left(\dfrac{2}{p}\right)=1$ biçiminde yazarız.
$$\left(\dfrac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}$$
teoremine göre $p=8k\pm 1$ şeklindedir. ($k>0$ bir tam sayı.)

Şimdi de $x_3^2 \equiv 3 \pmod{p}$ denkliğine bakalım. Eğer uygun bir $x_3$ tam sayısı varsa bu durumu Legendre sembolü ile $\left(\dfrac{3}{p}\right)=1$ biçiminde yazarız. Quadratic Reciprocity (Karesel Mütekabiliyet) Teoremi ile

$$\left(\dfrac{3}{p}\right)\left(\dfrac{p}{3}\right)=(-1)^{\frac{p-1}{2}\frac{3-1}{3}}=(-1)^{\frac{p-1}{2}}$$

Eğer $p=8k+1$ biçiminde ise $\left(\dfrac{3}{p}\right)\left(\dfrac{p}{3}\right)=(-1)^{4k}=1$ olup $\left(\dfrac{p}{3}\right)=1$ olmalıdır. Bu ise $p=3n+1$ ($n>0$ bir tam sayı) biçiminde olması ile mümkündür. Buna göre $p=8k+1=3n+1$ dir. O halde $k=3m$ formundadır. $p=24m+1$ ($m>0$ bir tam sayı) biçimindedir.

Eğer $p=8k-1$ biçiminde ise $\left(\dfrac{3}{p}\right)\left(\dfrac{p}{3}\right)=(-1)^{4k-1}=-1$ olup $\left(\dfrac{p}{3}\right)=-1$ olmalıdır. Bu ise $p=3n-1$ ($n>0$ bir tam sayı) biçiminde olması ile mümkündür. Buna göre $p=8k-1=3n-1$ dir. O halde $k=3m$ formundadır. Bu halde $p=24m-1$ ($m>0$ bir tam sayı) biçimindedir.

$p=24m\pm 1$ biçiminde olsun. $\left(\dfrac{5}{p}\right)=1$ ise quadratic reciprocity teoremi gereği $\left(\dfrac{5}{p}\right)\left(\dfrac{p}{5}\right)=(-1)^{\frac{5-1}{2}\frac{24m + \pm 1 -1}{2}}=1$ olup $$\left(\dfrac{p}{5}\right)=1$$ bulunur. Bu ise $p=5t+1$ veya $p=5t+4$ olması demektir. ($t>0$ bir tam sayı.) Böylece $p=120a-1$, $p=120a + 1$, $p=120a + 71$  veya $p=120a + 49$ ($a>0$ tam sayı) biçimindedir.

$2, 3, 5$ sayıları $\mod p$ içinde birer kare kalan olduğundan bunların çarpımından elde edilen $6, 8, 10$ sayıları da birer kare kalandır. ($1,4,9$ sayıları açıkça her modda kare kalandır.) O halde geriye incelememiz gereken $7$ sayısı kaldı. 
$$\left(\dfrac{7}{p}\right)=1$$
olmasını istiyoruz. Yine quadratic reciprocity teoremi ile $\left(\dfrac{7}{p}\right)\left(\dfrac{p}{7}\right)=(-1)^{\frac{7-1}{2}\frac{p-1}{2}}$ yazılabilir. $p=120a+1$, $p=120a+49$ drumlarında $$\left(\dfrac{p}{7}\right)=1$$ bulunur. $p=120a-1$, $p=120a+71$ durumlarında ise $$\left(\dfrac{p}{7}\right)=-1$$ bulunur. 

Bu ise $p=120a + 1$, $p=120a+49$ durumlarında $p=7b+1$, $p=7b+2$ veya $p=7b+4$ olması demektir. ($b \geq 0$ bir tam sayı.) Bu değerlerin her birini $p=120a + 1$ ve $p=120a + 49$ değerlerine eşitlersek
$p=840c + 1, 840c + 121, 840c + 361$ ve $p=840c+169, 840c + 289, 840c + 529$ ($c \geq 0$ tam sayı) sayılarını elde ederiz. $c=1$ için $841=29^2, 961=31^2, 1201, 1009, 1129, 1369=37^2$ sayıları bulunur. Bunlar arasındaki en küçük asal sayı $1009$ dur. ($1129$ ve $1201$ de asaldır.)

Öte yandan $p=120a - 1$, $p=120a+71$ durumlarında $p=7b+3$, $p=7b+5$ veya $p=7b+6$ olması demektir. ($b\geq 0$ bir tam sayı.) Bu değerlerin her birini $p=120a - 1$ ve $p=120a + 71$ değerlerine eşitlersek
$p=840c + 479, 840c + 719, 840c -1$ ve $p=840c+311, 840c + 551, 840c + 671$ ($c\geq 0$ bir tam sayı) sayılarını elde ederiz. $c=0$ için $479, 719, -1, 311, 551=19\cdot 29, 671=11\cdot 61$ sayıları bulunur. Bunlar arasındaki en küçük asal sayı $311$ dir. ($479$ ve $719$ da asaldır.) $c=1$ vererek $311$ den daha büyük asallar elde edilir.

O halde elde edilen tüm değerler arasındaki en küçük asal sayı çözüm $311$ dir.

 

Notlar: 

1. $p=120a-1, 120a + 1, 120a + 49, 120a +71$ forumundaki asal sayılar küçükten büyüğe doğru incelenerek $x_7^2 \equiv 7\pmod{p}$ denkliğini sağlayan $x_7$ tam sayılarının varlığı da araştırılarak $311$ asal sayısına ulaşmayı deneyebilirdik. Fakat aranan en küçük asalın ilk başlarda karşımıza çıkacağından emin olamadığımız için deneme-yanılma çözümünün çok uzama riski de vardır. Bu sebeple yukarıdaki kesin sonuca götüren yöntemi tercih ettik. Böylece istenen özellikteki tüm asal sayıların $p \equiv 1, 121, 361, 169, 289, 529, 479, 719, -1, 311, 551 \pmod{840}$ formunda olduğunu da kanıtlamış olduk.

 

2. $x_{11}^2 \equiv 11 \pmod{479}$ denkliğinin çözüme sahip olduğunu quadratic reciprocity teoremi ile gösterebiliyoruz. $x_{12}^2 \equiv 12 \pmod{479}$ için inceleme yapalım. $3$ ve $4$ kare kalan olduğundan $12=3\cdot 4$ de bir kare kalandır. Böylece her $i\in \{1,2,\dots , 11,12 \}$ için $x_i^2\equiv i\pmod{p}$ olacak şekilde $x_i$ tam sayıları olmasını sağlayan en küçük asal sayı $p=479$ bulunur.