Gönderen Konu: Tübitak Lise 1. Aşama 2003 Soru 22  (Okunma sayısı 3876 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1812
  • Karma: +8/-0
Tübitak Lise 1. Aşama 2003 Soru 22
« : Mayıs 07, 2014, 12:42:12 öö »
Aşağıdaki $n$ tam sayılarından hangisi için $x^2 \equiv -1 \pmod{n}$ denkliğini sağlayan en az bir $x$ tam sayısı vardır?

$
\textbf{a)}\ 97
\qquad\textbf{b)}\ 98
\qquad\textbf{c)}\ 99
\qquad\textbf{d)}\ 100
\qquad\textbf{e)}\ \text{Hiçbiri}
$

Çevrimdışı Dogukan6336

  • G.O Sevecen Üye
  • ****
  • İleti: 54
  • Karma: +2/-0
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #1 : Nisan 30, 2017, 10:05:41 ös »
Teorem 1 : p asal sayı ve (a,b) = OBEB(a,b)=1 olmak üzere

$ x^n \equiv a (mod p)$  olsun. Eğer $ a^{\dfrac {p-1} {(n,p-1)}} \not\equiv  1 (mod p) $  ise denkliğin çözümü yoktur..


İspat 1 :


$(n,p-1)=d$ olsun. Bu denkliğin çözümlerinden biri $u$ olsun. Ve  Fermat teoreminden $ u^{p-1}\equiv 1 (mod p)$ olduğunu biliyoruz. Bu durumda

$a^{\dfrac {p-1} {d}} \equiv u^{n(\dfrac {p-1} {d})} \equiv u^{(p-1)(\dfrac {n} {d})} \equiv 1 (mod p)  $

Olacaktır. İspatımız bitmiştir.

Teorem 2:

 $a^{\dfrac {p-1} {(n,p-1)}} \equiv  1$ ise denkliğin çözümü vardır.


İspat 2 :

Öyle bir $g$ sayısı alalım ki $g$ sayısının $mod p$ deki mertebesi $p-1$ olsun. Ayrıca

$g^j \equiv a (mod p)$
[/b]

olsun ve bu denkliği sağlayan en küçük üs $j$ olsun.

$g^{j(\dfrac {p-1} {d})}\equiv 1 \equiv g^0 (mod p)$



$\dfrac {j(p-1)} {d}\equiv 0 (mod p-1)$

$\dfrac {j(p-1)} {d} = k(p-1)$


olup $d$ sayısı $j$ sayısını bölecektir.

$g$ nin mertebesi $p-1$ olduğundan $g^0 , g^1 , ...g^{p-1}$ sayıları $p$ modülüne göre bir asal kalan sistemi oluştururlar.

O halde $x^n \equiv a (mod p)$ denkliğinin çözümleri $x \equiv g^y (mod p)$  şeklindedir. Ve vardırlar.



Soru için bizden istenen $  (-1)^{\dfrac {n-1} {2}} \equiv 1 (mod n)$ olması. Seçeceğimiz $n$ sayısı asal olmalı. Şıklarda tek asal sayı $97$ dir. $(-1)^{48} \equiv 1 (mod 97)$




« Son Düzenleme: Mayıs 01, 2017, 02:05:18 öö Gönderen: Dogukan6336 »

Çevrimdışı Eray

  • G.O Genel Moderator
  • G.O Efsane Üye
  • ********
  • İleti: 381
  • Karma: +8/-0
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #2 : Nisan 30, 2017, 10:44:46 ös »
Soru için bizden istenen $  (-1)^{\dfrac {n-1} {2}} \equiv 1 (mod n)$ olması. Seçeceğimiz $n$ sayısı asal olmalı. Şıklarda tek asal sayı $97$ dir. $(-1)^{48} \equiv 1 (mod 97)$

Seçeceğimiz $n$ sayısı neden asal olmalı?

$(-1)^\dfrac{n-1}{2}\equiv1\pmod n$ denkliği $n=4k+1$ formundaki doğal sayılar için de sağlanır
Matematik bilimlerin sultanıdır
-Carl Friedrich Gauss

Çevrimdışı Dogukan6336

  • G.O Sevecen Üye
  • ****
  • İleti: 54
  • Karma: +2/-0
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #3 : Nisan 30, 2017, 11:00:25 ös »
Soru için bizden istenen $  (-1)^{\dfrac {n-1} {2}} \equiv 1 (mod n)$ olması. Seçeceğimiz $n$ sayısı asal olmalı. Şıklarda tek asal sayı $97$ dir. $(-1)^{48} \equiv 1 (mod 97)$

