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$

This will give the answer : http://www.proofwiki.org/wiki/Integer_as_Sum_of_Three_Squares

You need to prove that $n+1=\frac{x^2+2}{3}$ is not of the form $4^k(8m+7)$ for $k,m\in \mathbb{N}$ and its not that difficult to show this.

For Square modulo 8 we know that $x^2 =0,1,4 \mod{8}$, so $x^2 +2 =2,3,6 \mod{8}$. Since $x^2 +2 =0 \mod{3}$ we obtain that $\frac{x^2 +2}{3} = 1,2,A \mod{8}$ where $A=\frac{2+8a}{3}$, $a$ positive integer. And $A=\psi \mod{8}$ namely, $2=3\psi \mod{8}$ with $\psi\in\{0,1,...,7\}$. The only possible value is $\psi=6$ hence $\frac{x^2 +2}{3} = 1,2,6 \mod{8}$.

If it was of that particular form then:

For $m=0$,$k=0$ it is equal to 7 modulo 8

For $m=0$,$k=1$ it is equal to 4 modulo 8

For $m=0$,$k=2$ it is equal to 0 modulo 8

For $m>0,k>2$ it is equal to 0 modulo 8 So you obtain a contradiction.