書記が数学やるだけ#73 合同式の基本操作，中国剰余定理

休憩（？）として，大学入試からその後まで幅広く用いられる合同式について，いくつか話題を提供する。

今回は基本操作と中国剰余定理について，次回はフェルマーの小定理について扱うことにする。

過去に平方剰余について扱った記事があるのでそちらも参照。

問題

前座として，見るからに合同式を使う問題。

中国剰余定理について，「孫子算経」が元とされている。

説明

整数の割り算について余りを考えるのが合同式の始まり。

重要なのは和と積についての式。

そこから累乗においても合同であることが言える（証明について，2018年京都府大／生命環境にて出題）。これがとても便利なもので，例え何乗して膨大な数になっても余りが簡単にわかるようになる。

中国剰余定理について，「孫子算経」にこのような問題がある。

引用元：

https://ctext.org/sunzi-suan-jing/zh

今有物，不知其數。三、三數之，賸二；五、五數之，賸三；七、七數之，賸二。問物幾何？
答曰：二十三。
術曰：「三、三數之，賸二」，置一百四十；「五、五數之，賸三」，置六十三；「七、七數之，賸二」，置三十。并之，得二百三十三。以二百一十減之，即得。凡三、三數之，賸一，則置七十；五，五數之，賸一，則置二十一；七、七數之，賸一，則置十五。一百六以上，以一百五減之，即得。

この問題は「孫子算経」とともに日本にも伝わり，後に和算の隆盛した江戸時代には「百五減算」として知られた。のちに，ガウスは「整数論」（1801年）で，以下に示す中国剰余定理の証明を行なった。

解法

累乗における合同を利用することで，剰余を絞り込むことができる。

最小公倍数と最大公約数からabの値はわかる。

合同式の基本操作を駆使して，それぞれの剰余を求めていく。

最後にaとbそれぞれの値を出す。和と差の剰余から候補を割り出す。

中国剰余定理の問題。

孫子算経に書かれていた解法はこちらである。

これを，連立合同式を立てて地道に解くとこうなる。

中国剰余定理は，現代では暗号理論において重要な役割を果たしている。

参考：

中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

本記事のもくじはこちら：