6-th Czech-Slovak Match

We first show that if $2^n-1$ is a divisor of $m^2+9$ for some number $m$, then $n$ is the power of number 2. Otherwise the $n$ has some odd divisor $\ell \ge 3$ and so $2^{\ell }-1$ is a divisor of $m^2+9$ because $2^{\ell }-1$ divide $2^n-1$. But for $\ell \ge 3$ we have $2^{\ell }-1\equiv -1(\mathrm{mod}4)$, and therefore the $2^{\ell }-1$ has prime divisors $p$ such that the $p\equiv -1(\mathrm{mod}4)$. Firstly, we deal with $p\ne 3$. Since $p\mid m^2+3^2$ by Fermat little theorem we have $$1\equiv m^{p-1}\equiv (m^2{)}^{(p-1)/2}\equiv (-9{)}^{(p-1)/2}\equiv (-1{)}^{(p-1)/2}\cdot 3^{p-1}\equiv -1(\mathrm{mod}p)$$ But this is impossible, so $p=3$. But then for odd $\ell$ we have $2^{\ell }\equiv -1\not\equiv -1(\mathrm{mod}3)$, which is a contradiction. Consider $n=2^k$ now. For $n=1$, the claim is true. If $k\ge 1$ then $$2^n-1=3(2^2+1)(2^{2^2}+1)\cdots (2^{2^{k-1}}+1)$$ Therefore, if $2^n-1$ divides $m^2+9$, also $2^{\ell }+1$ divides $m^2+9$ for each $\ell =1,2,\dots ,k-1$. Moreover if $\alpha \ne \beta$ the numbers $2^{2\alpha }+1$ and $2^{2\beta }+1$ are relatively prime because if $d>2$ is the greatest common divisor and $\alpha >\beta$, then $$-1\equiv 2^{2\alpha }\equiv (2^{2\beta }{)}^{2^{\alpha -\beta }}\equiv 1(\mathrm{mod}d)$$ which is a contradiction. So it is necessarily $d=1$ ($d\ne 2$, because both are odd). Then, according to the Chinese remainder theorem there is a natural number $c$ such that $$c\equiv 2^{2\ell }(\mathrm{mod}{2}^{2^{\ell +1}}),\forall \ell =0,1,\dots ,k-2$$ Then $c^2+1\equiv 0(\mathrm{mod}{2}^{2\ell +1})$ for $\ell =0,1,\dots ,k-2$, and thus $2^n-1$ divides $(3c{)}^2+9$. $\square$

---

Alternative solution.

We claim that, if $2^n-1$ divides $m^2+9$ for some $m\in \mathbb{N}$, then $n$ must be a power of 2. Suppose otherwise that $n$ has an odd divisor $d>1$. Then $2^d-1\mid 2^n-1$ is also a divisor of $m^2+9=m^2+3^2$. However, $2^d-1$ has some prime divisor $p$ of the form $4k-1$, and by a well-known $p$ divides both $m$ and 3. Hence $p=3$ divides $2^d-1$, which is impossible because, for $d$ odd, $2^d\equiv 2(\mathrm{mod}3)$. Hence $n=2^r$ for some $r\in \mathbb{N}$. Now let $n=2^r$. We prove the existence of $m$ by induction on $r$. The case $r=1$ is trivial. Now for any $r>1$ note that $$2^{2r}-1=(2^{2^{r-1}}-1)(2^{2^{r-1}}+1)$$ The induction hypothesis claims that there exists an $m_1$ such that $2^{2^{r-1}}-1\mid m_1^2+9$. We also observe that $2^{2^{r-1}}+1\mid m_2^2+9$ for simple $m_2=3\cdot 2^{2^{r-2}}$. By the Chinese remainder theorem, there is an $m\in \mathbb{N}$ that satisfies $m\equiv m_1(\mathrm{mod}{2}^{2^{r-1}}-1)$ and $m\equiv m_2(\mathrm{mod}{2}^{2^{r-1}}+1)$. It is easy to see that this $m^2+9$ will be divisible by both $2^{2^{r-1}}-1$ and $2^{2^{r-1}}+1$. This completes the induction. $\square$