# 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.

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.

My work:
$3n+1=x^2$
$3n+3=x^2+2$
$3(n+1)=x^2+2$
$(n+1)=\dfrac{x^2+2}{3}$

• where did you got his question? Some Olympiad? – user87543 Jan 10 '14 at 12:39
• no, not olympiad...i got it somewhere...don't remember where.had been trying since then without any luck! – Hawk Jan 10 '14 at 12:42
• I would suggest you to work out for $2n+1$ case first and then look for $3n+1$... i.e., $2n+1$ is a perfect square then $n+1$ is sum of two perfect squares.... let me tell you this is not so easy and this would take some time.... do not get frustrated... Good luck! – user87543 Jan 10 '14 at 12:45
• No, the cause for my frustration is, this problem was classified as 'easy'. – Hawk Jan 10 '14 at 12:48
• I am not aware of your level but this is a "Putnam practice level problem"... Good luck any how! – user87543 Jan 10 '14 at 12:49

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$ it 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.

• really neat...and great approach...thank you! can you suggest me some materials or books which will help me with these approaches for practice? – Hawk Jan 11 '14 at 6:28

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$

• yes, this a good method too! It is just that you treated the residue modulo class before and Lin did after formulation! But one thing is good in this method...that is, I do not have to think about producing $9n+9$, which is a little complicated to think about in the first place! – Hawk Jan 12 '14 at 5:28
• @Hawk, another point: I didn't deal $a\equiv1,2\pmod 3$ separately – lab bhattacharjee Jan 12 '14 at 5:34
• yes, that is what I said, you did not treat the residue modulo class directly! – Hawk Jan 12 '14 at 5:40
• @Hawk, sorry, I somehow missed that line:) – lab bhattacharjee Jan 12 '14 at 5:41

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.

• are you sure it is not difficult... I do not think so... :O – user87543 Jan 10 '14 at 12:29
• @PraphullaKoushik.Agreed!I cannot do it easily still now and I am trying! – Hawk Jan 10 '14 at 12:38
• Please show us your technique, you think it is easy. It will be easy for you to show! – Hawk Jan 10 '14 at 12:39
• I know it is not easy! :D – user87543 Jan 10 '14 at 12:39
• Hope my answer is more helpful now. Also I tried to help and my first thought was that is must be easy to show that last part. I might be wrong. So I don't understand the frustration. – Kal S. Jan 10 '14 at 12:55