Seçeceğimiz $n$ sayısı neden asal olmalı?

$(-1)^\dfrac{n-1}{2}\equiv1\pmod n$ denkliği $n=4k+1$ formundaki doğal sayılar için de sağlanır
Sağlanır tabii ki, hatta n = 8k+1 için de sağlanır. Güzel bir denklik fakat asal sayılar dışında oyuncak olmaktan başka işe yaramaz. Çünkü,

$n = 9$ için sağlanır mesela sizin dediğiniz gibi. Fakat $x^2 \equiv -1 (mod 9)$ denkliğinin çözümü yok. Çünkü Benim yazdığım teoreme göre, çözümün varlığını incelemek için yalnızca asal sayılar ve Carmichael sayılarını kullanabiliyoruz. Çünkü,

$ (u)^{p-1} \equiv 1 (mod p)$

denkliğini sağlayan tek sayılar onlar.
« Son Düzenleme: Mayıs 01, 2017, 01:05:46 öö Gönderen: Eray »

Çevrimdışı Eray

  • G.O Genel Moderator
  • G.O Efsane Üye
  • ********
  • İleti: 381
  • Karma: +8/-0
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #4 : Mayıs 01, 2017, 01:19:15 öö »
Sağlanır tabii ki, hatta n = 8k+1 için de sağlanır. Güzel bir denklik fakat asal sayılar dışında oyuncak olmaktan başka işe yaramaz. Çünkü,

$n = 9$ için sağlanır mesela sizin dediğiniz gibi. Fakat $x^2 \equiv -1 (mod 9)$ denkliğinin çözümü yok. Çünkü Benim yazdığım teoreme göre, çözümün varlığını incelemek için yalnızca asal sayılar ve Carmichael sayılarını kullanabiliyoruz. Çünkü,

$ (u)^{p-1} \equiv 1 (mod p)$

denkliğini sağlayan tek sayılar onlar.

Öncelikle teoreme verdiğiniz ispat, ifadesi şöyle olan teoremin ispatıdır: "$(a,p)=1$ ve $x^n\equiv a\pmod p$ denkliğinin çözümü varsa $a^{\dfrac {p-1} {(n,p-1)}} \equiv 1 \pmod p$ dir."
Sizin yazdığınız teoremin ifadesinde bu önermenin karşıtı yer alıyor.

Asal sayılar için bir teorem iddia edip sonra $n$ sayımızı asal seçelim diyip $97$ yi denemişsiniz. $97$ yi denemek için bu kadar şey yazmaya gerek yok halbuki :)
Matematik bilimlerin sultanıdır
-Carl Friedrich Gauss

Çevrimdışı Dogukan6336

  • G.O Sevecen Üye
  • ****
  • İleti: 54
  • Karma: +2/-0
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #5 : Mayıs 01, 2017, 01:27:47 öö »
Sağlanır tabii ki, hatta n = 8k+1 için de sağlanır. Güzel bir denklik fakat asal sayılar dışında oyuncak olmaktan başka işe yaramaz. Çünkü,

$n = 9$ için sağlanır mesela sizin dediğiniz gibi. Fakat $x^2 \equiv -1 (mod 9)$ denkliğinin çözümü yok. Çünkü Benim yazdığım teoreme göre, çözümün varlığını incelemek için yalnızca asal sayılar ve Carmichael sayılarını kullanabiliyoruz. Çünkü,

$ (u)^{p-1} \equiv 1 (mod p)$

denkliğini sağlayan tek sayılar onlar.

Öncelikle teoreme verdiğiniz ispat, ifadesi şöyle olan teoremin ispatıdır: "$(a,p)=1$ ve $x^n\equiv a\pmod p$ denkliğinin çözümü varsa $a^{\dfrac {p-1} {(n,p-1)}} \equiv 1 \pmod p$ dir."
Sizin yazdığınız teoremin ifadesinde bu önermenin karşıtı yer alıyor.

Asal sayılar için bir teorem iddia edip sonra $n$ sayımızı asal seçelim diyip $97$ yi denemişsiniz. $97$ yi denemek için bu kadar şey yazmaya gerek yok halbuki :)
Anladım şimdi hocam ama olsun ya çok fark etmiyor sonuçta doğru çözüme ulaşıyoruz :D. Benim soruyu gördüğümde aklıma ilk bu geldi. Muhtemelen daha kısa bir çözüm yöntemi vardır  :D. edit : Teoremi düzelteceğim birazdan.
« Son Düzenleme: Mayıs 01, 2017, 01:38:34 öö Gönderen: Dogukan6336 »

