Feladat:	B.4857	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Andó Angelika ,  Baran Zsuzsanna ,  Borbényi Márton ,  Csahók Tímea ,  Daróczi Sándor ,  Döbröntei Dávid Bence ,  Gáspár Attila ,  Győrffy Ágoston ,  Imolay András ,  Janzer Orsolya Lili ,  Kerekes Anna ,  Mikulás Zsófia ,  Németh Balázs ,  Saár Patrik ,  Schrettner Jakab ,  Simon Dániel Gábor ,  Szakály Marcell ,  Tóth Balázs ,  Tóth Viktor ,  Weisz Máté ,  Zólomy Kristóf
Füzet:	2017/szeptember, 346 - 347. oldal		PDF  |  MathML
Témakör(ök):	Feladat, Oszthatóság, Magasabb fokú kongruenciák
Hivatkozás(ok):	Feladatok: 2017/február: B.4857

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Megoldás. Legyen $p$ tetszőleges, $2$-nél nagyobb prím. Vizsgáljuk a $\begin{array}{c}{\displaystyle 2^{2^1}\mathrm{,}{2}^{2^2}\mathrm{,}{2}^{2^3}\mathrm{,}\text{...}}\end{array}$ számok $p$-vel való osztási maradékát. Ezek a számok sorban egymás négyzetei, hiszen $\begin{array}{c}{\displaystyle {\left(2^{2^n}\right)}^2=2^{2^{n+1}}\mathrm{.}}\end{array}$ Ha valamelyikük maradéka $-1$, akkor a következőé ${\left(-1\right)}^2=1$, és az összes többié is $1$. Ebből következik, hogy a $\left(-1\right)$-es maradék legfeljebb egyszer fordulhat elő. Tegyük fel, hogy előfordul, azaz $2^{2^m}\equiv -1\left(\text{mod}p\right)$, másszóval $p\mid 2^{2^m}+1$. Megmutatjuk, hogy ekkor $m<p$. Tételezzük fel ugyanis, hogy $m\ge p$. Akkor előtte legalább $p-1$ maradék volt, de egyik sem lehet 0, (mert egy kettőhatványt nem oszthat egy páratlan prím), továbbá egyik sem lehet $-1$, hiszen csak az $m$-edik $-1$. Így az összes maradék közül csak $\left(p-2\right)$-féle lehet előtte, ezért a skatulyaelv miatt lesz két megegyező maradék, mondjuk az $s$-edik és a $t$-edik, ahol $1\le s<t<m$. Ekkor, mivel egymás után egymás négyzetei vannak, és egy szám négyzetének $p$-vel való maradéka a szám $p$-vel való maradéka négyzetének a $p$-vel való maradéka, azért az $\left(s+1\right)$-edik és a $\left(t+1\right)$-edik maradékok is megegyeznek egymással, ugyanezért az $\left(s+2\right)$-edik és a $\left(t+2\right)$-edik is stb. Így azonban az $m-\left(t-s\right)$-edik maradék megegyezne az $m$-edikkel, vagyis mindkettő $\left(-1\right)$ lenne, ami lehetetlen. Tehát valóban $m<p$. Tegyük fel, hogy egy $n\mathrm{,}k$ számpárra $nk\mid \left(2^{2^n}+1\right)\left(2^{2^k}+1\right)$; szimmetria miatt feltehetjük, hogy $n\le k$. Ha $n>1$, akkor legyen $p$ az $n$ egyik prímtényezője. Nyilván $p\ne 2$, hiszen $\left(2^{2^n}+1\right)\left(2^{2^k}+1\right)$ páratlan. Mivel $p\le n\le k$, a fentiek szerint sem $2^{2^n}+1$, sem pedig $2^{2^k}+1$ nem lehet $p$-vel osztható, de akkor a szorzatuk sem, ami ellentmondás; így szükségképpen $n=1$. Tegyük fel, hogy $k>1$, és az egyik prímosztója $p$. A fenti esethez hasonlóan $p>2$, és $p\le k$ miatt $p$ nem osztja a $2^{2^k}+1$ tényezőt. Ezért $p\mid k\mid \left(2^{2^n}+1\right)\left(2^{2^k}+1\right)$ csak úgy lehetséges, hogy $p\mid 2^{2^n}+1=5$, ezért ‐ mivel $k$ minden prímtényezője relatív prím $2^{2^k}+1$-hez ‐ $k\mid 5$. Tehát a lehetséges számpárok (a sorrendet is figyelembe véve): $\left(\mathrm{1,1}\right)$, $\left(\mathrm{1,5}\right)$, $\left(\mathrm{5,1}\right)$, amik valamennyien teljesítik is a feladat feltételét.