Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

中国の剰余定理で3つの式がある場合を解く

整数論

$a = 1 \mod 2$
$a = 2 \mod 3$
$a = 3 \mod 5$
を解きます。これを満たすaは0以上、 $2 \times 3 \times 5 = 30$ 未満に一つしかありません。
$a = 2x + 1$
$a = 3y + 2$
$a = 3z + 5$
$2x + 1 = 3y + 2$
$2x = 3y + 1$
$2(x-2) = 3(y-1)$
$x-2 = 3m$ とおけます。
$a = 2x + 1 = 2(3m+2) + 1 = 6m + 5$
$6m + 5 = 5z + 3$
$6m = 5z - 2$
$6(m-3) = 5(z - 4)$
$m-3=5n$ とおけます。
$a = 2x + 1 = 6m + 5 = 6(5n + 3) + 5 = 30n + 23$
$a = 23 \mod 30$ が解となります。

一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語