If $n$ is a positive integer greater than 1 such that $3n+1$ is perfect square, then show that $n+1$ is the sum of three perfect squares.

We are given that $3n+1 = a^2 $.

We want to show that $n+1$ is the sum of 3 perfect squares.

Note that $a$ is not a multiple of 3.

If $ a \equiv 1 \pmod{3}$, then observe that $9n+9 = 3a^2 + 6 = (a-1)^2 + (a-1)^2 + (a+2)^2$, and hence

$$ n+1 = \left( \frac{a-1}{3} \right)^2 + \left( \frac{a-1}{3} \right)^2 + \left( \frac{a+2}{3} \right)^2. $$

If $ a \equiv 2 \pmod{3}$, then observe that $9n+9 = 3a^2 + 6 = (a+1)^2 + (a+1)^2 + (a-2)^2$, and hence

$$ n+1 = \left( \frac{a+1}{3} \right)^2 + \left( \frac{a+1}{3} \right)^2 + \left( \frac{a-2}{3} \right)^2 $$

Thus the result is true.

The motivation behind the solution is: We want to show that $n+1$ is the sum of 3 squares, and the only thing that we have to work with is $a^2$, and possibly things around it. Since $3a^2$ (the naive sum of 3 squares) is so close to $9n+9$, this suggests that we have some sort of wriggle room. Remembering that we have to account for the factor of 3 then greatly restricts our options.

---

As an extension, show that $n+3$ can also be written as the sum of 3 perfect squares, using a similar approach.

If $\displaystyle 3n+1=a^2, (a,3)=1\implies a$ can be written as $\displaystyle3b\pm1$ where $b$ is an integer

So we have $\displaystyle 3n+1=(3b\pm1)^2\implies n=3b^2\pm2b$

$\displaystyle n+1=3b^2\pm2b+1=b^2+b^2+b^2\pm2b+1=b^2+b^2+(b\pm1)^2$