http://goo.gl/MFRFj 130223 初版

トップページ

機械的な計算方法は こちら

スクリプトによる自動計算はこちら

例題1

1次不定方程式 7x+4y=1 の 整数解 (x,y) を求めてみよう。
1つめのポイントは
この式を 7x=-4y+1 変形して，
7の倍数のうちで，4で割って 1余るものを求める問題とみる  ①
実はこれがすべてである。
だから，等差数列の共通項の問題と同値である。
2つめのポイントは
7の倍数の4で割った余りをとること，
3の倍数の4で割った余りをとることは，同値だということ  ②
4で割った余りは，高々4通りしかないから，
少なくともx=1,2,3のうちのどれかが解になる。
よって，(x, y)=(3, -5) を得る。
一組見つければ，一般解は，
7x+4y=1  7×3+4×(-5)=1 の両辺の引き算をして，
7(x-3)+4(y+5)=0
x-3 は4の倍数 (xは4で割って3余る数) だから
整数 k をもって，x=3+4k このとき， y=-5-7k
すなわち (x, y)=(3+4k, -5-7k) (k は任意の整数)
数列の問題もそうだが，
この程度の問題なら， 数にどれだけ親しんでいるかが，問われているだけだと思う。
1次不定方程式はこの ① ② ２つの原理で解ける。

次は，いじわるな問題
例題2

1次不定方程式 33x+16y=1 の 整数解 (x,y) を求めてみよう。
この式を 33x=-16y+1 変形して，
33の倍数のうちで，16で割って 1余るものを求める問題とみる  ①
33の倍数の16で割った余りをとること，
1の倍数の16で割った余りをとることは，同値だということ  ②
よって，(x,y)=(1, -2) を得る。
一般解は，
33x+16y=1  33×1+16×(-2)=1 の両辺の引き算をして，
33(x-1)+16(y+2)=0
x-1 は16の倍数 (xは16で割って1余る数) だから
(x,y)=(1+16k, -2-33k) (k は任意の整数)
互除法なんか使わない。
というか  ② が互除法の思想。

例題3

1次不定方程式 18x+7y=4 の 整数解 (x,y) を求めてみよう。
この式を 18x=-7y+4 変形して，
18の倍数のうちで，7で割って 4余るものを求める問題とみる  ①
18の倍数の7で割った余りをとること，
4の倍数の7で割った余りをとることは，同値だということ  ②
よって，(x,y)=(1, -2) を得る。
一般解は，
18x+7y=4  18×1+7×(-2)=4 の両辺の引き算をして，
18(x-1)+7(y+2)=0
x-1 は7の倍数 (xは7で割って1余る数) だから
(x,y)=(1+7k, -2-18k) (k は任意の整数)
互除法は使わない。
というか  ② が互除法の思想。

例題4

1次不定方程式 7x+33y=1 の 整数解 (x,y) を求めてみよう。
この式を 33y=-7x+1 変形して，
33の倍数のうちで，7で割って 1余るものを求める問題とみる  ①
33の倍数の7で割った余りをとること，
5の倍数の7で割った余りをとることは，同値だということ  ②
よって，(x,y)=(-14, 3) を得る。
一般解は，
7x+33y=1  7×(-14)+33×3=1 の両辺の引き算をして，
7(x+14)+33(y-3)=0
x+14 は33の倍数 (xは33で割って19余る数) だから
(x,y)=(-14+33k, 3-7k) (k は任意の整数)
互除法は使わない。
というか  ② が互除法の思想。

いよいよ 例題5

1次不定方程式 73x+35y=1 の 整数解 (x,y) を求めてみよう。

機械的な計算方法は こちら

73の倍数のうちで，35で割って 1余るものを求める問題とみる  ①
3の倍数のうちで，35で割って 1余るものを求める問題とみる  ②
x=12 が すぐに見つからなかったら， 次のようにする。
Ⅰ \(73x=-35y+1\) となる 整数解を求める
② ⇓
Ⅱ \(3x=-35y_1+1\) となる 整数解を求める
Ⅱ′ \(35y_1=-3x+1\) となる 整数解を求める
② ⇓
Ⅲ \(2y_1=-3x_1+1\) となる 整数解を求める
整数解を辿る。
Ⅰ \(73x=-35y+1\) \((x,y)=(12,-25)\)
⇓ ⇑
Ⅱ \(3x=-35y_1+1\) \((x,y_1)=(12,-1)\)
Ⅱ′ \(35y_1=-3x+1\)
⇓ ⇑
Ⅲ \(2y_1=-3x_1+1\) \((x_1,y_1)=(1,-1)\)
よって，(x,y)=(12, -25) を得る。
一般解は，
73x+35y=1  73×12+35×(-25)=1 の両辺の引き算をして，
73(x-12)+35(y-3)=0
x-12 は35の倍数 (xは35で割って12余る数) だから
(x,y)=(12+35k, -25-73k) (k は任意の整数)
互除法は使わない。
というか  ② が互除法の思想。
これをスクリプトに行わせるのが， ディオファントス計算器

技法を覚えることと， 思想を身につけることでは，少し違いがある。