連立合同方程式②

もう少し話を進めよう。

a≡1(mod4)，a≡3(mod7) を同時に満たす整数aの求め方についてだ。

ガウスの方法で求めてみよう。

まず，4α+7β=1を満たす整数α，βを一組求める。

例えばα=2，β=-1である。

これさえ見つかれば，

a=1×7β+3×4αと置くだけでほぼ終わりである。

なぜならば，4α+7β=1において，

法を4とすれば7β≡1(mod4)，法を7とすれば4α≡1(mod7)

だから，a=1×7β+3×4αは，a≡1(mod4)，a≡3(mod7)を必ず同時に満たすことになる。

a=-7+24=17

よって，a=17+28k (kは整数)

この技はガウスの名を関してはいるが、百五減算の仕組みと同じである。