# If $(m,n)\in\mathbb Z_+^2$ satisfies $3m^2+m = 4n^2+n$ then $(m-n)$ is a perfect square.

I came across this question on another forum. The question is:

$$\text{If m,n\in \mathbb{Z}_+ such that 3m^2+m=4n^2+n, then (m-n) is a perfect square.}$$

I have managed to partially prove this using this question as motivation as follows.

Let $m>n$ and $k^2 = m-n$. The problem then becomes to show $k$ is an integer. Making the substitution $m=n+k^2$ we get

$$3(n+k^2)^2+(n+k^2) = 4n^2+n$$

And solving for $n$ yields

$$n = 3k^2\pm |k|\sqrt{12k^2+1}$$

So $n$ will be an integer if and only if $12k^2+1$ is a perfect square. This is where the previous question comes in. We want all solutions $(k,N)$ to $12k^2+1=N^2$, i.e. $$N^2-12k^2=1$$ Using Pell's equation and Wikipedia (Pell Equation) as a guide we find the fundamental solution as $y_1=k=2, x_1=N=7$, and hence all other solutions are $x_i, y_i$ where $$x_i+y_i\sqrt{12} = \left(7+2\sqrt{12}\right)^i.$$

It is not hard to see $y_i$ is an integer for all $i$. My conclusion is then: If $(m,n)$ is a solution then $k^2=(m-n)\in S=\{y_i^2\}_{i=1}^{\infty} = \{2^2, 28^2, 390^2,...\}$.

My questions are:

$\ \ \ \bullet$ I made the assumption that $m>n$, is this easy to show?

$\ \ \ \bullet$ If $y\in S$, is there always a solution $(m,n)$ with $(m-n)=y$ ?

$\ \ \ \bullet$ More importantly: Is there an easier way to prove this?

