KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 10 December 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 solutions.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley