KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 March 2017.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4857.
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

  • Támogatóink:   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