Gönderen Konu: Tübitak Lise 1. Aşama 2020 Soru 26  (Okunma sayısı 640 defa)

Çevrimdışı Uygar ÖZTÜRK

  • G.O Azimli Üye
  • ***
  • İleti: 35
  • Karma: +0/-0
Tübitak Lise 1. Aşama 2020 Soru 26
« : Eylül 06, 2020, 10:29:26 öö »
$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$

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3199
  • Karma: +22/-0
  • İstanbul
Ynt: Tübitak Lise 1. Aşama 2020 Soru 26
« Yanıtla #1 : Eylül 06, 2020, 08:00:45 ös »
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,5 \pmod {9}$ dur. Ortak çözüm yapılırsa $a \equiv 1, 16, 31 \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ü varsa $(a,23)=1$ olduğundan Fermat teoreminden $a^{22}\equiv 1 \pmod{23}$ olur. Bu halde $a$ nın mertebesi $22$ nin bölenidir ve $2, 11,22$ sayılarından biri olabilir. Bu ise $a^3 \equiv 1 \pmod {23}$ olması ile çelişir. Yani $a^3 \equiv 1 \pmod {23}$ denkliğinin $a \equiv 1 \pmod {23}$ dışında çözümü yoktur. $n=69$ sayısı tuhaf sayı olur.
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı metonster

  • G.O Genel Moderator
  • Geo-Maniac
  • ********
  • İleti: 504
  • Karma: +7/-0
Ynt: Tübitak Lise 1. Aşama 2020 Soru 26
« Yanıtla #2 : Haziran 15, 2021, 03:18:18 ös »
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)^{\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$$ 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. 
Gerçek hikayeler aslında söylenmeyenlerdir.

Çevrimdışı DrLucky

  • G.O Azimli Üye
  • ***
  • İleti: 25
  • Karma: +0/-0
Ynt: Tübitak Lise 1. Aşama 2020 Soru 26
« Yanıtla #3 : Haziran 21, 2021, 01:54:30 öö »
 $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

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3199
  • Karma: +22/-0
  • İstanbul
Ynt: Tübitak Lise 1. Aşama 2020 Soru 26
« Yanıtla #4 : Haziran 21, 2021, 03:26:47 öö »
Burada kullandığınız teoremi ne diye aratsam bulabilirim? @metonster

Quadratic Reciprocity (Karesel Mütekabiliyet) Teoremi için buraya ve şuraya bakılabilir.
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı DrLucky

  • G.O Azimli Üye
  • ***
  • İleti: 25
  • Karma: +0/-0
Ynt: Tübitak Lise 1. Aşama 2020 Soru 26
« Yanıtla #5 : Haziran 21, 2021, 01:20:04 ös »
Teşekkür ederim hocam

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal