Soldier Lines Riddle

Let $x$ be the number of lines in one group and $y$ be that in the other for integers $y > 2$ and $x>3$ . We could set up the system of equilavences as show below:

$x^2 \equiv 2 \pmod y$ $y^2 \equiv 3 \pmod x$

Then let $d = |x-y|$ . We can then substitute $d^2$ into the equivalences with $d^2 > 3$ or $d>1$ :

$x^2 \equiv (x-y)^2 \equiv d^2 \equiv 2 \pmod y$ $y^2 \equiv (y-x)^2 \equiv d^2 \equiv 3 \pmod x$

Now we will rewrite the system as equations for some integer quotients $n,m$ :

$d^2 = ny + 2$ $d^2 = mx +3$

Thus, $ny-mx = 1$ , and according to Bezout's identity, gcd(x,y) = 1, and gcd(m,n) = 1.

Solving for $x,y$ , we will get:

$y = \dfrac{d^2 -2}{n}$ $x = \dfrac{d^2 -3}{m}$

That means $d = |x-y| = | \dfrac{d^2 -3}{m} - \dfrac{d^2 -2}{n}|$ . Then $dmn = |(m-n)d^2 -2m +3n|= |(m-n)(d^2 - 2) + n| = |(m-n)(ny) + n|$ . Dividing by $n$ both sides, $dm = |(m-n)y + 1|$ . Thus, $dm \equiv |1| \equiv 1 \pmod y$ for $y>x$ .

Let us check cases, where $y > x$ and that $y = x+d$ .

From the above equation, we could also set up $dm \equiv 1 \pmod{m-n}$ . Since $m-n \equiv 0 \pmod{m-n}$ , then $m \equiv n \pmod{m-n}$ . Thus, $d$ is a modular inverse of $m$ and $n$ . Then $dn \equiv 1 \pmod{m-n}$ , and $(d^2 -2) n \equiv d-2n \pmod{m-n}$ .

Substituting $ny = d^2 - 2$ , we will get $n^2 y \equiv d - 2n \pmod{m-n}$ .

$n^2 y - 2n \equiv d \pmod{m-n}$ .

$(ny)^2 - 2ny \equiv dy \pmod{y(m-n)}$ .

$(mx+1)^2 -2(mx +1) \equiv dy \pmod{y(m-n)}$ .

$(mx)^2 - 1 \equiv dy \pmod{y(m-n)}$ .

$(mx-1)(mx+1) \equiv dy \pmod{y(m-n)}$ .

$(mx-1)(ny) \equiv dy \pmod{y(m-n)}$ .

$(mx-1)(n) \equiv d \pmod{(m-n)}$ .

$mx-1 \equiv d^2 \pmod{(m-n)}$ .

$mx+3 \equiv d^2 +4\pmod{(m-n)}$ .

$d^2 \equiv d^2 +4\pmod{(m-n)}$ .

Finally, $4 \equiv 0 \pmod{m-n}$ . That means $m-n|4$ , and the value of $m-n$ is either $1$ , $2$ , or $4$ .

However, by checking values of $d =2,3,4$ , no answers can be found:

For $d=2$ , $d^2 = 4 \equiv 3 \pmod x$ ; $1 \equiv 0 \pmod x$ , which is contradicted because $x > 3$ .

For $d=3$ , $d^2 = 9 \equiv 2 \pmod y$ ; $7 \equiv 0 \pmod y$ . Only $y=7$ works, leading to $x = 7- 3 = 4$ , but $d^2 - 3 = 9-3=6$ , which is not divisible by $4$ and so contradicted.

For $d=4$ , $d^2 = 16 \equiv 2 \pmod y$ ; $14 \equiv 0 \pmod y$ . Again, only $y=7$ works, leading to $x = 7- 4 = 3$ , but $d^2 - 3 = 16-3=13$ , which is not divisible by $3$ and so contradicted.

By all means, we can conclude that $d > m-n$ . Returning to $dm = (m-n)y + 1$ . $d(m - \dfrac{1}{d}) = (m-n)y$ . Since $d > m-n$ , then $y > m - \dfrac{1}{d}$ . With both $y,m$ being integers, we can conclude $y > m$ .

Returning to $dm \equiv 1 \pmod y$ . $d^2 m \equiv d \pmod y$ . Since $d^2 = ny + 2$ , then $d^2 \equiv 2 \pmod y$ . Thus, $2m \equiv d \pmod y$ , and $m = d-m \pmod y$ . We know that $y>m$ and $y>d$ , so that means $y > |d-m|$ . Here are the $3$ possible scenarios:

First, $d-m = 0$ , that makes $m = 0 \pmod y$ , which is contradicted because $y > m$ .

Second, $d-m < 0$ , with $y > m$ and $y > d$ , the resulting $2m-d \equiv 0 \pmod y$ only applies for $y = 2m-d$ . For any higher quotient before $y$ will make an inequality. Then $x+d = 2m-d$ , and so $x = \dfrac{d^2 -3}{m} = 2(m-d)$ . Rearranging the quadratic equation, we will obtain $d^2 +(2m)d-(2m^2 + 3) = 0$ . By the quadratic formula, $d = -m + \sqrt{3(m^2 + 1)}$ . In order to yield integer $d$ , $m^2 + 1 = 3t^2$ for some integer $t$ . However, per modulo $3$ , $m^2 \equiv -1 \pmod 3$ , and for all perfect squares modulo $3$ , it only results in a remainder of $1$ or $0$ only. Thus, this is contradicted.

As a result, $y> d-m > 0$ and $y > m$ . Thus, in order for the remainders $m \equiv d-m \pmod y$ to be true, it needs to be $m = d-m$ . Thus, $d = 2m$ . Then $d^2 = 4m^2 = mx+3$ , and so $m(4m-x) = 3$ . That means $m|3$ , leaving only $m = 1$ or $m=3$ , but for $m=1$ , it will cause $d=2$ , which is shown to be contradicted earlier.

Since no lesser $d$ is applicable, the other cases, where $x>y$ wouldn't result in least possible solution.

Finally, $m=3$ ; $d=6$ , and $36 \equiv 2 \pmod y$ . $34 = 2\times 17 \equiv 0 \pmod y$ . Clearly, $n=2$ and $y = 17$ , and $x = 17-6 =11$ .

Therefore, the total number of soldiers = $11^2 + 17^2 = \boxed{410}$ .

Checking the answers, we can prove the solution:

$11^2 = 17\times 7 + 2$

$17^2 = 11\times 26 + 3$