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の整数解 | 高校数学の美しい物語

プライバシーポリシー

お問い合わせ

スポンサーリンク