A number of the type $m^2+9$ can, with exception of $p=3$, only have prime divisors $p \not \equiv -1 \mod 4$: If $q \equiv -1 \mod 4$ and $q \neq 3$, we have $3$ invertible $\mod q$ and get $m^\prime^2 \equiv -1 \mod q$ with $m^\prime \equiv m \cdot 3^{-1} \mod p$. But now we easily derive a contradiction with Fermat's little theorem: $1 \equiv m^\prime^{p-1} = (m^\prime^2)^\frac{p-1}2 \equiv (-1)^\frac{p-1}2 \equiv -1 \mod p$. Claim: exactly those $n$ being a power of two work. If $n$ has any odd prime divisor $q$, then $2^q-1 | 2^n-1$, so we just have to disprove the possibility of $2^q-1|m^2+9$ for $q$ any odd prime. Since $q>1$, $2^q-1 \equiv -1 \mod 4$, thus there is a prime $p \equiv -1 \mod 4$ dividing $2^q-1$. If we would have $p=3$, then $2^2 \equiv 1 \mod p$ yielding $1 \equiv 2^q \equiv 2^{q \mod 2} \equiv 2^1 \mod p$, impossible. Thus $p>3$, but now $p$ has to divide $m^2+9$, impossible by the above. We are left to prove that all $n=2^k$ work and do so by induction on $k$: $k=1$ gives the number $3$ which obviously works with $m_1=3$. If we have found $m_k$ with $m_k \equiv -9 \mod (2{}^{2{}^k}-1)$, we see that $2{}^{2{}^{k+1}}-1=(2{}^{2{}^k}+1)(2{}^{2{}^k}-1)$ and that these two factors are coprime. By the chinese remainder theorem we find $m_{k+1} \equiv m_k \mod (2{}^{2{}^k}-1)$ and $m_{k+1} \equiv 2{}^{2{}^{k-1}} \mod (2{}^{2{}^k}+1)$ and this one works.

ZetaX wrote: $ m_{k + 1} \equiv 2^{2^{k - 1}} \mod (2^{2^k} + 1)$ Does it work for $ m_{k + 1}^{2}\equiv {-9}\mod(2^{2^{k}}+1)$ ?

There is a factor $ 3$ missing...

the only prime in form of 4k+3 which can devide m^{2}+9 is 3. and so n must be a power of 2; so we should find for which n 2^{2^{n}} devides m^{2}+9. Lemma 1 : all prime factors of 2^{2^{n}} module 4 is 1. Lemma 2: a|b^{2} +1 iff all odd prime factors of a module 4 is qual to 1 and 4 does not divide a. so we can easily get that 2^{2^{n}}=3p, so that by using Lemma 1,2 there exist an m such that p devides m^{2} +1. finally we get 3p devides 3.m^{2} +3 and so (3m)^2 +9. so we done.

we will prove by induction on $n$ : let $2^{2^{n}}-1|m^{2}+9$ for some $m\in \mathbb{Z}$.it's clear that $\upsilon _{3}(2^{2^{n}}-1)=1$. $so 2^{2^{n}}-1=3c$. now we are going to prove there exist $m'\in \mathbb{Z}$ so that $2^{2^{n+1}}-1|m'^{2}+9.$ let $m'=3(\frac{m}{3})+3tc=3k+3tc$. now what we want here is a $t\in\mathbb{Z}$ such that : $2^{2^{n+1}}-1=(2^{2^{n}}-1)( 2^{2^{n}}+1)|m'^{2}+9 =9((k+tc)^{2}+1)\rightarrow c.2^{2^{n}}+1|((k+tc)^{2}+1$. it's clear that $c|RHS.$ by Chinese Remainder Theorem it is also clear that there exist such a $t$ so that $k+tc\equiv 2^{2^{n-1}} mod 2^{2^{n}}+1.$ (note that $(c,2^{2^{n}}+1 )=1 )$. so $TIWWWTP$. (This Is What We Want To Prove ).

Peter wrote: Determine all positive integers $n$ for which there exists an integer $m$ such that $2^{n}-1$ divides $m^{2}+9$.

actually this forgets the prime 2.

The above is clearly false; the argument does not work for the prime $3|2^n - 1$ when $n$ is even (in particular if it is a power of two).

We can only define the quadratic residue or Lengendre symbol when gcd(9, p)=1. We have to show when p and 9 have a G.C.D. if gcd(9, p) is not 1, we can find p=3 (is only prime that divides 2^n-1), it means n=2. when, n=2, we can find out that m can be any number if m is divided by 3. Sorry... My English grammer is not good...

N = $2^k$

Suppose that $n=2^k r$, $r>1$ and odd, works. Then we would have $$2^r-1\mid 2^{2^k r}-1\mid m^2+3^2.$$Let $p$ be a prime divisor of $2^r-1$ then by Fermat's Christmas theorem we must have $$p=2, \quad p\mid \gcd(2^r-1,3)=3 \quad \text{ or } \quad p\equiv 1\mod 4$$Since $p=2,3$ is not possible (easy to check), we must have $p\equiv 1 \pmod 4$. Thus all prime factors of $2^r-1$ is $1\pmod 4$ so $2^r-1$ must also be $1\pmod 4$, however this is a contradiction since it is $-1\pmod 4$. Now we will show that $n=2^k$ works. Note that $3\mid 2^{2^k}-1$ but $9\nmid 2^{2^k}-1$. Let $\frac{2^{2^k}-1}3=\prod p_i^{e_i}$. Notice that $$p_i^{e_i} \mid \frac{2^{2^k}-1}3= (2^{2^{k-1}}+1)(2^{2^{k-2}}+1)\cdots (2^2+1)\implies p_i^{e_i}\mid 2^{2^a}+1$$for some $a\leq k-1$ since $\gcd(2^{2^a}+1,2^{2^b}+1)=1$ whenever $a\neq b$. This implies that $-1$ is a quadratic residue mod $p_i^{e_i}$ for every $i$. It follows that $-1$ is a quadratic residue mod $\frac{2^{2^k}-1}3$. So there is a $t$ such that $$\frac{2^{2^k}-1}3\mid t^2+1\implies 2^{2^k}-1\mid (3t)^2+9,$$as claimed.