中国剰余定理について風あざみ 2014/04/01 目次 1 証明の準備編 2 2 中国剰余定理の証明編 2 1 1 証明の準備編定理１：a, b を互いに素な正の整数とする。このとき、ax + by = 1 をみたす整数 x, y が存在することが言える。証明：整数の集合 I を以下のように定義する。 I = {k は整数 | 整数 s, t を用いて、k = as + bt とかける。} a = a · 1 + b · 0 ∈ I, b = a · 0 + b · 1 ∈ I だから、I は正の整数 a, b を元に持つ。 I の正の元のうち、最小になるものを e とする。I の元 k を任意にとるとき、k は e で割り切れることを証明する。まず k が e で割り切れないと仮定する。このとき、k を e で割った時の商を q 、余りを r とすると、以下のように書ける。 k = eq + r, 0 < r < e ここで、k, e ∈ I だから整数 s, t, u, v が存在して、以下のように書ける。 k = as + bt, e = au + bv r = k − eq = a(s − uq) + b(t − vq) ∈ I だから、r は I の元となる。ところが 0 < r < e だから、r は e より小さな正の整数であることがわかる。このことは、e の最小性に反する。したがって、k が e で割り切れないという仮定は誤りで、k は e で割り切れることが証明された。特に、I の元 a, b が e で割り切れることがいえる。e ≥ 2 と仮定すると、e が a, b の 2 以上の公約数となり、a, b を互いに素であることに反する。よって、e = 1 であること、つまり au + bv = 1 が証明された。以上より、ax+by = 1 をみたす整数 x, y の存在が言えた。 □ 定理２：a, b, c を正の整数とする。ax + by = 1 と ax + cy = 1 がともに整数解を持つとき、ax + bcy = 1 も整数解を持つ。証明： ax + by = 1 の整数解を (x1 , y1 )、ax + cy = 1 の整数解を (x2 , y2 ) とすると、a(ax1 x2 + cx1 y2 + bx2 y1 ) + bc(y1 y2 ) = 1 よって、ax+bcy = 1 も整数解を持つことがいえた。 2 □ 中国剰余定理の証明編定理３：n を正の整数、m1 , m2 , · · · , mn をどの二つをとっても互いに素となるような正の整数とする。a1 , a2 , · · · , an を任意の整数とする。すると z ≡ a1 (mod m1 ) 2 z ≡ a2 (mod m2 ) ·················· z ≡ an (mod mn ) を同時に満たす整数 z が存在する。証明： n = 1 のときは明らか。n = h のとき定理３の条件をみたす zh の存在を仮定する。 n = h + 1 のときを考える。 m1 と mh+1 、m2 と mh+1 、…、mh と mh+1 は互いに素だから定理１より、 m1 x + mh+1 y = 1 m2 x + mh+1 y = 1 ·················· mh x + mh+1 y = 1 がすべて整数解を持つことが言える。したがって、定理２を繰り返し適用すると、 m1 m2 · · · mh x + mh+1 y = 1 が整数解、(xh , yh ) を持つことがいえる。整数 zh+1 を以下のようにとる。 zh+1 = m1 m2 · · · mh xh · ah+1 + mh+1 yh · zh m1 , m2 , · · · , mh から任意に mi をとるとき、以下が言える。 zh+1 ≡ mh+1 yh · zh ≡ (1 − m1 m2 · · · mh xh )zh ≡ zh ≡ ai (mod mi ) また、以下のことも言える。 zh+1 ≡ m1 m2 · · · mh xh · ah+1 ≡ (1 − mh+1 yh )ah+1 ≡ ah+1 (mod mh+1 ) よって n = h + 1 のときも、定理３の条件をみたす整数 zh+1 の存在がいえるので、任意の正の整数 n に対して、定理３が成り立つことが示された。定理３は中国剰余定理そのものである。 3 □