If $(m,n)\in\mathbb Z_+^2$ satisfies $3m^2+m = 4n^2+n$ then $(m-n)$ is a perfect square.
Solution 1:
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.
Solution 2:
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) $$
Your fourth values are
$$ 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
Solution 3:
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)$$