Conjecture about natural number satisfying $ m(n)^k+1\space\mid\space n^{2k}+1 $

Solution 1:

If $n$ is not prime then $n=pm$ where $m=m(n)$ and $p$ is the smallest prime dividing $n$. Then the condition implies $$ m+1 \mid m^2p^2+1 $$ But $$ m+1 \mid (m+1)(m-1)p^2 = m^2p^2-p^2 $$ hence $$ m+1 \mid m^2p^2+1-(m^2p^2-p^2) = p^2+1 $$ and we must have $p^2\ge m$.

If $n\ne p^3$ then $m<p^2$. So $m$ cannot have two prime factors $\ge p$, but nor can it have any prime factors $<p$ since $p$ is the smallest prime factor of $n$. Hence $m$ must be prime.

Let $r>n$ be a prime with $\left(\frac{m}{r}\right)=-1$.$^\dagger$ Then by Euler's criterion $$ m^{\frac{r-1}{2}} \equiv -1 \pmod r \\ r \mid m^{\frac{r-1}{2}}+1 $$ But $$ n^{r-1}+1 \equiv 2 \pmod r $$ and hence $$ m^{\frac{r-1}{2}}+1 \not\mid n^{r-1}+1 $$

Hence if $n$ is not of the form $p$ or $p^3$ with $p$ prime, then the condition cannot be satisfied for all $k$.

$\dagger$ Given $m$ prime we can always find a prime $r>n$ with $\left(\frac{m}{r}\right)=-1$. Let $b$ be any quadratic nonresidue mod $m$. By the Chinese Remainder Theorem we can find $r_0$ with $r_0 \equiv 1 \pmod {4}$ and $r_0 \equiv b \pmod m$. Then by Dirichlet's theorem there is a prime $r>n$ with $r\equiv r_0 \pmod {4m}$, and by quadratic reciprocity $$ \left(\frac{m}{r}\right) = \left(\frac{r}{m}\right) = \left(\frac{b}{m}\right) = -1 $$