Feladat:	B.4409	Korcsoport: 14-15	Nehézségi fok: átlagos
Megoldó(k):	Kulcsár Ildikó
Füzet:	2014/május, 272 - 273. oldal		PDF  |  MathML
Témakör(ök):	Maradékos osztás, Prímszámok, Feladat
Hivatkozás(ok):	Feladatok: 2011/december: B.4409

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. Tudjuk, hogy $n$ pozitív egész, $2^n+1$ pedig prímszám. Ha létezne olyan $p$ páratlan prímszám, amelyre $p\mid n$, akkor lenne olyan $x\in \text{N}$, hogy $n=p\cdot x$. Így $2^n+1=2^{p\cdot x}+1={\left(2^x\right)}^p+1^p$. Az ismert azonosság alapján $\begin{array}{c}{\displaystyle 2^x+1\mid {\left(2^x\right)}^p+1^p\mathrm{,}}\end{array}$ és $1<2^x+1<2^n+1$, tehát valódi osztó, így ekkor $2^n+1$ nem lehetne prímszám. Ellentmondásra jutottunk, tehát $n$-nek nem lehet páratlan osztója, így $n=2^k$ alakú szám. Vizsgáljuk meg az ilyen alakú kitevők esetén a maradékokat 240-el osztva: ${\displaystyle \begin{array}{ccc}\hfill {\displaystyle 2^{2^0}+1}& {\displaystyle =}\hfill & {\displaystyle 3\equiv 3\left(\text{mod}240\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 2^{2^1}+1}& {\displaystyle =}\hfill & {\displaystyle 5\equiv 5\left(\text{mod}240\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 2^{2^2}+1}& {\displaystyle =}\hfill & {\displaystyle 17\equiv 17\left(\text{mod}240\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 2^{2^3}+1}& {\displaystyle =}\hfill & {\displaystyle 257\equiv 17\left(\text{mod}240\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle 2^{2^4}+1}& {\displaystyle =}\hfill & {\displaystyle 65537\equiv 17\left(\text{mod}240\right)\mathrm{.}}\hfill \end{array}}$ Sejtés: ezután mindig 17 lesz a maradék. $\begin{array}{c}{\displaystyle 240=2^4\cdot 3\cdot 5.}\end{array}$ Tehát azt kell megvizsgálnunk, hogy a $2^{2^k}+1$ alakú számok milyen maradékot adnak $2^4$-nel, 3-mal és 5-tel osztva. Legyen $A=2^{2^k}+1$. Ha $k\ge 2$, akkor $2^4\mid 2^{2^k}$, így $2^4\mid A-1\Rightarrow 2^4\mid A-1-16\Rightarrow 2^4\mid A-17$. ${\displaystyle \begin{array}{c}\hfill {\displaystyle A=2^{2^k}+1={\left(3-1\right)}^{2^k}+1\equiv {\left(-1\right)}^{2^k}+1\equiv 2\left(\text{mod}3\right)\Rightarrow }\hfill \\ \hfill {\displaystyle \Rightarrow 3\mid A-2\Rightarrow 3\mid A-2-15\Rightarrow 3\mid A-17.}\hfill \end{array}}$ A 2-hatványok végződései pozitív kitevő esetén rendre 2, 4, 8, 6, 2, 4, 8, 6 stb. Tehát $A=2^{2^k}+1$ végződése 7, így $A-17$ végződése 0, vagyis $5\mid A-17$. Így $k\ge 2$ esetén a $2^n+1$ prímszámnak mindig 17 lesz a maradéka 240-nel osztva. Tehát 3, 5 és 17 lehet a maradék.