## Two Squares

#### Problem

Given that $n$ is a positive integer and $2n+1$ and $3n+1$ are perfect squares, prove that $n$ is divisible by 40.

#### Solution

Clearly $2n+1$ is odd, so let $2n+1 = (2k + 1)^2 = 4k^2+4k+1 \implies n = 2k(k+1)$

As exactly one of $k$ or $k+1$ is even, we deduce that $n$ is divisible by 4.

Because $n$ is even, $3n+1$ must be odd; let $3n + 1 = (2j + 1)^2 \implies 3n = 4j(j+1)$.

Similarly, as exactly one of $j$ or $j+1$ is even, we further deduce that $n$ must be divisible by 8.

Next we note that all square numbers have remainders 0, 1, or 4 when divided by 5.

Proof: If $a \equiv 0, 1, 2, 3, 4 \mod 5$ then $a^2 \equiv 0, 1, 4, 4, 1 \mod 5$.

Now we consider $2n+1$ and $3n+1$ under modulo 5:

$\mod 5$
$$n$$$2n+1$$3n+1$
011
134
202
320
443

From this we can see that it is only possible for both $2n+1$ and $3n+1$ to be squares when $n$ is divisible by 5.

As $n$ is divisible by 8 and 5 it must be divisible by 40.

It must be noted that $n \equiv 0 \mod 40$ is a necessary condition but is not sufficient. For example, when $n = 40$, we can see that $2n+1 = 81 = 9^2$ and $3n+1 = 121 = 11^2$. However, when $n=80$, neither $2n+1 = 161$ nor $3n+1 = 241$ are square.

Does it follow that if $n \equiv 0 \mod 40$ and $2n+1$ is square then $3n+1$?
Find the next two cases of $n$ for which both are square; can you deduce anything further about $n$?

Problem ID: 338 (16 May 2008)     Difficulty: 3 Star

Only Show Problem