Geomania.Org Forumları

Yarışma Soruları => Tübitak Lise 1. Aşama => 2003 => Konuyu başlatan: geo - Mayıs 06, 2014, 11:42:12 ös

Başlık: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: geo - Mayıs 06, 2014, 11:42:12 ös

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}
$

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: Dogukan6336 - Nisan 30, 2017, 09:05:41 ös

Teorem 1:

$p$ asal sayı ve $(a,b) = \text{OBEB}(a,b)=1$ olmak üzere $x^n \equiv a \pmod p$ olsun. Eğer $ a^{\dfrac {p-1} {(n,p-1)}} \not\equiv  1 \pmod 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 \pmod 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 \pmod 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 $\bmod p$ deki mertebesi $p-1$ olsun. Ayrıca

$$g^j \equiv a \pmod p$$ olsun ve bu denkliği sağlayan en küçük üs $j$ olsun.

$$g^{j(\dfrac {p-1} {d})}\equiv 1 \equiv g^0 \pmod p$$
$$\dfrac {j(p-1)} {d}\equiv 0 \pmod {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, \dots, g^{p-1}$ sayıları $p$ modülüne göre bir asal kalan sistemi oluştururlar.

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

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

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: Eray - Nisan 30, 2017, 09:44:46 ös

Alıntı yapılan: Dogukan6336 - Nisan 30, 2017, 09:05:41 ö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

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: Dogukan6336 - Nisan 30, 2017, 10:00:25 ös

Alıntı yapılan: Eray - Nisan 30, 2017, 09:44:46 ös

Alıntı yapılan: Dogukan6336 - Nisan 30, 2017, 09:05:41 ö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.

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: Eray - Mayıs 01, 2017, 12:19:15 öö

Alıntı yapılan: Dogukan6336 - Nisan 30, 2017, 10:00:25 ös

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 :)

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: Dogukan6336 - Mayıs 01, 2017, 12:27:47 öö

Alıntı yapılan: Eray - Mayıs 01, 2017, 12:19:15 öö

Alıntı yapılan: Dogukan6336 - Nisan 30, 2017, 10:00:25 ös

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.

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: ArtOfMathSolving - Mayıs 01, 2017, 05:09:18 ös

İ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.

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.

Başlık: Ynt: Tübitak Lise 1. Aşama 2003 Soru 22
Gönderen: Lokman Gökçe - Mayıs 02, 2017, 04:03:44 öö

Yanıt: $\boxed{A}$

burada (http://geomania.org/forum/index.php?topic=6154.0) ispatladığımız Teorem 1'den dolayı $n=97$ asalı için çözüm vardır.