「ベズーの等式」の版間の差分
削除された内容 追加された内容
リンク貼替え (Wikipedia:Bot作業依頼, oldid=57465452 による) |
m →証明: (高木「初等整数論講義」に沿った証明にしました。） |
||
38行目:
== 証明 ==
ベズーの補題は性質を定義する[[除法の原理]]、すなわち <math>0</math> でない整数 <math>b</math> による割り算は <math>\left | b \right |</math> よりも真に小さい[[余り]]をもつことの結果である。以下の証明は任意の[[ユークリッド整域]]に対して適用することができる。
与えられた <math>0</math> でない整数 <math>a</math> と <math>b</math> に対して、<math>x</math> と <math>y</math> を整数として <math>ax + by</math> のとりうる整数の集合 <math>\mathit{S}</math>について、<math>\mathit{S}</math> の任意の要素 <math>u, v</math> および整数 <math>k</math> に対して <math>u + v, ku</math> は <math>\mathit{S}</math> に含まれる。実際、<math>u, v</math> が <math>u = ax_1 + by_1, v = ax_2 + by_2</math> と書ければ、<math>u + v = a(x_1 + x_2) + b(x_2 + y_2) \in \mathit{S}, ku = a(kx_1) + b(ky_1) \in \mathit{S} </math> である。
今 <math>\mathit{S}</math> に含まれる正の整数のうち最小の数を <math>h</math> とする。すると、<math>\mathit{S}</math> の要素はすべて <math>h</math> の倍数になっている。
というのは、もし <math>h</math> の倍数で表せない数 <math>m</math> が存在すると仮定すると <math>m</math> を <math>h</math> で割った商を <math>q</math>、<math>0</math> でない余りを <math>r</math> と置いて <math>m = qh + r</math> と書け、<math>r = m - qh</math> より <math>r \in \mathit{S}</math>。<math>r</math> は割り算の余りなので割る数 <math>h</math> より小さく、
これは <math>h</math> が <math>\mathit{S}</math> の最小の数であるという仮定に反する。すなわち <math>\mathit{S}</math> の要素はすべて <math>h</math> の倍数になっている。
<math>ax + by</math> の式で <math>x = 1, y = 0</math> を代入すれば <math>a</math> となるから、<math>a \in \mathit{S}</math>、同様に <math>b \in \mathit{S}</math>。
ということは、<math>a, b</math> は <math>h</math> の倍数であり、<math>h</math> は <math>a, b</math> の公約数である。したがって <math>a, b</math> の最大公約数 <math>g</math> 以下であるから <math>h \leqq g</math>。……①
また <math>a, b</math> は <math>g</math> の倍数だから、<math>a = a'g, b = b'g</math> と置いて、<math> ax + by = (a'x + b'y)g</math> となり、<math>\mathit{S}</math> の要素は <math>g</math> の倍数である。
特に <math>h \in \mathit{S}</math> も <math>g</math> の倍数だから、<math>h \geqq g</math>。……②
①②より <math>h = g</math>、すなわち、<math>ax + by = d</math>（<math>d</math> は <math>a, b</math> の最大公約数）を満たす <math>x, y</math> が存在する。
== 一般化 ==
| |||