A B. 4309. feladat (2010. november)

B. 4309. Melyik az a legkisebb n pozitív egész szám, amelyre 3²ⁿ-1 osztható 2²⁰¹⁰-nel?

(4 pont)

A beküldési határidő 2010. december 10-én LEJÁRT.

Megoldás. Írjuk fel \(\displaystyle n\)-et \(\displaystyle 2^km\) alakban, ahol \(\displaystyle m\) páratlan szám. Szorzattá alakítva

\(\displaystyle 3^{2n}-1=3^{2^{k+1}m}-1=(3^{2^km}+1)(3^{2^km}-1)=\ldots=\)

\(\displaystyle =(3^{2^km}+1)(3^{2^{k-1}m}+1)\cdots(3^{2m}+1)(3^{m}+1)(3^{m}-1).\)

Itt minden szorzótényező páros. Mivel 3 hatványai felváltva adnak 3, illetve 1 maradékot 4-gyel osztva, ha \(\displaystyle \ell\) páratlan, akkor \(\displaystyle 3^\ell-1\), ha \(\displaystyle \ell\) páros, akkor pedig \(\displaystyle 3^\ell+1\) nem osztható 4-gyel. A fenti \(\displaystyle k+2\) tényezős szorzatnak tehát egyedül az utolsó előtti tényezője lehet osztható 4-gyel. Ez a tényező tényleg osztható 4-gyel, 8-cal viszont nem, hiszen 8-cal osztva

\(\displaystyle 3^{m}+1=3\cdot 9^{\frac{m-1}{2}}+1\)

4 maradékot ad. A szorzat tehát osztható \(\displaystyle 2^{k+3}\)-nal, de nem osztható \(\displaystyle 2^{k+4}\)-nel. A legkisebb megfelelő \(\displaystyle n\) számot ezek szerint a \(\displaystyle k=2007\), \(\displaystyle m=1\) választás eredményezi, amikor is \(\displaystyle n=2^{2007}\).

Statisztika:

70 dolgozat érkezett.
4 pontot kapott:	Baráti László, Beke Lilla, Böőr Katalin, Csuka Róbert, Damásdi Gábor, Dinev Georgi, Dolgos Tamás, Dudás 002 Zsolt, Fonyó Viktória, Hegedűs Csaba, Homonnay Bálint, Karl E. Holter, Kenéz Balázs, Klincsik Gergely, Kúsz Ágnes, Lenger Dániel, Machó Bónis, Máthé László, Nagy 111 Miklós, Nagy Róbert, Neukirchner Elisabeth, Perjési Gábor, Simig Dániel, Strenner Péter, Szabó 928 Attila, Tatár Dániel, Tossenberger Tamás, Varnyú József, Viharos Andor, Vuchetich Bálint, Weisz Gellért, Zilahi Tamás, Zsakó András.
3 pontot kapott:	Ágoston Péter, Csizmadia Luca, Czipó Bence, Énekes Péter, Maga Balázs, Mihálykó András, Nagy Balázs, Szilágyi Gergely Bence, Szórádi Márk, Zelena Réka.
2 pontot kapott:	6 versenyző.
1 pontot kapott:	10 versenyző.
0 pontot kapott:	7 versenyző.
Nem versenyszerű:	4 dolgozat.

A KöMaL 2010. novemberi matematika feladatai