• If we consider everything modulo $3$ and $4$, we get that $m - n \equiv n^2 \mod 3$ and $m - n \equiv m^2 \mod 4$. Perhaps this might help? (Although I haven't found out how) – Yiyuan Lee Feb 18 '14 at 16:18
• I don't think you need to show that $m>n$ as it is a necessity for $m-n$ to be a perfect square. If you really want to show it I guess you could assume $m<n$ and get a quick contradiction because $m-n$ is a perfect square. Check $m=n$ has solution $m=0$ and $n=0$ (v.easy). For your last question, I don't see any easier way to do it, that said there might still be one. Perhaps try the comment above? – user88595 Feb 18 '14 at 16:19
• Obviously $m > n$. Otherwise $3m^2+m$ would be less than $4n^2+n$. – TonyK Feb 18 '14 at 16:23
• Don't know how I missed that @TonyK – David Peterson Feb 18 '14 at 16:26
• How did you get this: "So $n$ will be an integer if and only if $12k^2+1$ is a perfect square." For example, $k=\frac{1}{2}$ gives you a rational solution, how did you get rid of the possibility that such rationals are not integer? Also, $k$ could potentially be irrational, but give integer as a whole expression. Another question is: you are solving this using Pell's equations method which is designed to find integer solutions $k$, but you are to show that $k$ is integer. Don't you trick yourself here? – Vadim Feb 18 '14 at 16:48

Rewrite the original equation $3m^2+m=4n^2+n$ as

$$12m^2+12n^2+m-n-24mn=16n^2+9m^2-24mn.$$

This factors as

$$(m-n)(12(m-n)+1)=(4n-3m)^2.$$

Since $\gcd(m-n,12(m-n)+1)=1$, it follows that $m-n$ is a perfect square, as desired.

• extremely concise! I think this classifies as "an easier way to prove this" – robjohn Dec 20 '14 at 8:12
• To find this solution in the first place, write $m=n+k$; it's easier to see the right way to rewrite the equation then. – Greg Martin Dec 20 '14 at 8:27
• Great proof, was thinking there might be some easier alternative, never thought it'd be this simple. – David Peterson Dec 20 '14 at 9:56

All solutions of $u^2 - 3 v^2 = 1$ are known. Your relation is $$(12m+2)^2 - 3 (8n+1)^2 = 1$$

It is going to turn out that the values of $a = \sqrt {m-n}$ obey $$a_{j+2} = 14 a_{j+1} - a_j,$$ as $14 \cdot 28 -2 = 390.$ Just one of those things.

Meanwhile, given $u^2 - 3 v^2 = 1,$ the next solution is $$(2u+3v)^2 - 3 (u+2v)^2 =1.$$ One must pick out those with $u \equiv 2 \pmod {12}$ and $v \equiv 1 \pmod {8}$

MORE TO COME... $$u = 12 m + 2, v = 8n + 1; m = (u-2)/12; n = (v-1)/8.$$

Alright, your starting pair $$(u,v) = (362,209).$$ To get the next pair with correct mod 12, 8 use $$(97 u + 168 v, 56 u + 97 v).$$ This is the identity matrix mod 8 and has top row (1,0) mod 12. Note $$\left( \begin{array}{rr} 2 & 3 \\ 1 & 2 \end{array} \right)^4 = \left( \begin{array}{rr} 97 & 168 \\ 56 & 97 \end{array} \right)$$

$$u = 2,642,885,282; \; \; \; v = 1,525,870,529;$$ $$m = 220,240,440; \; \; \; n = 190,733,816;$$ $$m-n = 29,506,624 = 5432^2;$$ $$14 \cdot 390 - 28 = 5432.$$

u= 362   v= 209
m= 30   n= 26
diff= 4   sqrt= 2
30 + 26 = 56
56 / 2  =  28
14 * 2 - 0  =  28

u= 70226   v= 40545
m= 5852   n= 5068
diff= 784   sqrt= 28
5852 + 5068 = 10920
10920 / 28  =  390
14 * 28 - 2  =  390

u= 13623482   v= 7865521
m= 1135290   n= 983190
diff= 152100   sqrt= 390
1135290 + 983190 = 2118480
2118480 / 390  =  5432
14 * 390 - 28  =  5432

u= 2642885282   v= 1525870529
m= 220240440   n= 190733816
diff= 29506624   sqrt= 5432
220240440 + 190733816 = 410974256
410974256 / 5432  =  75658
14 * 5432 - 390  =  75658

u= 512706121226   v= 296011017105
m= 42725510102   n= 37001377138
diff= 5724132964   sqrt= 75658
42725510102 + 37001377138 = 79726887240
79726887240 / 75658  =  1053780
14 * 75658 - 5432  =  1053780

u= 99462344632562   v= 57424611447841
m= 8288528719380   n= 7178076430980
diff= 1110452288400   sqrt= 1053780
8288528719380 + 7178076430980 = 15466605150360
15466605150360 / 1053780  =  14677262
14 * 1053780 - 75658  =  14677262

u= 19295182152595802   v= 11140078609864049
m= 1607931846049650   n= 1392509826233006
diff= 215422019816644   sqrt= 14677262
1607931846049650 + 1392509826233006 = 3000441672282656
3000441672282656 / 14677262  =  204427888
14 * 14677262 - 1053780  =  204427888

u= 3743165875258953026   v= 2161117825702177665
m= 311930489604912752   n= 270139728212772208
diff= 41790761392140544   sqrt= 204427888
311930489604912752 + 270139728212772208 = 582070217817684960
582070217817684960 / 204427888  =  2847313170
14 * 204427888 - 14677262  =  2847313170

u= 726154884618084291242   v= 419245718107612602961
m= 60512907051507024270   n= 52405714763451575370
diff= 8107192288055448900   sqrt= 2847313170
60512907051507024270 + 52405714763451575370 = 112918621814958599640
112918621814958599640 / 2847313170  =  39657956492
14 * 2847313170 - 204427888  =  39657956492

u= 140870304450033093547922   v= 81331508195051142796769
m= 11739192037502757795660   n= 10166438524381392849596
diff= 1572753513121364946064   sqrt= 39657956492
11739192037502757795660 + 10166438524381392849596 = 21905630561884150645256
21905630561884150645256 / 39657956492  =  552364077718
14 * 39657956492 - 2847313170  =  552364077718

u= 27328112908421802064005626   v= 15777893344121814089970225
m= 2277342742368483505333802   n= 1972236668015226761246278
diff= 305106074353256744087524   sqrt= 552364077718
2277342742368483505333802 + 1972236668015226761246278 = 4249579410383710266580080
4249579410383710266580080 / 552364077718  =  7693439131560
14 * 552364077718 - 39657956492  =  7693439131560

u= 5301513033929379567323543522   v= 3060829977251436882311426881
m= 441792752827448297276961960   n= 382603747156429610288928360
diff= 59189005671018686988033600   sqrt= 7693439131560
441792752827448297276961960 + 382603747156429610288928360 = 824396499983877907565890320
824396499983877907565890320 / 7693439131560  =  107155783764122
14 * 7693439131560 - 552364077718  =  107155783764122

u= 1028466200469391214258703437642   v= 593785237693434633354326844689
m= 85705516705782601188225286470   n= 74223154711679329169290855586
diff= 11482361994103272018934430884   sqrt= 107155783764122
85705516705782601188225286470 + 74223154711679329169290855586 = 159928671417461930357516142056
159928671417461930357516142056 / 107155783764122  =  1492487533566148
14 * 107155783764122 - 7693439131560  =  1492487533566148

u= 199517141378027966186621143359026   v= 115191275282549067433857096442785
m= 16626428448168997182218428613252   n= 14398909410318633429232137055348
diff= 2227519037850363752986291557904   sqrt= 1492487533566148
16626428448168997182218428613252 + 14398909410318633429232137055348 = 31025337858487630611450565668600
31025337858487630611450565668600 / 1492487533566148  =  20787669686161950
14 * 1492487533566148 - 107155783764122  =  20787669686161950

u= 38705296961136956048990243108213402   v= 22346513619576825647534922383055601
m= 3225441413428079670749186925684450   n= 2793314202447103205941865297881950
diff= 432127210980976464807321627802500   sqrt= 20787669686161950
3225441413428079670749186925684450 + 2793314202447103205941865297881950 = 6018755615875182876691052223566400
6018755615875182876691052223566400 / 20787669686161950  =  289534888072701152
14 * 20787669686161950 - 1492487533566148  =  289534888072701152

• I'll need to digest this a bit. Thanks for the effort! – David Peterson Feb 18 '14 at 22:32
• @DavidPeterson, I might emphasize that the fractions $u/v$ occur as convergents in the continued fraction for $\sqrt 3,$ as in $1/1,2/1,5/3,7/4,19/11,26/15,71/41, 97/56,265/163,362/209$ and so on. The true beginning for your problem is $2/1,$ which corresponds to $m=n=0.$ After that, it is every eighth convergent. – Will Jagy Feb 19 '14 at 9:02
• I do not see where you actually proved that it is integer. where does the recursion for square roots follow from? – Vadim Feb 19 '14 at 23:38

Since I criticized your solution, I felt kind of obliged to provide one. Besides, it is an interesting problem. So, here it is.

What I want to show is that if $(m,n)$ is an integer solution to your equation, and $(m^*,n^*)$ is the next solution (we will order all solutions), then

$$\sqrt{m^*-n^*}=\frac{m+n}{\sqrt{m-n}} \tag{*}$$

so that, by induction, if $\sqrt{m-n}$ is an integer, $\sqrt{m^*-n^*}$ is rational and its square is integral, hence, it is an integer as well. The first non-trivial solution $m=30$, $n=26$ (see below) gives $\sqrt{30-26}=2$.

Step 0. Note that using the equation from the problem statement,

$$(m+n)^2=2(m^2+n^2)-(m-n)^2=2(m-n)(7m+7n+2)-(m-n)^2$$

so that in order to show (*) we need to show that

$$m^*-n^*=\frac{(m+n)^2}{m-n}=13m+15n+4 \tag{**}$$

Now, this is a pretty straightforward exercise.

Step 1. Pell's equation. We rewrite equation so that it looks more like a Pell's equation:

$$3(m+1/6)^2-(2n+1/4)^2=1/48$$

or, by multiplying to make all coefficients integral,

$$(12m+2)^2-3(8n+1)^2=x^2-3y^2=1$$

Step 2. Solve Pell's equation. The initial solution corresponding to $m=n=0$ is $(x,y)=(2,1)$. So, others are given by recursion:

$$x'=2x+3y,y'=x+2y$$

We need to filter out those that give non-integer values for $m$ and $n$. The chain of $(x\mod 12,y\mod 8)$ starting from the first solution: $(2,1)\rightarrow(7,4)\rightarrow(2,7)\rightarrow(1,0)\rightarrow(2,1)\rightarrow\dots$. So, the solutions $(x,y)$ giving integer $m$ and $n$ are exactly 4 steps away from each other.

$$\left(\begin{array}{} x^* \\ y^* \end{array}\right)=\left(\begin{array}{} x'''' \\ y'''' \end{array}\right)=\left(\begin{array}{} 2 & 3 \\ 1 & 2 \end{array}\right)^4\left(\begin{array}{} x \\ y \end{array}\right)=\left(\begin{array}{} 97 & 168 \\ 56 & 97 \end{array}\right)\left(\begin{array}{} x \\ y \end{array}\right)$$

And, from here, we obtain (**):

$$24(m^*-n^*)=2(x^*-2)-3(y^*-1)=2x^*-3y^*-1=26x+45y-1=$$ $$=312m+52+360y+45-1=24(13m+15n+4)$$

EDIT, December 2014: I put pages from four books at OTHER, with prefix indefinite_binary. Buell is my favorite for what we see here.

Alright, complete proof, my way. I had thought that the OP would be able to finish using explicit square root powers as in his post, but that is unwieldy, and I never actually succeeded in finishing the proof that way. Given the degree-two recurrences below, such formulas can be recovered without as much difficulty. We begin with the indefinite binary quadratic form $x^2 - 14 xy + y^2.$ We get an "automorph" or isometry of the form from the matrix identity

$$\left( \begin{array}{rr} 14 & 1 \\ -1 & 0 \end{array} \right) \left( \begin{array}{rr} 1 & -7 \\ -7 & 1 \end{array} \right) \left( \begin{array}{rr} 14 & -1 \\ 1 & 0 \end{array} \right) = \left( \begin{array}{rr} 1 & -7 \\ -7 & 1 \end{array} \right).$$

This means (check!) that, if $u = 14 x - y, v = x,$ then $u^2 - 14 uv+v^2 = x^2 - 14 xy+y^2.$ In particlar, with $s_0 = 0, s_1 = 2, s_2 = 28, s_3 = 390,s_4 = 5432$ and $s_{j+2}= 14 s_{j+1} - s_j,$ then $s_{j+2}^2 - 14 s_{j+2}s_{j+1}+s_{j+1}^2 = s_{j+1}^2 - 14 s_{j+1}s_j+s_j^2.$ This starts at 4 and remains 4, so $$s_{j+1}^2 - 14 s_{j+1}s_j+s_j^2 = 4.$$

Next, suppose we have a special type of automorph corresponding to a diagonal indefinite form, that is integers $\alpha^2 - \beta \gamma = 1,$ and the relation $$\left( \begin{array}{r} x_{j+1} \\ y_{j+1} \end{array} \right) = \left( \begin{array}{rr} \alpha & \beta \\ \gamma & \alpha \end{array} \right) \left( \begin{array}{r} x_{j} \\ y_{j} \end{array} \right) .$$ Then $$\left( \begin{array}{r} x_{j+2} \\ y_{j+2} \end{array} \right) = \left( \begin{array}{rr} \alpha^2 + \beta \gamma & 2 \alpha \beta \\ 2 \alpha \gamma & \alpha^2 + \beta \gamma \end{array} \right) \left( \begin{array}{r} x_{j} \\ y_{j} \end{array} \right)= \left( \begin{array}{rr} 2 \alpha^2 -1 & 2 \alpha \beta \\ 2 \alpha \gamma & 2 \alpha^2 -1 \end{array} \right) \left( \begin{array}{r} x_{j} \\ y_{j} \end{array} \right) .$$

What becomes evident is that $$x_{j+2} + x_j = 2 \alpha x_{j+1}, \; \; \; y_{j+2} + y_j = 2 \alpha y_{j+1}.$$

For this problem, I used letters $u_j = 12 m_j + 2, v_j = 8 n_j + 1.$ The Greek letters are $\alpha = 97, \beta = 168, \gamma = 56.$ We find that $$u_{j+2} = 194 u_{j+1} - u_j, \; \; v_{j+2} = 194 v_{j+1} - v_j.$$ For your original letters, $$m_{j+2} = 194 m_{j+1} - m_j + 32, \; \; n_{j+2} = 194 n_{j+1} - n_j + 24.$$ So, $$(m-n)_{j+2} = 194 (m-n)_{j+1} - (m-n)_{j} + 8.$$

We know that $(m-n)_{j}$ agrees with $s_j^2$ for small $j.$ The induction step is to show that $s_j^2$ satisfies the same degree two linear recursion. We need to prove that $s_{j+2}^2 = 194 s_{j+1}^2 - s_{j}^2 + 8.$

PROOF. We know $s_{j+2}= 14 s_{j+1} - s_j,$ and $s_{j+1}^2 - 14 s_{j+1}s_j+s_j^2 = 4.$ $$s_{j+2}^2 = 196 s_{j+1}^2 - 28 s_{j+1} s_{j} + s_{j}^2.$$ $$8 = 2 s_{j+1}^2 - 28 s_{j+1}s_j+ 2 s_j^2.$$ Subtract $$s_{j+2}^2 -8 = 194 s_{j+1}^2 - s_{j}^2.$$ $$s_{j+2}^2 = 194 s_{j+1}^2 - s_{j}^2 + 8.$$ COMPARE $$(m-n)_{j+2} = 194 (m-n)_{j+1} - (m-n)_{j} + 8.$$ So, $$m_j - n_j = s_j^2$$ $$\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$$

It became interesting for the General case. When the difference is a square?

Write so equation:

$$aX^2+X=bY^2+Y$$

If you use the solutions of the Pell equation.

$$p^2-abs^2=\pm1$$

Then decisions can be recorded.

$$X=\pm(p+bs)s$$

$$Y=\pm(p+as)s$$

$p,s$ - can be of any sign. So the difference will be equal.

$$X-Y=\pm(b-a)s^2$$

Mean difference solutions of the square when the difference of the coefficients of the square.