A B. 4857. feladat (2017. február)

B. 4857. Határozzuk meg azokat az $\displaystyle (n,k)$ pozitív egészekből álló számpárokat, amelyekre $\displaystyle \big(2^{2^n}+1\big)\big(2^{2^k}+1\big)$ osztható $\displaystyle nk$-val.

Bolgár feladat

(6 pont)

A beküldési határidő 2017. március 10-én LEJÁRT.

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)$.

Statisztika:

33 dolgozat érkezett.
6 pontot kapott:	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 pontot kapott:	Kovács 246 Benedek, Kővári Péter Viktor, Márton Dénes.
3 pontot kapott:	3 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	3 versenyző.

A KöMaL 2017. februári matematika feladatai