問題 5-5 2つの整数aとbの最大公約数をgとする。このとき. ともの任意 の公約数cはgの約数であることを証明せよ。 方針 自分で気付けなくてよい これはかなり巧妙な証明です。 (読んで理解できればO.K.) g1 = L(g, c) とおき, g1 = g を証明します。 g1=gが証明できれば、 gとcの最小公倍数がgということなので,gはcの倍数(つまりは gの約数)となります。 91gの証明は, gi≧g...(☆) かつ 91 ≦ g...(☆☆) の2つに分けて証明します。←abanbash この証明方法は,問題7-1 でも用います。

問題 5-5 の別解 aとbの最大公約数がg とするとき、 g= ax + by ... ① ←なぜふい風に となる整数x,yが存在する。 ← p.97 の定理 されるのか 仮定より, [a=ck₁ < 1b = ck cはとりの公約数なのでcはaとの共通の約数 1b=ck2 を満たす整数 k,k が存在する。 ①に代入すると, g = ckx+ckey = c(kix+kzy) よって,g = ck となる整数kが存在する(k=kx+kzy とすればよい)。 したがって, cはgの約数である。 要するに (g = ax + by ベス aとbがcで割り切れるのでもcで割り切れるということ