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:

I have no clue what to do next. Please help!

  • $\begingroup$ where did you got his question? Some Olympiad? $\endgroup$ – user87543 Jan 10 '14 at 12:39
  • $\begingroup$ no, not olympiad...i got it somewhere...don't remember where.had been trying since then without any luck! $\endgroup$ – Hawk Jan 10 '14 at 12:42
  • $\begingroup$ 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! $\endgroup$ – user87543 Jan 10 '14 at 12:45
  • $\begingroup$ No, the cause for my frustration is, this problem was classified as 'easy'. $\endgroup$ – Hawk Jan 10 '14 at 12:48
  • $\begingroup$ I am not aware of your level but this is a "Putnam practice level problem"... Good luck any how! $\endgroup$ – 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.

  • $\begingroup$ really neat...and great approach...thank you! can you suggest me some materials or books which will help me with these approaches for practice? $\endgroup$ – 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$

  • $\begingroup$ @Hawk, how about this method? $\endgroup$ – lab bhattacharjee Jan 11 '14 at 10:37
  • $\begingroup$ 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! $\endgroup$ – Hawk Jan 12 '14 at 5:28
  • $\begingroup$ @Hawk, another point: I didn't deal $a\equiv1,2\pmod 3$ separately $\endgroup$ – lab bhattacharjee Jan 12 '14 at 5:34
  • $\begingroup$ yes, that is what I said, you did not treat the residue modulo class directly! $\endgroup$ – Hawk Jan 12 '14 at 5:40
  • $\begingroup$ @Hawk, sorry, I somehow missed that line:) $\endgroup$ – 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.

  • $\begingroup$ are you sure it is not difficult... I do not think so... :O $\endgroup$ – user87543 Jan 10 '14 at 12:29
  • $\begingroup$ @PraphullaKoushik.Agreed!I cannot do it easily still now and I am trying! $\endgroup$ – Hawk Jan 10 '14 at 12:38
  • $\begingroup$ Please show us your technique, you think it is easy. It will be easy for you to show! $\endgroup$ – Hawk Jan 10 '14 at 12:39
  • $\begingroup$ I know it is not easy! :D $\endgroup$ – user87543 Jan 10 '14 at 12:39
  • $\begingroup$ 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. $\endgroup$ – Kal S. Jan 10 '14 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.