http://goo.gl/MFRFj 130107 初版 141104 更新
トップページ
a, b, cを整数とするとき，
1次不定方程式 ax+by=c の
整数解 (x,y) を求めてみよう。
ここでは理論を記す。
互除法を用いた構成的な解法は
こちら
例題とその解法は
こちら (互除法はなるべく使わない)
ざっくりとした機械的な計算方法は
こちら (逆行表と呼ぶ人がいる 互除法の拡張)
スクリプトによる自動計算は
こちら (ディオファントス計算器)
以下，
この頁では断りのない限り文字は整数である。
このあたりは二千年の伝統のある分野である。
理論はとうにできている。
高校の教科書にあるのは，本来理論を
構築する
こと自体が目的だから，
以下を安易にみてはいけない。
a, b が 1より大きい公約数 d をもつとすると，
ax+by は d の倍数である。
ところが， d の倍数 任意の c に対して，
ax+by=c が解をもつかどうかは，問題である。
ax+by=d が解をもってしまえば，
kx, ky は ax+by=kd の解だから，
ax+by=d が解をもつかどうかが問題である。
特に，
a, b が 互いに素であるとき，
ax+by=1 は解をもつ。
初級者には次の証明は少し理解しがたい。
存在を示す証明はしばしば理解しがたい。
こちらでは
構成的な証明をしてみるが，
数列(逐次)の考えが必要である。
合同式を使うが，それが難しい根本原因ではない。
ax+by=1 を満たす整数解を求めることは，
合同式 ax ≡ 1 (mod b) を満たす x を求めることである。
整数を b を法として分類すると，
0, 1, 2, 3,… b-1 の b 通りがあるが，
x はこのうちの 0 を除いた b-1 個のうちのどれかである。
また，ax を b で割った余りも
0, 1, 2, 3,… b-1 の b 通りがあるが，
ax はこのうちの 0 を除いた b-1 個のうちのどれかである。
(a と b は互いに素だから)
いま，x から ax への対応は1対1であることを示そう。
\(ax_1\equiv ax_2\) (mod b)
⇔ \(a(x_1-x_2)\) は b の倍数 である
a, b は互いに素だから，\(x_1-x_2\) は b の倍数である。
数の合同の定義によって，\(x_1 \equiv x_2\) (mod b)
対偶をとって，
\(x_1\not\equiv x_2\) ⇔ \(ax_1\not\equiv ax_2\) (mod b)
したがって，x から ax への対応は1対1であることがいえたので，
x が 1 から b-1 までの b-1 個あるならば，
ax も 1 から b-1 までのちょうど b-1 個ある。
(
鳩の巣原理)
よって，ax ≡ 1 (mod b) を満たす x は存在する。
例
32x-15y=1を満たす (x,y) を求める。
これは，
32x ≡ 1 (mod 15) を満たす x を求めること同じであり，さらに，
32 を 15 で割った余りは 2 だから，
2x ≡ 1 (mod 15) を満たす x を求めることと同値である。
| x |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
| 2x (mod 15) |
0 |
2 |
4 |
6 |
8 |
10 |
12 |
14 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
よって(探してみたら)，x = 8 が解である。
このとき，32 × 8 - 15y = 1 を解いて，y=17
一般解は整数 k を用いて，
x = 8 + 15k, y=17 + 32k