No.186
\(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 を使用した.