スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

スポンサーリンク

ユークリッドの互除法

・ユークリッドの互除法例題1例題2



ユークリッドの互除法は最大公約数を求めるための方法です.これを利用することで比較的大きな整数でも簡単に最大公約数を求めることができます.



【例題 1】

  15436 の最大公約数を求めなさい.




STEP 1
大きい方の数を小さい方の数で割り商と余りを出します.

互除法q1a1
(注) 小数点以下は計算しないでください



STEP 2
(割られる数)=(割る数)×(商)+(余り)という形にしておきます。

互除法q1a2

最大公約数を知りたいだけならこの形に直す必要はありません.しかし,この後に学習する一次不定方程式でこの形を使うことがあるので式を作る練習をしておくことをオススメします.



STEP 3
STEP 2で作った式で(割る数)だったものを(余り)で割ります.同じように商と余りを出して(割られる数)=(割る数)×(商)+(余り)という形にしましょう.先ほどの式では割る数が36,余りが10なので36÷10=3余り6です.

互除法q1a3



STEP 4
1つ前の式の(割る数)を(余り)で割るという操作を繰り返します。余りが0になったら終了です。

互除法q1a4

余りが0になった(割り切れた)式の割る数の部分が最大公約数です。今回は 2 が最大公約数になりました。



【例題 2】

   312274 の最大公約数を求めなさい




まず,大きい方の数を小さい方の数で割り,商と余りを出して(割られる数)=(割る数)×(商)+(余り)の形にする.

  

手前の式で割る数だったものを余りで割ることを繰り返す.

  

  

  

  

余りが0になったときの割る数が最大公約数になる.よって,312と274の最大公約数は2である.



スポンサーリンク

コメント
コメントの投稿
管理者にだけ表示を許可する
スポンサーリンク
最新記事
検索フォーム
ランキング
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。