補足
0.
1次不定方程式の整数解が存在するための条件
6は0でない整数とするとき,一般に次のことが成り立つ。
+by=1 を満たす整数x,yが存在するαともは互いに素………(*)
このことは, 1次方程式に関する重要な性質であり, 1次不定方程式が整数解をもつかど
うかの判定にも利用できる。 ここで, 性質 (*)を証明しておきたい。
まず,⇒については,次のように比較的簡単に証明できる。
(*)のの証明]
ax+by=1 が整数解 x=m, y=n をもつとする。
また,aとbの最大公約数をg とすると a=ga', b=gb′
と表され
am+bn=g(a'm+6'n)=1
g=1
よって,gは1の約数であるから
したがって,aとは互いに素である。
◆aとbの最大公約数が
1となることを示す方
針。 p.397 基本例題 103
(2) 参照。
α'm+b'n は整数,
g>0
433
一方の証明については,次の定理を利用する。
4章
aとbは互いに素な自然数とするとき, 6個の整数
a1,a2, a 3, ・・・..., ab をそれぞれ6で割った余りはすべて互いに異なる。
証明 i, jを 1≦i<j≦b である自然数とする。
ai, aj をそれぞれ6で割った余りが等しいと仮定すると背理法を利用。
aj-ai=bk (k は整数)と表される。
よって a(j-i) =bk
差が6の倍数。
aとは互いに素であるから, j-iはもの倍数である。... ①p, gは互いに素で, pr
しかし, 1≦j-i≦b-1 であるから, j-iは6の倍数にはな
がqの倍数ならば, rは
gの倍数である(p,a,
rは整数)。
5
らず,①に矛盾している。
est
したがって,上の定理が成り立つ。
t
[(*)のの証明]
15
ユークリッドの互除法
aとbは互いに素であるから,上の定理により6個の整数α・1,上の定理を利用。
a•2, a·3,......., ab をそれぞれ6で割った余りはすべて互いに
異なる。 ここで,整数を6で割ったときの余りは 0, 1, 2,
6-1のいずれか(通り)であるから, akをbで割った余りが
1となるような整数ん (1≦k≦b)が存在する。識は
akをbで割った商を1とすると
ak=6l+1 すなわち ak+6(-1)=1
よって, x=k, y=-l は ax + by = 1 を満たす。
すなわち, ax+by=1 を満たす整数x, y が存在することが示
された。
このような論法は, 部屋
割り論法と呼ばれる。
詳しくは次ページで扱
ったので、読んでみてほ
しい。
