T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS ユークリッドの互除法とか、、

<<   作成日時 : 2017/07/30 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

ガロア理論の頂を踏む」を入手して読み始めたのですが、初っ端の「ユークリッドの互除法」辺りで躓きました。どうも整数論というのが苦手ですね。これをゆっくりと考えてみたいと思います。つまり高いレベルの内容を期待しないで下さい。悪しからず。。

・最大公約数の例題

「12 と 32 の最大公約数を求めよ。」

まあ直観でも答えは 4 なのは分かりますが、これをこんな風に考えてみます。

12cm×32cm の板があるとします。
画像

12 と 32 の最大公約数があるとして、それを r とすると、この板は r2 の正方形を並べて埋め尽くすことができる訳ですね。r は 12 の約数なので、その小正方形は 12cm×12cm の正方形も埋め尽くすことができます。
画像

この図のように、 12cm×12cm の正方形が2つ取れるのですが、この正方形は r2 の正方形で埋め尽くすことができ、12cm×32cm の板も r2 の正方形で埋め尽くすことができるので、この2つの正方形を取り除いた部分も r2 の正方形で埋め尽くすことできることになります。
画像

残った部分を同じ考えで、正方形を取り除いていくと最後は同じ正方形しか残らなくなるでしょう。もう一度組み立て直すと
画像

画像

つまり、「12 と 32 の最大公約数は 4 」ということが分かったことになります。

この経過を式で追うと、
画像


この例題は直観でも分かるため、もう一つ例題をやってみましょう。

851 と 185 の最大公約数を求めよ。
画像


ここで、「互除法の原理」をまとめると

定理1.1「互除法の原理」-------------------------------------------------
の最大公約数を表すことにする。
を自然数とする。 で割った余りが のとき、次が成り立つ。
   
-------------------------------------------------------------------

証明

とすると、自然数 を用いて
     ……@
で割った商を 、余りを とすると、 から
     ……A

このAに@式を代入すると、
   
となり を約数として持つということですが、 はもともと を約数として持ちます。
つまり、 の公約数ですが、公約数は最大公約数以下なので、 です。
 
また、 の倍数なので、自然数 を用いて
   
これを、 に代入すると
   
を約数を持ちますが、 はもともと を約数を持つため、 の公約数です。
公約数は最大公約数以下なので、 です。


なお、 の最大公約数が のとき、互いに素であるといいます。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
ユークリッドの互除法とか、、 T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる