ax + by = d の整数解について風あざみ 2015/04/21 定理１：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 の存在が言えた。 1 □ 定理１と同様に下記のことも成り立つ定理２：a, b を最大公約数が d となるような正の整数とする。このとき、 ax + by = d をみたす整数 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 は a, b の公約数となる、したがって e ≤ d がいえる。一方、d は a, b の最大公約数だから、整数 a′ , b′ を用いて a = da′ , b = db′ がいえる。よって e = au + bv = d(a′ u + b′ v) だから、e は d で割り切れる。ここで d, e は正より a′ u + b′ v > 0 がいえるから e ≥ d がいえる。したがって、e = d がいえるから au + bv = d が成り立つことがわかる。以上より、ax+by = d をみたす整数 x, y の存在が言えた。 2 □