Tübitak Lise 1. Aşama 2020 Soru 26

[Uygar ÖZTÜRK]

$n$ pozitif bir tam sayı olmak üzere, $a^{3}-1$ in $n$ ile tam bölündüğü her $a$ tam sayısı için $a^{2020}-1$ de $n$ ile tam bölünüyorsa, $n$ ye $\textit{tuhaf sayı}$ diyelim. Aşağıdakilerden hangisi bir tuhaf sayıdır?

$\textbf{a)}\ 61 \qquad\textbf{b)}\ 63 \qquad\textbf{c)}\ 65 \qquad\textbf{d)}\ 67 \qquad\textbf{e)}\ 69$

[Lokman Gökçe]

Yanıt: $\boxed{E}$

$a^3 \equiv 1 \pmod n$ olması $a^{2020} \equiv 1 \pmod n$ olmasını gerektiriyorsa buradan $a \equiv 1 \pmod n$ elde edilir. O halde $a^3 \equiv 1 \pmod n$ denkliğinin tek çözümü $a \equiv 1 \pmod n$ ise $n$ tuhaf sayı olur. Eğer $a^3 \equiv 1 \pmod n$ denkliğinin $a \equiv 1 \pmod n$ den farklı çözümleri varsa bu durumda $n$ tuhaf sayı olmayacaktır.

$n=61$ asalı için $a^3 \equiv 1 \pmod {61}$ ise $ (a-1)(a^2+a+1) \equiv 0 \pmod {61}$ olur. $a \equiv 1 \pmod {61}$ veya $a^2+a+1 \equiv 0 \pmod {61}$ olur. Bu ikinci dereceden denkliği $4$ ile genişleterek tam kareye tamamlayalım. $(2a+1)^2 \equiv -3 \pmod{61}$ olur.  $(2a+1)^2 \equiv -3 \equiv 58 \equiv 119 \equiv \cdots \equiv 729 \pmod{61}$ olup $2a+1 \equiv \pm 27 \pmod{61}$ yazılır. Buradan  $a \equiv 13, 47 \pmod {61}$ çözümleri elde edilir. Örneğin $a=13$ için $61\mid 13^3 -1$ olurken $61\nmid 13^{2020} -1$ dir. $n=61$ tuhaf sayı değildir.

$n=63$ bileşik sayısı için $a^3 \equiv 1 \pmod {63}$ ise $a^3 \equiv 1 \pmod {7}$ ve $a^3 \equiv 1 \pmod {9}$ olur. Bu denklikleri çözersek $a \equiv 1,2, 4\pmod {7}$, $a \equiv 1,4, 7 \pmod {9}$ dir. Denkliklerin her ikisini de sağlayan bir çözüm $a=4$ olduğundan $a \equiv 4 \pmod {63}$ bulunabilir. Çin kalan teoremi ile tüm çözümler $a \equiv 1, 4, 16, 22, 25, 37, 43, 46, 58 \pmod {63}$ olup $9$ tanedir fakat bunların hepsini bulmaya ihtiyaç yoktur. $a=4$ için $63\mid 4^3 -1$ olurken $63\nmid 4^{2020} -1$ dir. Dolayısıyla $n=63$ sayısı da tuhaf sayı değildir.

$n=65$ bileşik sayısı için $a^3 \equiv 1 \pmod {65}$ ise $a^3 \equiv 1 \pmod {5}$ ve $a^3 \equiv 1 \pmod {13}$ olur. $a^3 \equiv 1 \pmod {5}$ denkliğinin tek çözümü $a \equiv 1 \pmod {5}$ tir. $a^3 \equiv 1 \pmod {13}$ denkliğinin çözümleri ise $a \equiv 1,3, 8\pmod {13}$ tür. Ortak çözüm yapılırsa $a \equiv 1, 16, 61 \pmod {63}$ bulunur. $a=16$ için $65\mid 16^3 -1$ olurken $65\nmid 16^{2020} -1$ dir.Dolayısıyla $n=65$ sayısı da tuhaf sayı değildir.

$n=67$ asalı için $a^3 \equiv 1 \pmod {67}$ ise $ (a-1)(a^2+a+1) \equiv 0 \pmod {67}$ olur. $a \equiv 1 \pmod {67}$ veya $a^2+a+1 \equiv 0 \pmod {67}$ olur. Bu ikinci dereceden denkliği $4$ ile genişleterek tam kareye tamamlayalım. $(2a+1)^2 \equiv -3 \pmod{67}$ olur.  $(2a+1)^2 \equiv -3 \equiv 64 \pmod{67}$ olup $2a+1 \equiv \pm 8 \pmod{67}$ yazılır. Buradan  $a \equiv 29, 37 \pmod {67}$ çözümleri elde edilir. Örneğin $a=29$ için $67\mid 29^3 -1$ olurken $67\nmid 29^{2020} -1$ dir. $n=67$ tuhaf sayı değildir.

