ax + by = n の整数解および正の整数解について風あざみ 2014/03/27 目次 1 証明の準備編 2 2 ax + by = n の整数解編 2 3 ax + by = n の正の整数解編 3 1 1 証明の準備編定理１：a, b, c を正の整数とする。bc が a で割り切れ、かつ a と b が互いに素ならば、c が a で割り切れる。証明：整数の集合 I を以下のように定義する。 I = {h は整数 |hc が a で割り切れる。} ac, bc は a で割り切れるから、I は正の整数 a, b を元に持つ。I の正の元のうち、最小になるものを e とする。I の元 h を任意にとるとき、h は e で割り切れることを証明する。h が e で割り切れないと仮定する。このとき、h を e で割った時の商を w、余りを r とすると、以下のように書ける。 h = ew + r, 0 < r < e ここで、h, e ∈ I だから整数 u, v が存在して、hc = au, ec = av と書ける。 rc = (h − ew)c = hc − (ec)w = a(u − vw) ∈ I だから r は I の元となる。ところが 0 < r < e だから、r は e より小さな正の整数であることがわかる。このことは、e の最小性に反する。したがって、 h が e で割り切れないという仮定は誤りで、h は e で割り切れることが証明された。特に、I の元 a, b が e で割り切れることがいえる。e ≥ 2 と仮定すると、e が a, b の 2 以上の公約数となり、a, b を互いに素であることに反する。よって、e = 1 であること、つまり c = ec = av であることがいえるので、 c が a で割り切れることがいえた。 □ 2 ax + by = n の整数解編定理２：a, b を互いに素な正の整数とする。このとき、任意の整数 n に対して、ax + by = n は整数解 (x, y) を持つ。証明：a 個の整数 n−b, n−2b, · · · , n−ab を考える。この中に a の倍数が存在することを証明する。もしそうでなければ、a 個の整数 n − b, n − 2b, · · · , n − ab を a で割った時の余りで考えられるのは 1, 2, · · · , a − 1 の a − 1 種類だから、鳩の巣の原理より以下のような 2 数が存在する。 1 ≤ i < j ≤ a をみたす整数 i, j が存在して、n − bi ≡ n − bj (mod b) が成り立つ。したがって、b(j −i) = (n−bi)−(n−bj) は a で割り切れる。ここで、a と b が互いに素だから、定理１より j − i は a で割り切れることがわかる。ところが、 0 < j − i < a だから不合理。したがって、a 個の整数 n − b, n − 2b, · · · , n − ab の中に a の倍数が必ず存在する。それを n − bt とすると、整数 s が存在して 2 as + bt = n と書ける。整数 s, t が問題の条件をみたす、x, y であることは明らかである。 □ 定理３：a, b を互いに素な正の整数とする。整数 n を任意にとるとき、ax+by = n の任意の整数解 (x, y) は定理２の解を、(x0 , y0 ) とするとき、x = x0 −bk, y = y0 + ak と書ける (ただし、k は任意の整数とする)。証明：ax + by = ax0 + by0 = n だから b(y − y0 ) = a(x0 − x) がいえる、よって、b(y − y0 ) は a で割り切れる。ここで、a と b が互いに素だから、定理１より y − y0 は a で割り切れる、よって整数 k が存在して、y = y0 + ak がいえる。これを b(y − y0 ) = a(x0 − x) に代入すると、x = x0 − bk となる。逆に、x = x0 − bk, y = y0 + ak と書けるとき (ただし、k は任意の整数)、 ax+by = ax0 +by0 = n となる。したがって、定理３はいえた。 □ 3 ax + by = n の正の整数解編定理４：a, b を互いに素な正の整数とする。このとき、n > ab をみたす任意の整数 n に対して、ax + by = n は 1 ≤ y ≤ a をみたす正の整数解 (x, y) を持つ。証明：a 個の整数 n−b, n−2b, · · · , n−ab を考える。この中に a の倍数が存在することを証明する。もしそうでなければ、a 個の整数 n − b, n − 2b, · · · , n − ab を a で割った時の余りで考えられるのは 1, 2, · · · , a − 1 の a − 1 種類だから、鳩の巣の原理より以下のような 2 数が存在する。 1 ≤ i < j ≤ a をみたす整数 i, j が存在して、n − bi ≡ n − bj (mod b) が成り立つ。したがって、b(j −i) = (n−bi)−(n−bj) は a で割り切れる。ここで、a と b が互いに素だから、定理１より j − i は a で割り切れることがわかる。ところが、 0 < j − i < a だから不合理。したがって、a 個の整数 n − b, n − 2b, · · · , n − ab の中に a の倍数が必ず存在する。それを n − bt とすると、整数 s が存在して as + bt = n と書ける。また、as = n − bt ≥ n − ab > 0 より s は正の整数となる。また 1 ≤ t ≤ a がいえるので、整数 s, t が問題の条件をみたす、x, y であることは明らかである。 □ 3