中国剰余定理
主張
$ x\equiv 3\pmod{11}
$ x\equiv5\pmod{7}
この2つの合同式を1つにまとめて$ x \equiv 47 \pmod{77}みたいにできるのでは…？というもの。
但しmodの所(11と7)は互いに素です。
考え
11で割ると3余り、7で割ると5余る…という数をNとすると、
$ N = 11x + 3 = 7y + 5 \ \ (x,y \in \mathbb{Z})
のように表せます。右側を取り出して整理すると
$ 11x - 7y = 2
が導けます。これはいつもの不定方程式の形です。これを解くことで
$ x = 7k + 4かつ$ y = 11k+6 \ \ (k \in \mathbb{Z})が得られます。
ここで序盤の式$ N = 11x + 3に$ x = 7k + 4を代入して整理すると、
$ N = 77k + 47、すなわち
$ N \equiv 47 \pmod{77}が導けます。やった〜
考え(バージョン2)
aで割ってαあまり、bで割ってβあまる…という条件を満たす整数xを求めていきたい…
但しaとbは互いに素。
まず、互いに素なので、$ ax + by = 1…① となるx,yが存在する。
このとき、$ byα + axβは条件を満たすxのうちの1つである。
aで割ったら①より by≡1(mod a) だったり、 axβは割り切れたりで実質 $ 1\cdot α + 0 = α
bで割ったら①より ay≡1(mod b) だったり、 axβは割り切れたりで実質 $ 0 + 1\cdot β = β