$n=69$ bileşik sayısı için $a^3 \equiv 1 \pmod {69}$ ise $a^3 \equiv 1 \pmod {3}$ ve $a^3 \equiv 1 \pmod {23}$ olur. $a^3 \equiv 1 \pmod {3}$ denkliğinin tek çözümü $a \equiv 1 \pmod {3}$ tür. $a^3 \equiv 1 \pmod {23}$ denkliğinin $a \not\equiv 1 \pmod{23}$ olacak biçimde bir çözümü var mıdır? Bunu araştıralım. $(a,23)=1$ olduğundan Fermat teoreminden $a^{22}\equiv 1 \pmod{23}$ olur.  $a^3 \equiv 1 \pmod {23}$ olduğundan, $a^{22} \equiv a \equiv 1 \pmod {23}$ yazılabilir. Yani $a \equiv 1 \pmod {23}$ dışında çözüm yoktur. $n=69$ sayısı tuhaf sayı olur.

[Metin Can Aydemir]

Lokman hocamın çözümünün en başında belirtildiği gibi $a^3\equiv 1\pmod{n}$ denkliğinin $a\equiv 1\pmod{n}$'den farklı çözümleri varsa bu durumda $n$ tuhaf sayı olmayacaktır. $a^3-1\equiv (a-1)(a^2+a+1)\equiv 0\pmod{n}$ olduğundan $a^2+a+1\equiv 0 \pmod{n}$ denkliğinin $1$'den farklı çözümü yoksa $n$ tuhaf sayıdır. $p\mid n$ olan bir $p$ tek asal sayısı için $$a^2+a+1\equiv \dfrac{\left ( 2a+1\right )^2+3}{4}\equiv 0\pmod{p}\Longrightarrow (2a+1)^2\equiv -3\pmod{p}$$ olur. Yani $-3$, $p$ modunda karekalandır. $p\neq 3$ için $$\left (\dfrac{3}{p}\right )\left (\dfrac{p}{3}\right )\equiv (-1)^{\frac{(p-1)(3-1)}{4}}\equiv (-1)^{\frac{(p-1)}{2}}\equiv \left (\frac{-1}{p}\right )\Longrightarrow \left (\dfrac{p}{3}\right )\equiv \left (\dfrac{-3}{p}\right )\equiv 1$$ Dolayısıyla $p\equiv 1\pmod{3}$ olmalıdır ($3$ modundaki $0$ haricindeki tek karekalan $1$'dir). Şıklara bakarsak, $61\equiv 1\pmod{3}$'dür. Dolayısıyla $a^2+a+1\equiv 0\pmod{61}$ denkliğinin $1$'den farklı çözümü vardır.

$63=9\cdot 7$'dir. $a^2+a+1\equiv 0\pmod{7}$ denkliğinin $1$'den farklı çözümü vardır. $a\equiv 1\pmod{9}$ ve $a\equiv a_0\not\equiv 1\pmod{7}$ çözümünü alırsak ikisinden elde ettiğimiz çözüm $63$ modunda $1$ kalanı vermeyecektir. Dolayısıyla $63$ de tuhaf sayı değildir.

$65=5\cdot 13$'dür. Benzer şekilde $a^2+a+1\equiv 0\pmod{13}$ denkliğinin $1$'den farklı çözümü vardır. $a\equiv 1\pmod{5}$ çözümünü ve mod $13$'den gelen $1$'den farklı çözümü birleştirirsek $1$'den farklı bir çözüm elde ederiz. $65$ de tuhaf sayı değildir.

$67$ asal sayıdır ve $67\equiv 1\pmod{3}$ olduğundan tuhaf sayı değildir.

$69=3\cdot 23$'dür. $a^2+a+1\equiv 0 \pmod{23}$ denkliğinin çözümü yoktur çünkü $23\equiv 2\pmod{3}$'dür. Ayrıca $a^2+a+1\equiv 0\pmod{3}$ denkliğinin de tek çözümü $a\equiv 1\pmod{3}$'dür. Dolayısıyla buradan $a\equiv 1\pmod{69}$ haricinde çözüm elde edemeyiz. Dolayısıyla $\boxed{69}$ bir tuhaf sayıdır.

Daha genelleştirirsek $p\mid n$ olacak şekilde $3k+1$ formatında bir tek asal sayı yoksa $n$ tuhaf sayıdır. 

[DrLucky]

 $p\neq 3$ için $$\left (\dfrac{3}{p}\right )\left (\dfrac{p}{3}\right )\equiv (-1)^{\dfrac{(p-1)(3-1)}{4}}\equiv (-1)^{\dfrac{(p-1)}{2}}\equiv \left (\dfrac{-1}{p}\right )\Longrightarrow \left (\dfrac{p}{3}\right )\equiv \left (\dfrac{-3}{p}\right )\equiv 1$$

Burada kullandığınız teoremi ne diye aratsam bulabilirim? @metonster

[Lokman Gökçe]

Burada kullandığınız teoremi ne diye aratsam bulabilirim? @metonster

Quadratic Reciprocity (Karesel Mütekabiliyet) Teoremi için buraya ve şuraya bakılabilir.

[DrLucky]

Teşekkür ederim hocam