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

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.

Problems in Mathematics of KöMaL, February 2017