How many positive integers $n$ are there such that $(7n + 1)$ is a perfect square and $(3n + 1) < 2008$

elementary-number-theorysquare-numbers

How many positive integers $n$ are there such that $(7n + 1)$ is a perfect square and $(3n + 1) < 2008$ ?

What I Tried: We have $(3n + 1) < 2008$
$\rightarrow n < 669$ .
Now, $(7n + 1) = k^2$ for some $k$ .
$$\rightarrow 7n = (k + 1)(k – 1)$$
Now I have to count all the $n$ so that after multiplied by $7$ , gives a product same as the product of $2$ consecutive numbers with a gap of one. I know that $n = 5,9$ are two solutions, but there are more values so that when multiplied by $7$ gives a valid solution, like $k = 24,32$ .

The problem I am facing is, is there any elegant way here to count all the solutions?
Can anyone help me?

Best Answer

Since $n\le 668$, we know that $7n+1\le 4677$. $\left\lfloor\sqrt{4677}\right\rfloor=68$, so we want to know how many of the integers $1,2,\ldots,68$ have squares of the form $7n+1$. Suppose that $7n+1=k^2$ for some integer $k$; then $k^2\equiv 1\pmod 7$, and it’s easy to check that this is the case precisely when $k\equiv 1\pmod 7$ or $k\equiv -1\pmod 7$, i.e., when $k=7m\pm 1$ for some integer $m$.

There are $9$ positive multiples of $7$ less than $68$, each of which provides two such values of $k$.

E.g., $3\cdot 7=21$ means that $k=20$ and $k=22$ will work: $20^2=400=7\cdot 57+1$, and $22^2=484=7\cdot 69+1$.

Thus, there are altogether $2\cdot9=18$ such integers $n$.