Çevrimdışı ArtOfMathSolving

  • G.O Efsane Üye
  • *******
  • İleti: 423
  • Karma: +4/-8
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #6 : Mayıs 01, 2017, 06:09:18 ös »
Bu eğlenceli konuşmaya ben de dahil olayım. O zaman başlayalım.
İfademizi $k \in \mathbb{Z^{+}}$ olmak üzere, $x^2 = nk-1$ şeklinde tanımlayalım. Soruya biraz analizsel yaklaşalım,

Şimdi bir işlem tanımlayacağız. Bu işlemi sevdiğim bir grek harfi olan $\psi$ ile göstereceğiz.

$n_1, n_2, n_3, \dots$ Tanımladığımız $\psi$ işleminin tanım kümesi olmak üzere bu kümeyi şu şekilde gösterelim :

$\psi^{\mathbb{T}} = \{n_1, n_2, n_3, \dots\}$.

Burada $\mathbb{P}$ asal sayılar kümesidir. $\mathbb{P_{1\pmod{4}}}$ te $4n+1$ formundaki asal sayıları göstermektedir. Göstermemiz gereken herhangi bir $l\in\mathbb{Z^{+}}$ için, $\psi\{n\}\longrightarrow|\psi^{\mathbb{T}}(1-l)-n| \longrightarrow\mathbb{P_{1\pmod{4}}}$ eşlemesinin doğru  olabildiği. Çünkü eğer bu eşleme doğru ise, tanımladığımız kümedeki sayıları kullanarak, $\psi\{x\}=p-\psi^{\mathbb{T}}l$ şeklinde çözümler elde etmek mümkün ve bunun doğal sonucu olarak ta $n\longrightarrow \mathbb{P_{1 \pmod{4}}}$ olacak. (Tabiki burada $p$ bir asal sayı).  Başka bir deyişle, kanıtlamamız gereken tanımladığımız işlemin uygun koşullar altında varlığı.

Bu durumda $\psi\{x\}$ işlemimizin $2$ adet doğrudan kökü olacaktır. $a\space\text{ve}\space l\in \mathbb{Z^{+}}$ olmak üzere şemamızı çizelim,
$$\begin{matrix}
   &&\psi\{a\}\longrightarrow |a-\psi^{\mathbb{T}}l|
\\   && \downarrow &
\\  && |\psi^{\mathbb{T}}(1-l)-a|
\end{matrix}$$

Çizdiğimiz eşleme şeması ise kafamızda canlandırdığımız muhtemel fonksiyon argümanı. Bundan sonraki adımlarımız, bu argümanın doğru olduğunu ispatlamak olacak.
Burada her ne kadar $\psi$ işleminin ürettiği $2$ kökü birbirinin eşi gibi görünüyorsa da aslında birbirlerinin tersidir. Genel olarak yol haritamızı açıkladığımıza göre teoremlerimizi vermeye başlayalım.
Sıradan bir matematikçi...

Çevrimdışı ArtOfMathSolving

  • G.O Efsane Üye
  • *******
  • İleti: 423
  • Karma: +4/-8
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #7 : Mayıs 02, 2017, 02:42:10 öö »
Kaldığımız yerden devam edelim.
Tanım 1
Herhangi bir $\psi$ işlemi için, $\psi^{\mathbb{T}}$ bu işlemin tanımlandığı kümedir.

Tanım 2
$\{n_1, n_2, n_3, \dots < k\}$ bir tamsayı kümesi olmak üzere, $\psi^{\mathbb{T}} = \{n_1, n_2, n_3, \dots <k \}$ şeklinde tanımlanır.

Tanım 3
$\mathbb{P}_{1 \pmod{4}}$ kümesi $4c+1,  (c\in \mathbb{Z^{+}})$ şeklinde tanımlı asal sayılar kümesidir.

Tanım 4
$\psi(n)\longrightarrow \mathbb{P}$ bir eşlemedir.

Tanım 5
$a\space\text{ve}\space l\in \mathbb{Z^{+}}$ olmak üzere,
$\psi\{a\}\longrightarrow |a-\psi^{\mathbb{T}}l|$ şeklinde tanımlanır.

Teorem 1
$\psi\{x\}$ işlemimizin en az $2$ adet kökü vardır.

