A B. 4409. feladat (2011. december)

B. 4409. Tegyük fel, hogy az n pozitív egész számra 2ⁿ+1 prím. Milyen maradékot adhat ez a prím 240-nel osztva?

(4 pont)

A beküldési határidő 2012. január 10-én LEJÁRT.

Megoldás. Legyen $\displaystyle n=2^km$, ahol $\displaystyle m$ páratlan szám. Ha $\displaystyle m\ne 1$, akkor $\displaystyle a+b\mid a^m+b^m$ miatt $\displaystyle 2^n+1$ osztható a nála kisebb, de 1-nél nagyobb $\displaystyle 2^{2^k}+1$ számmal, vagyis nem lehet prím. Ezért $\displaystyle n=2^k$, valamely nemnegatív $\displaystyle k$ egész számmal. A $\displaystyle k=0$, $\displaystyle k=1$ és $\displaystyle k=2$ esetekben rendre az $\displaystyle n=3$, $\displaystyle n=5$, illetve $\displaystyle n=17$ prímszámokat kapjuk. Megmutatjuk, hogy $\displaystyle k\ge 2$ esetén a maradék mindig 17 lesz. Valóban, ha $\displaystyle k\ge 2$ akkor $\displaystyle n-17=2^{2^k}-16=16\cdot (2^{2^k-4}-1)$. Mivel itt a $\displaystyle 2^k-4$ kitevő osztató 4-gyel, a $\displaystyle 2^{2^k-4}-1$ szám osztható a $\displaystyle 2^4-1=15$ számmal. Ezért $\displaystyle n-17$ valóban osztható lesz 240-nel.A lehetséges maradékok tehát 3, 5, illetve 17.

Statisztika:

119 dolgozat érkezett.
4 pontot kapott:	73 versenyző.
3 pontot kapott:	22 versenyző.
2 pontot kapott:	6 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	10 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2011. decemberi matematika feladatai