Tübitak Lise 2. Aşama 2011 Soru 4

[geo]

• Tweet

$a_{1}=5$ ve $n\ge 1$ için, $a_{n+1}=a_{n}^{3}-2a_{n}^{2}+2$ olsun. $p\equiv 3 \pmod 4$ koşulunu sağlayan bir $p$ asal sayısı $a_{2011}+1$ sayısını bölüyorsa, $p=3$ olduğunu kanıtlayınız.

(Fehmi Emre Kadan)

[geo]

• Tweet

(Muhammed Zahid ÖZTÜRK)

$\forall n$ için $a_n+1$ in $4k+3$ formunda bir asal böleni var ise 3 olduğunu gösterelim.

$a_{n+1}-2=a_n^3-2a_n^2$
$\Leftrightarrow \dfrac{a_{n+1}-2}{a_n-2}=a_n^2$
$\Rightarrow \dfrac{a_{n+1}-2}{a_n-2} \cdot \dfrac{a_n-2}{a_{n-1}-2} \cdots \dfrac{a_2-2}{a_1-2}=a_n^2\cdot a_{n-1}^2\ldots a_1^2$
$\Rightarrow \dfrac{a_{n+1}-2}{3}=a_n^2\cdot a_{n-1}^2\ldots a_1^2$
$\Rightarrow a_{n+1}+1=3\left[a_n^2\cdot a_{n-1}^2\ldots a_1^2+1\right].$

$p | a_{n+1}+1 \Rightarrow p|3$ ya da $p|a_n^2\cdot a_{n-1}^2\ldots a_1^2+1.$

İlk durumda $p=3$ olmak zorunda.

İkinci durumda,
$(a_n\cdot a_{n-1}\ldots a_1)^2 \equiv -1 (\mod  p)$
$\Rightarrow \left[(a_n\cdot a_{n-1}\ldots a_1)^2\right]^{\frac{p-1}{2}} \equiv (-1)^\frac{p-1}{2} (\mod p)$
$\Rightarrow 1 \equiv (-1)^\frac{p-1}{2} (\mod p)$
$\dfrac{p-1}{2}$ çift olmalıdır. Öyleyse $p=4k+1$ formuda olmak zorundadır, $4k+3$ formunda olamaz.

[alpercay]

• Tweet

Kaynak: 2011 Lise olimpiyatı 2. Aşama Sınavı

[Lokman Gökçe]

• Tweet

2011 Lise olimpiyatı 2. Aşama Sınavı başlığı altında 24 Aralık 2011'de gönderdiğim çözümü $\LaTeX$ kullanarak yeniden gönderiyorum. (Hatırlattığı için Alper Çay bey'e teşekkürler.) Temelde; verilen diğer çözüm, benim çözümümle aynıdır.


Çözüm [Lokman GÖKÇE]: Verilen bağıntıyı düzenlersek $a_{n+1} - 2 = a_n^2(a_n - 2) $ olup $\dfrac{a_{n+1} - 2}{a_n - 2} = a_n^2 $ yazılır. Şimdi $n$ ye $1$ den $2010$ a kadar değer vererek elde edilen ifadeleri taraf tarafa çarparsak, eşitliğin sol tarafı bir teleskopik çarpım olduğundan $\dfrac{a_{2011} - 2}{a_1 - 2} = a_1^2\cdot a_2^2 \cdots a_{2010}^2$ olur. Bir $x$ tam sayısı için $ a_1^2\cdot a_2^2 \cdots a_{2010}^2 = x^2$ olarak yazılabilir. $a_1=5$ olduğundan $a_{2011} - 2 = 3x^2$ olup
$$a_{2011} + 1 = 3(x^2 + 1)$$
bulunur. $a_{2011} + 1$ sayısının $p=3$ asalına bölündüğü açıktır.

Koşullara uygun başka $p$ asalı olmadığını ispatlamak için çelişki metodunu kullanalım. $p\equiv 3 \pmod{4}$ ve $p\neq 3$ olan bir $p$ asalı için $p\mid (a_{2011} + 1) $ olduğunu kabul edelim. Bu durumda $p\mid 3(x^2 + 1)$ olup $p\neq 3$ olduğundan $p \mid (x^2 + 1)$ dir. Dolayısıyla $x^2 \equiv -1 \pmod{p}$ dir. Fakat kare kalanlar ve Legendre sembolü için temel bir özellik olarak $p\equiv 3 \pmod{4}$ formunda bir asal sayı iken $\left( \dfrac{-1}{p}\right) = -1$ dir. Yani $x^2 \equiv -1 \pmod{p}$ denkliğini sağlayan $x$ tam sayısı yoktur, çelişki! İspatı için 4n+1 Asal bağlantısına bakılabilir. O halde $p\mid (a_{2011} + 1) $ ve $p\equiv 3 \pmod{4}$ koşullarına uygun biricik asal sayı $p=3$ tür.