İspat: Tanım $5$ ten biliyoruz ki işlemimizi, $\psi\{a\}\longrightarrow |a-\psi^{\mathbb{T}}l|$ şeklinde tanımlamak mümkün idi, eğer bu eşleme sorudaki denklemi sağlıyorsa mutlaka $\psi\{a\}\longrightarrow|a(1-l)-\psi^{\mathbb{T}}|$ eşlemesi de doğru olmalıdır çünkü $l=0$ ve $\psi^{\mathbb{T}}\longrightarrow 0$ olması durumunda, $\psi\{a\}\longrightarrow |a-\psi^{\mathbb{T}}l|\longrightarrow |a(1-l)-\psi^{\mathbb{T}}|\longrightarrow a $ olacaktır. Yani bu iki kök birbirini üretebilir çünkü buradaki eşlemeler birebirdir. $\blacksquare$

Tanım 6
 Teorem 5'ten dolayı $\psi\{x\}\longrightarrow x$ dir.

Teorem 2
$2\psi^{\mathbb{T}}-n\longrightarrow \mathbb{P}_{1 \pmod{4}}$ eşlemesi doğrudur.

İspat: Aslında Burada bu Teoreme örnek olarak $n=97$ için $x=22-97b,b\in \mathbb{Z^{+}}$ örneğini verebiliriz, bu da bize eşlemenin en az $1$ doğrudan kökü olduğunu gösterirdi. Her ne kadar bu örnek mevcut olsa da, bu örneği bulmanın zorluğu dolayısıyla bu ifadeyi genel olarak ispatlamakta fayda görüyorum.

Şimdi Varsayalım ki eşlemeyi doğru kılan bir $\psi^{\mathbb{T}}$ grubu ve $n$ tamsayısı olmasın, O halde ifademiz $4c+3$ şeklinde bir asal sayı veya herhangi bir asal olmayan pozitif tamsayıya eşit olabilir.

$|2\psi^{\mathbb{T}}-n|= \xi >k $ olsun,  $n=2\psi^{\mathbb{T}}- \xi$ Buradan $(2\psi^{\mathbb{T}}-\xi)k-1=x^2$ olur. $x^2\ge 0$ olduğundan dolayı ,$ (2\psi^{\mathbb{T}}-\xi)k-1\ge 0$ olmalı. Burayı da işlemimizin tanım  kümesini sade bırakacak şekilde düzenlersek,

$\psi^{\mathbb{T}}\ge \dfrac{k\xi+1}{2k}$ şeklinde bir ifadeye eşit olmalıdır. Fakat ispatımıza başlarken yaptığımız tanımdan dolayı bu mümkün değildir. Çelişki ! İspat biter $\blacksquare$

Teorem 3
$\psi\{n\}\longrightarrow \psi\{|\psi^{\mathbb{T}}(1-l)-n|\} \longrightarrow \mathbb{P}_{1 \mod4}$ eşlemesi birebirdir.

İspat: Burada $l=2$ alalım. Düzenlersek, $\psi^{\mathbb{T}}+n \longrightarrow \mathbb{P}_{1 \pmod4}$ olur. Bu eşlemenin Doğruluğu Teorem $2$ den doğrudur. Ayrıca bu eşlemenin birebirliği de Teorem $1$ den doğrudur. $\blacksquare$

Teorem 4
$n\longrightarrow \mathbb{P}_{1\pmod4}$ eşlemesi doğrudur.

ispat: Teorem $3$ ten $\psi\{n\}\longrightarrow \mathbb{P}_{1 \pmod4}$ olduğunu biliyoruz. Teorem $1$ in ispatından da $\psi\{n\}\longrightarrow n$ olduğunu ve bu eşlemenin birebir olduğunu biliyoruz. İspat biter. $\blacksquare$

Sonuç olarak $n$ sayımızı $\mathbb{P}_{1 \pmod4}$ kümesinin içinde almamız gerektiğini anlıyoruz. Böylece Teorem $2$ nin ispatında verdiğimiz örneği yineleyerek, cevabımızı $97$ olarak işaretliyoruz.
Sıradan bir matematikçi...

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3199
  • Karma: +22/-0
  • İstanbul
Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
« Yanıtla #8 : Mayıs 02, 2017, 05:03:44 öö »
Yanıt: $\boxed{A}$

burada ispatladığımız Teorem 1'den dolayı $n=97$ asalı için çözüm vardır.
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


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