\(X_1, Y_1, X_2, Y_2\) について考える. □を \(A\) とおくと,

\[A = a_1Y_1 + X_1 = a_2Y_2 + X_2\]

となる. \(g = \gcd(Y_1, Y_2), y_1 = Y_1/g, y_2 = Y_2/g\) とおくと,

\[g(a_1y_1-a_2y_2) = X_2-X_1\]

となる. よって, \(X_2-X_1\) が \(g\) の倍数でなければ \(A\) は存在しない.

ここで, \(x_2 = (X_2-X_1)/g\) とおくと,

\[A-X_1 = ga_1y_1 = g(a_2y_2 + x_2)\]

となるので, \(A-X_1\) も \(g\) の倍数となる. \(B = (A-X_1)/g\) とおくと,

\[B = a_1y_1 = a_2y_2 + x_2\]

となるので,

\[\begin{align} B & \equiv 0 \bmod y_1 \\ B & \equiv x_2 \bmod y_2 \end{align}\]

となる. ここで, \(y_1, y_2\) は互いに素なので, ベズーの等式から,

\[b_1y_1 + b_2y_2 = 1\]

となる \(b_1, b_2\) を拡張ユークリッドの互除法から求めることができる. 上の等式より \(b_1y_1 \equiv 1 \bmod y_2\) となるので,

\[B = b_1y_1x_2 + ky_1y_2\]

とおくと, この式は

\[\begin{align} B &\equiv 0 \bmod y_1 \\ B &\equiv x_2 \bmod y_2 \end{align}\]

を満たす. ここから,

\[\begin{align} A &= gB+X1 = g(b_1y_1(X_2-X_1)/g + ky_1y_2)+X_1 \\ &= b_1y_1(X_2-X_1)+X_1 + kgy_1y_2 \end{align}\]

となる. \(A\) は \(gy_1y_2 = \mathrm{lcm}(Y_1, Y_2)\) で割って \(b_1y_1(X_2-X_1)+X_1\) 余る数であるので, この最小値を求める.

以下, \(A\) と \(X_3\) についても同様に考えればいい.

数値はかなり大きくなるので, GMP を使用した.