Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4309. (November 2010)

B. 4309. Find the smallest possible positive integer n for which 32n-1 is divisible by 22010?

(4 pont)

Deadline expired on December 10, 2010.


Sorry, the solution is available only in Hungarian. Google translation

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}\).


Statistics:

70 students sent a solution.
4 points: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 points:Á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 points:6 students.
1 point:10 students.
0 point:7 students.
Unfair, not evaluated:4 solutionss.

Problems in Mathematics of KöMaL, November 2010