 |
A B. 4409. feladat (2011. december) |
B. 4409. Tegyük fel, hogy az n pozitív egész számra 2n+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