新規登録 ログイン

13_80 整数の性質 / ユークリッドの互除法

ユークリッドの互除法の証明

著者名: スレイマン
Text_level_1
マイリストに追加
ユークリッドの互除法の原理

a,b,q,d,rを自然数とします
a÷b=q…r とします
このとき、
dがaとbの公約数である⇔dがbとrの公約数である
証明

まず(⇒)を示します
左側を仮定として右側を示すということです
dがaとbの公約数なので自然数m,nを用いて
a=md,b=nd と表せますので、これを代入すると
a÷b=q…r ⇔md÷nd=q…r
⇒md-ndq=r (わり算の定義より)
⇔d(m-nq)=r ・・・ (ア)
自然数から自然数の和または差または積は整数になるという法則(☆)があります
m-nqはこの法則が当てはまります
何故なら
①mは自然数
②nqは自然数(nとqが両方自然数だから)
①②より、m-nqも、自然数から自然数をひいた数です
したがってm-nqは整数なので
(ア)よりdはrの約数です
さらに仮定よりdはbの約数でもありましたから
"dがbとrの公約数である"と示せました。
次に()を示します
左側を仮定として右側を示すということです
さっきのmとnでなく新しくm,nを設定します
dがrとbの公約数なので自然数m,nを用いて
r=md,b=nd となるようなm,nが存在するので、これを代入すると
a÷b=q…r ⇔a÷nd=q…md
⇒a=ndq+md (わり算の定義より)
⇔a=d(nq+m) ・・・ (イ)
さっきの法則(☆)をまた使います
nqとmをは両方自然数なのでたしても自然数です
よって(イ)よりdはaの約数です
仮定よりdはbの約数でもあります
したがって"dがaとbの公約数である"と示せました
最大公約数の求め方への応用

ユークリッドの互除法の原理より、
aとbの最大公約数xはbとrの公約数でもあります(⇒より)ので
bとrの最大公約数をyとするとy≧x
一方yもaとbの公約数なのだが(より)、aとbの最大公約数はxなのでx≧y
するとx=y
なので、aとbの最大公約数はbとrの最大公約数と一致します
なのでa÷bを計算してbとr(あまり)の最大公約数を求めれよいことになります
繰返し使うこともできます
bとrを新しくaとbと見なしておなじことをするのです
具体的な数字で実験してみてください

Related_title


Keyword_title

Reference_title
脳内

この科目でよく読まれている関連書籍

このテキストを評価してください。

※テキストの内容に関しては、ご自身の責任のもとご判断頂きますようお願い致します。

 

テキストの詳細
 閲覧数 1,286 pt 
 役に立った数 0 pt 
 う〜ん数 1 pt 
 マイリスト数 0 pt 

知りたいことを検索!

まとめ
このテキストのまとめは存在しません。