ax + by = dの整数解について

ax + by = d の整数解について
風あざみ
2015/04/21
定理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 の存在が言えた。
1
□
定理1と同様に下記のことも成り立つ
定理2: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
□