|
|
|
更新日時:
|
|
![]() |
ユークリッドの互除法の証明 |
著作名:
スレイマン
11,117 views |
ユークリッドの互除法の原理
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の公約数なのだが(
するとx=y
なので、aとbの最大公約数はbとrの最大公約数と一致します
なのでa÷bを計算してbとr(あまり)の最大公約数を求めれよいことになります
繰返し使うこともできます
bとrを新しくaとbと見なしておなじことをするのです
具体的な数字で実験してみてください
このテキストを評価してください。
役に立った
|
う~ん・・・
|
※テキストの内容に関しては、ご自身の責任のもとご判断頂きますようお願い致します。 |
|
ユークリッドの互除法
>
最近見たテキスト
ユークリッドの互除法の証明
10分前以内
|
>
|
数学A
- 場合の数と確率
- 場合の数/順列/組合せ
- 確率
- 整数の性質
- 約数と倍数
- ユークリッドの互除法
- 整数の性質の活用
- 図形の性質(平面図形/空間図形)
- 三角形の辺と角
- 三角形の外心・内心・垂心・重心
- 三角形の定理(中線定理/メネラウスの定理/チェバの定理)
- 円の基本性質
- 円と直線(接弦定理/方べきの定理/共通接線)
- 空間図形
- その他
- その他