No.186

□を $A$ とおく.

$$A \equiv X_1 \pmod{Y_1} \\ A \equiv X_2 \pmod{Y_2}$$

となる.

$g = \gcd(Y_1, Y_2)$ とすると, $Y_1, Y_2$ はともに $g$ の倍数なので,

$$A \equiv X_1 \pmod g \\ A \equiv X_2 \pmod g$$

となる. よって,

$$X_1 \equiv X_2 \pmod g$$

が成立しない場合は解がない.

また, ベズーの等式より

$$m'Y_1 + n'Y_2 = g$$

となる $m', n'$ が存在する.

$X_1, X_2$ は $g$ で割った余りが同じであるので, $X_2 - X_1 = kg$ となり,

$$mY_1 + nY_2 = X_2 - X_1$$

と表せる. この $m, n$ は拡張ユークリッドの互除法で求めることができる.

ここで, $l = {\rm lcm}(Y_1, Y_2)$ とすると,

$$A = mY_1 + X_1 + kl = X_2 - nY_2 + kl$$

とおくと, この $A$ は題意を満たすので,

$$A \equiv mY_1 + X_1 \pmod l$$

となる. $k = 3$ の式と上式については同様の方法で計算できる.