# If $2n+1$ and $3n+1$ are perfect squares, then prove that $8|n$.

If for some number $$n\in \mathbb N$$, the numbers $$2n+1$$ and $$3n+1$$ are perfect squares of integers, then prove that $$8|n$$.

if $$2n+1=m^2$$ and $$3n+1=k^2$$ then $$k^2-m^2=3n-2n+1-1=n$$ now I need to show that $$8|k^2-m^2$$ when you divide a some number $$m^2$$ with $$8$$ then remainder is $$0,1,4$$, so I need to show that $$m^2$$ and $$k^2$$ have the same remainder. But I do not know is this good way because I do not know how to prove that they must have the same remainder

If $$k$$ is odd, then $$k^2\equiv1 \mod 8$$. Hence $$3n+1\equiv1\mod 8$$, $$2n+1\equiv 1\mod 8$$, so $$(3n+1)-(2n+1)\equiv 1-1\equiv 0\mod 8$$

• You need to prove that $k$ is odd to apply that, but you have not done so. – Bill Dubuque Nov 21 '18 at 20:32
• Minor issue. How do we know $3n+1$ and $2n + 1$ are odd? – fleablood Nov 21 '18 at 20:49
• Damned, you're right :-( Didn't see this one coming :-) – Nicolas FRANCOIS Nov 22 '18 at 20:32

If $$2n+1=a^2$$ and $$3n+1=b^2$$, then $$a$$ is odd. So $$a=2k+1$$ and $$2n+1=(2k+1)^2=4k^2+4k+1$$. Thus, $$n=2k^2+2k=2k(k+1)$$. This shows that $$n$$ is divisible by $$4$$ because $$k(k+1)$$ is even.

Now, $$b^2=3n+1=6k(k+1)+1$$. So, $$b$$ is also odd and $$b=2l+1$$. Then, $$(2l+1)^2=6k(k+1)+1$$ implies $$2l(l+1)=3k(k+1)$$. That is $$k(k+1)$$ is divisible by $$4$$ because $$l(l+1)$$ is even. Because $$n=2k(k+1)$$ and $$k(k+1)$$ is divisible by $$4$$, $$n$$ is divisible by $$8$$.

In fact, $$3a^2-2b^2=3(2n+1)-2(3n+1)=1$$. That is, $$(1+\sqrt{-2})(1-\sqrt{-2})a^2=1+2b^2=(1+\sqrt{-2}b)(1-\sqrt{-2}b).$$ Note that $$\Bbb{Q}(\sqrt{-2})$$ is a quadratic field with class number $$1$$, it is a ufd and we can talk about gcd. Because $$\gcd(1+\sqrt{-2}b,1-\sqrt{-2}b)=1$$, we get that either $$\frac{1+\sqrt{-2}b}{1+\sqrt{-2}}=(u+\sqrt{-2}v)^2$$ or $$\frac{1-\sqrt{-2}b}{1+\sqrt{-2}}=(u+\sqrt{-2}v)^2$$ for some $$u,v\in\Bbb{Z}$$. But up to sign switching $$b\to -b$$, we can assume that $$\frac{1+\sqrt{-2}b}{1+\sqrt{-2}}=(u+\sqrt{-2}v)^2=u^2-2v^2+2uv\sqrt{-2}.$$ That is, $$1+\sqrt{-2}b=u^2-2v^2-4uv+(u^2-2v^2+2uv)\sqrt{-2}.$$ So, $$u^2-2v^2-4uv=1$$ and so $$(u-2v)^2-6v^2=1$$. So, $$(x,y)=(u-2v,v)$$ is a solution to the Pell-type equation $$x^2-6y^2=1.$$ The solutions are known $$x+\sqrt{6}y=\pm(5+2\sqrt{6})^t$$ where $$t\in\Bbb{Z}$$. Since the sign switching $$(u,v)\to(-u,-v)$$ does not change anything, we can assume that $$u-2v+\sqrt{6}v=(5+2\sqrt{6})^t.$$ So, $$u-2v=\frac{(5+2\sqrt{6})^t+(5-2\sqrt{6})^{t}}{2}$$ and $$v=\frac{(5+2\sqrt{6})^t-(5-2\sqrt{6})^{t}}{2\sqrt{6}}.$$ That is, $$u=\frac{(2+\sqrt{6})(5+2\sqrt{6})^t-(2-\sqrt{6})(5-2\sqrt{6})^{t}}{2\sqrt{6}}.$$ That is, $$b=u^2-2v^2+2uv=\frac{(2+\sqrt{6})(5+2\sqrt{6})^{2t}+(2-\sqrt{6})(5-2\sqrt{6})^{2t}}{4}.$$ This gives $$a=\sqrt{\frac{1+2b^2}{3}}=u^2+2v^2=\frac{(3+\sqrt{6})(5+2\sqrt{6})^{2t}+(3-\sqrt{6})(5-2\sqrt{6})^{2t}}{6}.$$ So, we have $$n=\frac{(5+2\sqrt{6})^{4t+1}-10+(5-2\sqrt{6})^{4t+1}}{24},$$ where $$t\in\mathbb{Z}$$. So the first seven values of $$n$$ are $$n=0,40,3960, 388080,38027920,3726348120,365144087880.$$ That is, $$n=n(t)$$ satisfies $$n(0)=0$$ and $$n(-1)=40$$ with $$n(t-1)+n(t+1)=9602 n(t)+4000$$ for all $$t\in\mathbb{Z}$$. So, not only $$8$$ divides $$n$$, $$40$$ divides $$n$$ for every such $$n$$.

