Find all positive solutions such that $n^2 + 9n +1$ is a perfect square

We know that:

$$ (n+1)^2 = n^2 + 2n +1 < n^2 + 9n +1 < n^2 + 10n + 25 = (n+5)^2 $$

So there are only 3 cases:

$$ n^2 + 9n + 1 = (n+i)^2 , i \in \{2, 3, 4\} $$

Solving each case separately, we get respectively for i = 2, 3, 4:

$$ 5n = 3 $$ $$ 3n = 8 $$ $$ 1n = 15 $$

The usual way to solve these questions is as you've done: bound the expression between two consecutive perfect squares, and prove that the bounds are strict for large $ n $.

The reason that one shouldn't expect a solution using modular arithmetic is that it is too "short-sighted": the question of whether a number is a perfect square or not depends on the exact multiplicity of the primes dividing it, whereas modular arithmetic only provides upper and lower bounds. This suggests that our solution must depend on a global approach.

Here is an alternative solution. We may write (completing the square):

$$ \left( n + \frac{9}{2} \right)^2 - x^2 = \frac{77}{4} $$

$$ (2n + 9)^2 - (2x)^2 = 77 $$

$$ (2n - 2x + 9)(2n + 2x + 9) = 77 $$

Now, we simply check all factors of $ 77 $ to see if they provide solutions. The given hypotheses mean that we must only check two cases: $ 2n + 2x + 9 = 11, 77 $, and the latter gives a solution.

Solutions only for $n=0$ and $n=15$.

Clearly, $n=0$ produces a perfect square. Say now that $n>0$ and $$n^2+9n+1=k^2,$$ for some $k\ge 1$. Then $(k+1)(k-1)=n(n+9)>n(n+2)$. Thus $k-1>n$. Let $k-1=n+v$, where $v$ a positive integer. Then $$ (n+v+2)(n+v)=n(n+9), $$ and hence $$ n(7-2v)=v^2+2v. $$ Hence, if such $v$ exists, it can only be $v\in\{1,2,3\}$. The cases $v=1,2$ lead to contradiction. Indeed, for $v=1$, we have $5n=3$, and for $n=2$, we have $3n=8$.

Meanwhile, for $v=3$, we have $$ n=15, $$ for which $n^2+9n+1=361=19^2$.