Three problems of one day of China TST was proposed by Mr.Feng(Feng Zuming),and this problem is one of the three. My Solution: Let ${p_i=2^{2^{i}}}+1,(i=0,1,2,3.4)$, $p_5=641$ $p_6|2^{2^{5}}+1, $,$p_6\not = 641$ then we choose k has the property $k\equiv 1 (mod p_i),i=0,...5,k \equiv -1( mod p_6)$ then for any positive integer $n=2^l*t,$,$t$ is odd if $l<=5$ then ${2^n k=(2^{2^l})^ t}k+1\equiv -k+1 \equiv 0 (mod p_l)$ if $l>= 6$ then $(2^{2^l})^t * k+1 \equiv k+1 \equiv 0 (mod p_6)$

Hawk Tiger, it seems that you solve completely other problem. As for Peter's problem, I have no idea.

Let p is odd prime and let $ T_p = 2^rm, \ m \ - \ odd$ is period for $ 2^n\mod p$. Let $ L_p$ period for $ 2^n\mod m$. If $ x_n = k*2^{2^n} + 1$, then $ x_{n + L_p}\equiv x_n\mod p$. If $ x_n = 0\mod p$ then for any s $ x_{n + sL_p} = 0\mod p$. Therefore sufficiently find one prime p and one n, suth that $ x_n = 0\mod p$. If $ k*2^{2^{n_0}} + 1 = P$ is prime, then $ p = P,n = n_0$ work.

Rust wrote: Let p is odd prime and let $ T_p = 2^rm, \ m \ - \ odd$ is period for $ 2^n\mod p$. Let $ L_p$ period for $ 2^n\mod m$. If $ x_n = k*2^{2^n} + 1$, then $ x_{n + L_p}\equiv x_n\mod p$. Why? I think, it is so if $ r\le n$.

Fedor Petrov wrote: Rust wrote: Let p is odd prime and let $ T_p = 2^rm, \ m \ - \ odd$ is period for $ 2^n\mod p$. Let $ L_p$ period for $ 2^n\mod m$. If $ x_n = k*2^{2^n} + 1$, then $ x_{n + L_p}\equiv x_n\mod p$. Why? I think, it is so if $ r\le n$. Yes. Let $ k=2^sk_1$, were $ k_1$ is odd. Let \[ P=k*2^{2^{n_0}}+1\] is prime. Then \[ m*2^r|k_1*2^{2^{n_0}+s}.\] It equavalent to $ m|k_1, r\le 2^{n_0}+s.$ Therefore \[ x_{n_0+lL_p}=k_12^{s+2^{n_0+lL_p}}+1=P+k*2^{2^{n_0}}(2^{2^{n_0}(2^{lL_p}-1)}-1).\] Because $ 2^{lL_p}-1=m*m_1$ we get \[ x_{n_0+lL_p}=x_{n_0}+(P-1)(2^{2^{n_0}mm_1}-1).\] If k is odd, then $ r\le 2^{n_0}$ or $ 2^{n_0}m=m_2T_p$. It give $ x_{n_0+lL_p}=x_{n_0}+(P-1)(2^{T_pm_1m_2}-1)=x_{n_0}\mod P.$ Therefore my solution work for odd k.

Rust wrote: If k is odd, then $ r\le 2^{n_0}$ or $ 2^{n_0}m = m_2T_p$. It give $ x_{n_0 + lL_p} = x_{n_0} + (P - 1)(2^{T_pm_1m_2} - 1) = x_{n_0}\mod P.$ Therefore my solution work for odd k. We need $ r\le n_0$, not $ r\le 2^{n_0}$. Because we need $ 2^r| 2^{n_0}$.

I give another solution. Let $ k=2^sk_1, \ k_1 \ - \ odd$ and p prime divisor of $ 2^tk_1+1$, suth that $ ord_2(p-1)\le t$. Let $ T_p$ is period $ 2^n\mod p$. Then $ p|k_12^{t+lT_p}+1$ for any integer $ l\ge 0$. Consider $ x_n=k*2^{2^n}+1=k_12^{s+2^n}+1$. We get $ p|x_n$ if $ T_p|2^n+s-t$. Let $ T_p=2^rm, \ m \ - \ odd$. We choose p, suth that $ r\le ord_2(p-1)\le t$. Wt need $ 2^r|s-t$. If s is odd, then take $ t=1$ we get $ 2^r|s-t$, because $ r\le t\le 1.$ And we get p is any prime divisor $ 2k_1+1$. If s even, we can not chose $ t=0$, because may be $ m+1$ is power of 2 (we need odd prime divisor p). But we can chose $ t=s$ for $ s>0$ (work any prime divisor k+1) and if $ s=0$ work $ p=x_n$. Then for $ L_p|\phi (m)$ we get $ p|x_{n_0+lL_p}$.

So, for odd $ k$ ($ s=0$) the solution is the same as earlier version? Then it looks that the same problem appears.

but I still can't catch the solution. Can you explain more about Tp is a divisor of 2^n+s--t? (sorry about awful latex)

Quote: but I still can't catch the solution. Can you explain more about $T_p$ is a divisor of $2^n+s-t$? (sorry about awful latex)