1. No category

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