倍数と約数・基本問題８・解答

　講座・問題集

（解答）

　217と155の最大公約数を求める。

　217÷155=1…62

　155÷62=2…31

　62÷31=2

　よって、217と155の最大公約数は、31

（答え）　31

（重要）

　通常の方法で簡単に公約数が見つからない場合（2，3，5など簡単な公約数がない場合）は、この問題の解答で用いたユークリッドの互除法を用いて最大公約数を求めてください。

【ユークリッドの互除法】

　ＡとＢの最大公約数を求める。（Ａ＞Ｂ）

　Ａ÷Ｂ=Ｃ…Ｄ

　Ｂ÷Ｄ=Ｅ…Ｆ

　Ｄ÷Ｆ=Ｇ…Ｈ

　という計算を割り切れるまでくり返した時、最後の式の除数（割る数）が最大公約数となる。

　（注）　最大公約数が1となる2つの整数は、“互いに素”である。

　←　問題に戻る　　　　　次の問題　→