Twitterフォローよろしくお願いします!

ユークリッドの互除法

スポンサーリンク
スポンサーリンク

今回の問題は「ユークリッドの互除法」です。

問題次の2数の最大公約数をユークリッドの互除法を用いて求めよ。$${\small (1)}~407~,~77$$$${\small (2)}~336~,~180$$

 

スポンサーリンク
スポンサーリンク

ユークリッドの互除法の解法

Point:ユークリッドの互除法整数 \(a~,~b~,~q~,~r\) について、\(a\) を \(b\) で割った商が \(q\)、余りが \(r\) となるとき、$$~~~a=bq+r$$が成り立つとき、
\(a~,~b\) の最大公約数」と「\(b~,~r\) の最大公約数」は一致します。
 
解法の手順は、
\(a\) を \(b\) で割った余り \(r\) を求めます。
② このときの割った数 \(b\) を余り \(r\) で割ります。
③ これを繰り返して、割り切れるまで(余りがなくなるまで)割っていきます。
④ 割り切れたときの割った数が最大公約数となります。

 

問題解説:ユークリッドの互除法

問題解説(1)

問題次の2数の最大公約数をユークリッドの互除法を用いて求めよ。$${\small (1)}~407~,~77$$

\(407\) を \(77\) で割ると、$$~~~407\div77=5\cdots22$$よって、$$407=77\times5+22$$
次に、このときの割った数 \(77\) を余り \(22\) で割ると、$$~~~77\div22=3\cdots11$$よって、$$~~~77=22\times3+11$$
次に、このときの割った数 \(22\) を余り \(11\) で割ると、$$~~~22\div11=2$$よって、$$~~~22=11\times2$$
したがって、答えは
最大公約数 \(11\) となります。

 

問題解説(2)

問題次の2数の最大公約数をユークリッドの互除法を用いて求めよ。$${\small (2)}~336~,~180$$

\(336\) を \(180\) で割ると、$$~~~336\div180=1\cdots156$$よって、$$336=180\times1+156$$
次に、このときの割った数 \(180\) を余り \(156\) で割ると、$$~~~180\div156=1\cdots24$$よって、$$~~~180=156\times1+24$$
次に、このときの割った数 \(156\) を余り \(24\) で割ると、$$~~~156\div24=6\cdots12$$よって、$$~~~156=24\times6+12$$
次に、このときの割った数 \(24\) を余り \(12\) で割ると、$$~~~24\div12=2$$よって、$$~~~24=12\times2$$
したがって、答えは
最大公約数 \(12\) となります。

 

今回のまとめ

ユークリッドの互除法については、解法の手順が重要となります。また、応用問題も様々ありますのでここでしっかりと練習しておきましょう。

【問題一覧】数学A:整数の性質
このページは「高校数学A:整数の性質」の問題一覧ページとなります。解説の見たい単元名がわからない...