I think it is easier to re-parametrize $$n$$ using non-negative integers instead of all integers. Let $$n_t=\frac{(5+2\sqrt{6})^{2t+1}-10+(5-2\sqrt{6})^{2t+1}}{24},$$ for non-negative integer $$t$$. So, $$n_0=0$$, $$n_1=40$$, and $$n_{t+2}=98n_{t+1}-n_t+40.$$ We have the corresponding $$a=a_t$$ and $$b=b_t$$ to $$n=n_t$$: $$a_0=1$$, $$a_1=9$$, and $$a_{t+2}=10a_{t+1}-a_t,$$ as well as $$b_0=1$$, $$b_1=11$$, and $$b_{t+2}=10b_{t+1}-b_t.$$

$$\begin{array}{ |c|c|c|c| } \hline t & n_t & a_t & b_t \\ \hline 0 & 0 & 1 &1 \\ 1 & 40 & 9& 11 \\ 2 & 3960 & 89 & 109 \\ 3 & 388080 & 881 &1079\\ 4 & 38027920 & 8721 & 10681 \\ 5 & 3726348120 & 86329 & 105731 \\ 6 & 365144087880 & 854569 & 1046629 \\\hline \end{array}$$

• Does $4|n$ as well? – Yadati Kiran Nov 21 '18 at 16:59
• If $8\mid n$, then $4\mid n$. – user614671 Nov 21 '18 at 17:00
• I don't know what you did, but your answer was off by a factor of $2$. So, I fixed it. – Batominovski Nov 21 '18 at 18:31
• I have a feeling that you can directly apply some results from Pell's equations, without having to deal with $\mathbb{Q}(\sqrt{-2})$. But I haven't thought about it well enough. – Batominovski Nov 21 '18 at 18:41
• @Displayname I don't think Snookie was trying to prove $40\mid n$. The aim was probably to find all $n$. The result $40\mid n$ is a nice little consequence. And I think we can use Pell's equation $x^2-6y^2=-2$ or $x^2-6y^2=3$ without having to deal with $\mathbb{Q}(\sqrt{-2})$. However, I am not sure whether these Pell-type equations have unique fundamental solutions. – Batominovski Nov 21 '18 at 21:09

It's a standard exercise that if $$b > a$$ and $$a$$ and $$b$$ are both odd that

i) $$a + b$$ and $$a-b$$ are both even and that

ii) exactly one of $$a+b$$ and $$a-b$$ is divisible by $$4$$.

Pf: Let $$b = 2m + 1$$ and $$a = 2n+1$$ so $$b-a = 2(m-n)$$ and $$b+a = 2(m+n+1)$$ are both even.

If $$m$$ and $$n$$ are both even or both odd then $$m-n$$ is even and $$m+n + 1$$ is odd so $$4|b-a$$ but $$4\not \mid b+a$$. If $$m$$ and $$n$$ are opposite paritty then the exact opposite occurs; $$m-n$$ is odd and $$m+n +1$$ is even so $$4\not \mid b-a$$ and $$4\mid b+a$$.

As a consequence $$b^2 - a^2 = (b-a)(b+a)$$ is divisible by $$8$$.

So if we have $$2n + 1 = a^2$$ then $$a^2$$ is odd so $$a$$ is odd.

AND we have $$2n = a^2 -1 = (a-1)(a+1)$$ is divisible by $$8$$ so $$n$$ is even.

And if $$3n + 1=b^2$$ then we have $$n$$ is even so $$b^2$$ is odd so $$b$$ is odd.

So $$n = (3n+1)-(2n+1) =b^2 - a^2$$ where $$a,b$$ are both odd..... which is divisible by $$8$$.

Odd squares are all congruent to $$1$$ mod $$8$$, so if $$2n+1$$ is a square, we must have $$4\mid n$$. Writing $$n=4n'$$, we now have $$3n+1=12n'+1$$, which, if it's square, must also be congruent to $$1$$ mod $$8$$, so we must have $$2\mid n'$$. Writing $$n'=2n''$$, we have $$n=4n'=8n''$$, so $$8\mid n$$.

We have $$2n+1, 3n+1 \equiv \{0,1,4 \} \mod 8,$$ whereupon checking $$n = 0, 1, \dots, 7,$$ we see that only $$n \equiv 0 \mod 8$$ works.

Snookie has shown that $$40 | n.$$ Indeed, we can show $$5 | n$$ in a similar fashion by noting that $$2n + 1 \equiv \{0, 1\} \mod 5$$ implies $$n \equiv 0 \mod 5$$ by checking $$0, 1, \dots, 4.$$

Since $$n=40$$ works, this is the strongest result that we can prove.