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

 

Problem B. 4857. (February 2017)

B. 4857. Determine all pairs \(\displaystyle (n,k)\) of positive integers for which \(\displaystyle \big(2^{2^n}+1\big)\big(2^{2^k}+1\big)\) is divisible by \(\displaystyle nk\).

(Bulgarian problem)

(6 pont)

Deadline expired on March 10, 2017.


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

Megoldás. Tegyük fel, hogy \(\displaystyle nk \mid \left(2^{2^n}+1\right)\left(2^{2^k}+1\right)\). A szimmetria miatt feltehetjük, hogy \(\displaystyle k\leq n\). Tegyük fel, hogy a \(\displaystyle p\) prím osztja \(\displaystyle \left(2^{2^n}+1\right)\)-et. Ekkor \(\displaystyle p\) páratlan, továbbá

\(\displaystyle 2^{2^n}\equiv -1 \pmod{p},\)

így ennek a kongruenciának a négyzete is teljesül:

\(\displaystyle 2^{2^{n+1}}\equiv 1 \pmod{p}.\)

Így a 2 rendje (mod \(\displaystyle p\)) osztója \(\displaystyle 2^{n+1}\)-nek. (https://hu.wikipedia.org/wiki/Multiplikat%C3%ADv_rend) Azonban \(\displaystyle 2^1, 2^2, 2^{2^2},\dots, 2^{2^n}\) egyike sem kongruens 1-gyel (mod \(\displaystyle p\)), hiszen akkor \(\displaystyle 2^{2^n}\equiv 1\pmod {p}\) lenne. Tehát 2 rendje (mod \(\displaystyle p\)) \(\displaystyle 2^{n+1}\). A kis Fermat-tétel szerint \(\displaystyle 2^{p-1}\equiv1 \pmod {p}\), ezért \(\displaystyle 2^{n+1}\mid p-1\), amiből speciálisan az is következik, hogy \(\displaystyle 2^{n+1}<p\). Így \(\displaystyle k\leq n<2^{n+1}<p\) miatt \(\displaystyle (p,nk)=1\). Mivel \(\displaystyle p\) a \(\displaystyle 2^{2^n}+1\) szám tetszőleges prímosztója, ezért ez egyben azt is jelenti, hogy \(\displaystyle (2^{2^n}+1,nk)=1\).

Vagyis \(\displaystyle nk \mid \left(2^{2^n}+1\right)\left(2^{2^k}+1\right)\) pontosan akkor teljesül, ha \(\displaystyle nk \mid \left(2^{2^k}+1\right)\). Az előzőhöz hasonló gondolatmenet alapján viszont \(\displaystyle (k,2^{2^k}+1)=1\), így csak \(\displaystyle k=1\) lehet. Ekkor \(\displaystyle n\mid 2^{2^k}+1=5\) pontosan akkor teljesül, ha \(\displaystyle n\in\{1,5\}\).

Tehát a feltételnek eleget tevő számpárok: \(\displaystyle (1,1); (1,5); (5,1)\).


Statistics:

33 students sent a solution.
6 points:Andó Angelika, Baran Zsuzsanna, Borbényi Márton, Csahók Tímea, Daróczi Sándor, Döbröntei Dávid Bence, Gáspár Attila, Győrffy Ágoston, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Mikulás Zsófia, Németh 123 Balázs, Saár Patrik, Schrettner Jakab, Simon Dániel Gábor, Szakály Marcell, Tóth 827 Balázs, Tóth Viktor, Weisz Máté, Zólomy Kristóf.
5 points:Kovács 246 Benedek, Kővári Péter Viktor, Márton Dénes.
3 points:3 students.
1 point:3 students.
0 point:3 students.

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