Tübitak Lise 1. Aşama 2022 Soru 06

[matematikolimpiyati]

$a_1=12$ ve her $n=1,2,...,2021$ için $a_{n+1}=12^{a_n}$ koşulunu sağlayan bir $(a_n)$ tam sayı dizisi tanımlanıyor. $a_{2022}$ sayısının $67$ ile bölümünden kalan kaçtır?

$\textbf{a)}\ 1  \qquad\textbf{b)}\ 4  \qquad\textbf{c)}\ 9  \qquad\textbf{d)}\ 16  \qquad\textbf{e)}\ 25$

[Metin Can Aydemir]

Yanıt: $\boxed{E}$

Hesaplamalarımız yüksek kuvvetli üslü sayılarla alakalı olduğundan "indeks" kavramını kullanmamız iyi olacaktır (Bu terimin halihazırda kullanımda olan türkçe karşılığı varsa belirtirseniz sevinirim). Bunun için öncelikle ilkel kök bulmalıyız. En küçük ilkel kök adayı $2$'den başlarsak $67-1=66=2\cdot 3\cdot 11$ olduğundan $2^{\frac{66}{11}}$, $2^{\frac{66}{3}}$ ve $2^{\frac{66}{2}}$ sayılarının  $67$ modunda $1$'e denk olmadığını göstermemiz ilkel kök olması için yeterlidir. Bunlar kolay hesaplamalar olduğundan burada yapmıyorum. $2$'nin bir ilkel kök olduğu bulunduğundan $2$'ye göre indeks alabiliriz. $$a_{2022}\equiv 12^{a_{2021}}\equiv x\pmod{67}\iff \text{ind}_2\left(12^{a_{2021}}\right)\equiv \text{ind}_2{x}\pmod{66}$$ İndeks kavramı ile logaritma benzer konsepte sahip terimlerdir ve çoğu özelliği ortaktır. $$\text{ind}_2\left(12^{a_{2021}}\right)\equiv a_{2021}\text{ind}_2\left(12\right)\equiv a_{2021}\left(\text{ind}_2\left(4\right)+\text{ind}_2\left(3\right)\right)\equiv a_{2021}\left(2+\text{ind}_2\left(3\right)\right)\pmod{66}$$ $\text{ind}_2\left(3\right)$'ü hesaplamak için normalde $2^k\equiv 3\pmod{67}$ olan bir $k$ sayısı bulmalıyız ve bu deneyerek hesaplaması uzun süren bir şey olabilir ama $2^6\equiv 64\equiv -3\pmod{67}$ olması ve $2$ ilkel kök olduğundan $2^{33}\equiv -1\pmod{67}$ olmasından dolayı $$2^{39}\equiv 3\pmod{67}\implies \text{ind}_2 3\equiv 39\pmod{66}$$ Buradan da $\text{ind}_2 x\equiv 41a_{2021}\pmod{66}$ bulunur. $a_{2021}$ sayısı $12$'nin bir kuvveti olduğundan $$a_{2021}\equiv 0\pmod{6}$$ $$a_{2021}\equiv 12^{a_{2020}}\equiv 1\pmod{11}$$ olacaktır. Çin kalan teoremiyle bu iki denkliği birleştirirsek $$a_{2021}\equiv 12\pmod{66}\implies \text{ind}_2x\equiv 41\cdot 12\equiv 30\pmod{66}\implies x\equiv2^{30}\pmod{67}$$ elde edilir. $$2^{30}\equiv 64^5 \equiv (-3)^5\equiv -243\equiv 25\pmod{67}$$ bulunur.

[Lokman Gökçe]

$a_{2022} = 12^{a_{2021}} \equiv x \pmod{67}$ diyelim. Fermat teoreminden $12^{66}\equiv 1 \pmod{67}$ olduğundan $a_{2021}=12^{a_{2020}}\equiv y \pmod{66}$ denkliği ile ilgilenmeliyiz. $66 \equiv 6\cdot 11$ dir. Burada ilginç bir şey oluşuyor. Her $n$ pozitif tam sayısı için
$$
\left\{
\begin{split}
 12^n  & \equiv 0 \pmod{6} \\
 12^n &\equiv 1 \pmod{11}
\end{split}
\right.
$$
olduğundan $12^n \equiv 12 \pmod{66}$ elde ediyoruz. Yani $12$ nin modülo $66$ içindeki (mertebesi demeyelim ama buna benzer bir terim kullanarak) periyodu $1$ dir, diyelim. Kendimden şüphe edip bir de $12^2 \equiv 144 \equiv 2\cdot 66 + 12 \equiv 12 \pmod{66}$ işlemiyle kontrol ediyorum. Bu da, yine her $n$ pozitif tam sayısı için $12^n \equiv 12 \pmod{66}$ olduğunu gösteriyor. Dolayısıyla, $a_{2021} = 66k + 12$ olacak şekilde bir $k$ pozitif tam sayısı vardır.

Böylelikle $a_{2020} = 12^{66k+12} = (12^{66})^k \cdot 12^{12} \pmod{67} \equiv 12^{12} \pmod{67}$ buluruz. $x \equiv 12^{12} \pmod{67}$ problemini çözeceğiz.

$12^{2} = 144 \equiv 10 \pmod{67}$
$12^{4} \equiv 10^2 \equiv 33 \pmod{67}$
$12^{8} \equiv 33^2 \equiv 1089 \equiv 17 \pmod{67}$
$x\equiv 12^{12} = 12^{8}\cdot  12^{4} \equiv 17 \cdot  33 \equiv 561 \equiv 25 \pmod{67}$ elde edilir.