The Problems of Ukrainian Authors

Let $p$ be some prime divisor of the number $2^{2^n}+1$. Consider numbers $x$ of the form $2^k$. By the statement of the problem we need $x^x-1=2^{2^s}-1\equiv 0(\mathrm{mod}p)$. If $s\ge n+1$ then $$2^{2^{2^k}}-1=(2^{2^{n+1}}{)}^{2^{2^k-(n+1)}}-1:2^{2^{n+1}}-1=(2^{2^k}-1)(2^{2^k}+1),$$ where $a:p$ denotes "a is divisible by $p",i.e.$p|a$.Thus$2^{2^k} - 1$isdivisibleby$p$.Soifallthenumbers$2^{2^{n+1}}, 2^{2^{n+2}}, \dots, 2^{2^{2008}}$arelessthan$p$,theproblemissolved.Thesolutionoftheproblemfollowsfromthelemma,statedbelow,for$A = 2^{2008}$.\ast \ast Lemma1.\ast \ast Foranypositiveintegernumber$A$thereexistssuch$n_0$thatallnumbersofakind$2^{2^n} + 1$,where$n \ge n_0$,haveprimedivisorgreaterthan$A \cdot 2^{2^n}$.Toprovelemma1,weneedanadditionallemma.\ast \ast Lemma2.\ast \ast Iftheprimenumber$p$isadivisorofthenumber$2^{2^n} + 1$,then$2^{n+1} \le p-1$.\ast Proof\ast (oflemma2).Let$\Delta$betheleastpositiveintegersuchthat$p|2^\Delta - 1$.Weshowthat$\Delta | p-1$.ItfollowsfromFerma{t}^{\prime }s(little)theoremthat$2^{p-1} \equiv 1 \pmod{p}$.Let$\Delta_1$betheremainderindivisionof$p-1$by$\Delta$.Thenfrom$2^\Delta \equiv 1 \pmod{p}$and$2^{p-1} \equiv 1 \pmod{p}$itfollowsthat$2^{\Delta_1} \equiv 1 \pmod{p}$.Fromthesuppositionofminimalityof$\Delta$itfollowsthat$\Delta_1 = 0$,i.e.$\Delta | p-1$.<br/><br/>$2^{2^{n+1}} - 1 = (2^{2^n} - 1)(2^{2^n} + 1)$,so$p \mid 2^{2^{n+1}}$.Reasoningbyanalogywiththeabove,onegets$\Delta \mid 2^{n+1}$,thatis$\Delta = 2^k$,$k \le n+1$.If$k \le n$then$2^{2^n} + 1 = (2^{2^k})^{2^n-2^k} + 1 \equiv 1^{2^n-2^k} + 1 \equiv 2 \pmod p$,whichisimpossibledueto$p \mid 2^{2^{n+1}}$.Hence$\Delta = 2^{n+1}$,which(with$\Delta \mid p-1$provenabove)finishestheproofofthelemma.\ast Proof\ast (oflemma1).Itfollowsfromlemma2thatallprimedivisorsofthenumber$2^{2^n} + 1$canbeexpressedas$2^{n+1} \beta_j + 1$.Let$2^{2n+2} < 2^{2^n}$(whichistruefor$n > 2$),then$2^{2^n} + 1 \equiv 1 \pmod{2^{2(n+1)}}$,hencewecangetfrom(1)$2^{n+1} \sum_{j=1}^s \alpha_j \beta_j \equiv 0 \pmod{2^{2(n+1)}}$,therefore$\sum_{j=1}^s \alpha_j \beta_j \equiv 0 \pmod{2^{n+1}}$.Notethat$\alpha_j > 0$and$\beta_j > 0$,so$\sum_{j=1}^s \alpha_j \beta_j \ge 2^{n+1}$.Supposethatall$\beta_j < A$(otherwise,whenoneofthe$\beta_j \ge A$,letitbe$\beta_{j_0}$,thenumber$2^{2^n} + 1$hasaprimedivisor$2^{n+1} \beta_{j_0} + 1 > 2^{n+1} A$andthelemmaisproved).Then$p_j$aredistinctnumbers,thusall$\beta_j$arealsodistinctnumbers,andthenumberof$\beta_j$is$s$.Bysuppositionall$\beta_j < A$,whenceweget$s < A$.So$2^{n+1} < A^2 \alpha_k$,thatis$\alpha_k > \frac{2^{n+1}}{A^2}$,butthen$p_k^{\alpha_k} = (2^{n+1} \beta_k + 1)^{\alpha_k} > (2^{n+1})^{\alpha_k} > 2^{(n+1)2^{n+1}/A^2}$.Since$p_k^{\alpha_k} \le 2^{2^n} + 1$,then$2^{(n+1)2^{n+1}/A^2} < 2^{2^n} + 1$.(2)Thereexistssuch$n_0$thatfor$n \ge n_0$wehave$\frac{n+1}{A^2} > 1$. Then it follows from (2) that $$2^{2^n}+1\ge 2^{(n+1)2^{n-1}/A^2}>2^{2^{n+1}}>2^{2^n}+1.$$ a contradiction, which proves the lemma.