Tübitak Lise 1. Aşama 2024 Soru 22

[matematikolimpiyati]

$2^{22!}-1$ sayısını bölmeyen en küçük tek pozitif tam sayının rakamları toplamı kaçtır?

$\textbf{a)}\ 7  \qquad\textbf{b)}\ 9  \qquad\textbf{c)}\ 11  \qquad\textbf{d)}\ 13  \qquad\textbf{e)}\ 15$

[diktendik]

Yanıt : $\boxed{C}$

$22$ den küçük herhangi bir $x$ tamsayısı için $\phi(x)<22$ olacağından ve $2^{22!}\equiv 1 \pmod{x}$ olduğundan sayı $x$'e bölünür. (Euler teoreminden $a$, $x$ ile bölünmemek üzere $a^{\phi(x)}\equiv 1 \pmod{x}$ olduğundan). Bu yüzden bu sayı $22$'den büyüktür. $23$ asal olduğundan $\phi(23)=22$ olur. $22$ sayısı için $2^{22}\equiv 1$ ve $22$, $22!$'i böldüğünden sayı durumu sağlamaz. $25$ için euler değeri $20$ olur. Sağlamaz. $27,29,\cdots,43,45$ içinde durumun farklı olmadığı görülür. $47$ için $\phi(47)=46$ olduğundan $2^{46}\equiv 1 \pmod{47}$ olur. Wilson teoreminden $22!\equiv -1 \pmod{23}$ ve $22!$ çift olduğundan $22!\equiv 22 \pmod{46}$ elde edilir. Fermat teoreminden $2^{46} \equiv  1 \pmod{47}$ olduğundan $2^{22!}\equiv 2^{22}\pmod{46}$ olur. $2^{22!}\equiv 1\pmod{47}$ olsaydı $2^{22}\equiv 1\pmod{47}$ ve kare alıp $4$ ile çarpmayla $2^{46}\equiv 4$ olurdu. Halbuki $2^{46}\equiv 1\pmod{47}$ olduğu açıktır. Çelişki elde edilir. $47$ sayısı $2^{22!}-1$ sayısını bölmez. Cevap $4+7=11$ olur.

[Metin Can Aydemir]

Ocak ayından beri kendi yazdığım veya yarışmalardan topladığım güzel sayılar teorisi sorularını arşivliyorum. Bu soruya çok benzeyen

"$2n+3\mid 2^{n!}-1$ ancak ve ancak $n+1$ veya $2n+3$'den birisi bileşik sayıdır." sorusunu eklemiştim. HMMT'de bir sorunun çözümünde kullanılan bir lemmaydı (HMMT'nin açılımı yanlış bilmiyorsam Harvard-MIT Mathematics Tournament olması lazım). Gerçekten de $n=22$ için $47\nmid 2^{22!}-1$'dir çünkü hem $23$ hem de $47$ asal sayı.

$47$'den küçük tek sayılarda $\phi(k)\mid 22!$ çıktığından $k\mid 2^{22!}-1$ bulunuyor.