ユークリッドの互除法

2018.09.022020.06.09

ユークリッドの互除法の解法
問題解説：ユークリッドの互除法
1. 問題解説(1)
2. 問題解説(2)
今回のまとめ

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

Point：ユークリッドの互除法整数 $a~,~b~,~q~,~r$ について、$a$ を $b$ で割った商が $q$、余りが $r$ となるとき、$$~~~a=bq+r$$が成り立つとき、
「$a~,~b$ の最大公約数」と「$b~,~r$ の最大公約数」は一致します。

解法の手順は、
① $a$ を $b$ で割った余り $r$ を求めます。
② このときの割った数 $b$ を余り $r$ で割ります。
③ これを繰り返して、割り切れるまで（余りがなくなるまで）割っていきます。
④ 割り切れたときの割った数が最大公約数となります。

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

問題解説(1)

問題次の２数の最大公約数をユークリッドの互除法を用いて求めよ。$${\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)

問題次の２数の最大公約数をユークリッドの互除法を用いて求めよ。$${\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$ となります。