Let $2^a||m^h-1$ and $2^b||k$. Then $2^{a-b}||\frac{m^h-1}{k}$, so since $m$ divides $n^{\frac{m^h-1}{k}}+1$ there is a residue modulo $m$ of order $2^{a-b+1}$, it easily follows that $2^{a-b+1}$ divides $p-1$ for every prime divisor of $m$, and hence $2^{a-b+2}|m^2-1$. By induction on $r$, we can prove that $2^t||m^h-1$ iff and only iff $2^t||(m^2-1)2^{r-1}$ so we get that: $a-b+2+r-1$ is at most $a$, so from here it follows that $b\geq r+1$. We prove this is a sufficient condition. Let $k=2^{r+1+t}h$ with $h$ odd. Iff t is not $0$, then choose an $m$ such that $2^{t+2}$ is the max power of 2 dividing $m^2-1$ and also such that $h|m-1$, and put $n=m+1$, in this case everything works. iff $t=0$, let $p$ be a prime of the form $8j+5$, and such that $h|p-1$, then there exist an $n$, such that $n^2+1$ is a multiple of $p$, so this $n$ works!

Pascual2005 haven't considered the case when $ k$ is odd, but of course every odd $ k$ works, since we can take $ m=k+1$ and $ n=m-1$.

orl wrote: For any $ h = 2^{r}$ ($ r$ is a non-negative integer), find all $ k \in \mathbb{N}$ which satisfy the following condition: There exists an odd natural number $ m > 1$ and $ n \in \mathbb{N}$, such that $ k \mid m^{h} - 1, m \mid n^{\frac {m^{h} - 1}{k}} + 1$. The proof is rather long and complicated,but it is not that difficult

Attachments:

How about writing it in English and maybe $ \text{\LaTeX}$ here?

orl wrote: How about writing it in English and maybe $ \text{\LaTeX}$ here? Thank you for your advice But the above documents were taken from my notebook(I wrote it down last year not today)If anyone had any questions,I would like to explain.

This is my solution. I hope it's right. Firstly, setting $ k=2^{b}q$ with$ gcd(2;q)=1.$ Case 1: $ b \ge r + 2$ Applying Chinese remainder theorem, exist $ m \in N$; $ m$ is odd such that $ q| {m - 1} $and $ 2^{b - r} \| {m - 1} $ From that, we have $ v_2 (m^h - 1) = r - 1 + v_2 (m^2 - 1) = r - 1 + b - r + 1 = b = v_2 (k)$ So, $ \frac{{m^h - 1}}{k}$ is odd and we only choose $ n\in N$ such that $ m| {n+1}.$ Case 2:$ 1\le b \le r + 1.$ Setting$ m^h-1=k.N$. Suppose that $ N=2^u.M ( gcd(2;M)=1).$ We have $ u + b = r - 1 + v_2 (m^2 - 1).$ If exist $ n$ such that $ m| {n^N+1}$ then $ m| {(n{}^2{}^{u})^M+1}$. So$ v_p (m) \le v_p (M) + v_p (n{}^{2{}^u } + 1) = v_p (n{}^{2{}^u } + 1) \Rightarrow m| {n{}^{2{}^u } + 1} $. From that, we can easily see that$ m \equiv 1(\bmod 2^{u + 1} )$. So $ v_2 (m^2 - 1) \ge u + 2 \Rightarrow b \ge r + 1$. Thus, $ k=2^{r+1}q$. We choose $ m \in N$; $ m$ is odd such that $ q| {m - 1} $ and $ 2^{b - r} \| {m - 1} $ Then $ v_2 (\frac{{m^h - 1}}{k}) = 2.$ Setting $ \frac{{m^h - 1}}{k}=2.N$ with$ N$ is odd. Because $ (-1/m)=1$ so exist $ n$ such that $ m| {n^2 + 1} | {n^{2N} + 1} $

We claim that $k$ works if and only if $2^{r+1}\mid k$. We divide the proof into two parts. Necessity: Let $A=\dfrac{m^{2^r}-1}{k}$ The main claim is Claim: $\nu_2(p-1)\geq\nu_2(A)+1$ for any prime divisor $p$ of $m$. Proof: Let $u=\mathrm{ord}_p(n)$. Then notes that $u\mid 2A$ but $u\nmid A$ (notice that $m$ odd). Therefore $\nu_2(u)=\nu_2(A)+1$. But $u\mid p-1$ so we are done. $\blacksquare$ Let $t=\nu_2(A)$. The claim implies $m\equiv 1\pmod{2^{t+1}}$. However, by LTE, \begin{align*} t &= \nu_2(m^{2^r}-1)-\nu_2(k) \\ &= \nu_2(m-1)+\nu_2(m+1)+r-1-\nu_2(k) \\ &\geq (t+1)+1+r-1-\nu_2(k) \end{align*}thus $\nu_2(k)\geq r+1$ as claimed. Sufficiency: By Dirichlet, take prime $p\equiv 1\pmod{4k}$ and $m=p$ so the first divisibility is clearly satisfied. Let $t=\nu_2((p^{2^r}-1)/k)$. Since $p+1\equiv 2\pmod 4$, we get \begin{align*}t &=\nu_2(p-1)+\nu_2(p+1)+r-1-\nu_2(k) \\ &= \nu_2(p-1)+(r-\nu_2(k))\end{align*}Thus $t+1\leq\nu_2(p-1)$. Since groups $\mathbb{Z}_p^{\times}$ and $\mathbb{Z}_{p-1}$ are isomorphic, there exists an element $n$ of $\mathbb{Z}_p^{\times}$ that has order $2^{t+1}$. This means $$n^{2^t}\equiv -1\pmod p\implies n^{(p^{2^r}-1)/k} = n^{2^t\cdot\text{odd}}\equiv -1\pmod p$$so this $m,n$ works.