■ 其の190 ■ 最大公約数の問題 『30107、52003、58259 の最大公約数 を求めよ。電卓使用OK！』
３０１０７ ５２００３ ５８２５９
小 中 大
どれも約数を見つけるのは難しそう
すべて奇数で、しかも３が約数になっていない
素因数分解できそうにない
困った！
こういう時は、まず２つの数を選んで、公約数を求める
方法は、ユークリッドの互除法
中学生がイメージできるように分かりやすく
大きい数 ÷ 小さい数 ＝ 商 … 余り と書く
Ａ ÷ Ｂ ＝ Ｃ … Ｄ
次にＢとＤについて、同様の式を書く
これを続けていくと、余りが０になる時がくる
余りが０になった時、Ｂが公約数である
では、実戦してみます
まず ３０１０７ ５２００３ を選ぶ
小 中
５２００３ ÷ ３０１０７＝ １ … ２１８９６
３０１０７ ÷ ２１８９６＝ １ … ８２１１
２１８９６ ÷ ８２２１＝ ２ … ５４７４
８２２１ ÷ ５４７４＝ １ … ２７３７
５４７４ ÷ ２７３７＝ ２ … ０
よって、３０１０７ と ５２００３ の公約数は、２７３７
次に ５２００３ ５８２５９ を選ぶ
中 大
５８２５９ ÷ ５２００３＝ １ … ６２５６
５２００３ ÷ ６２５６＝ ８ … １９５５
６２５６ ÷ １９５５＝ ３ … ３９１
１９５５ ÷ ３９１＝ ５ … ０
よって、５２００３ と ５８２５９の公約数は、３９１
次に ３０１０７ ５８２５９ を選ぶ
小 大
５８２５９ ÷ ３０１０７＝ １ … ２８１５２
３０１０７ ÷ ２８１５２＝ １ … １９５５
２８１５２ ÷ １９５５＝ １４ … ７８２
１９５５ ÷ ７８２＝ ２ … ３９１
７８２ ÷ ３９１＝ ２ … ０
よって、３０１０７ と ５８２５９の公約数は、３９１
２つの公約数のうち小さい方が３つの数の最大公約数である
答え ３９１
念のため２７３７ を ３９１で割ってみる
２７３７ ÷ ３９１ ＝ ７
割り切れたのでOＫ！
《 追加説明 》
なぜ３つの数の最大公約数は小さい方なのか？
３つの数の最大公約数は、三つのケースがある
１）公約数が共通の場合
４ ６ １０ のケース
４と６の公約数は ➡２
４と１０の公約数は ➡２
６と１０の公約数は ➡２
もちろん最大公約数は２
２）公約数が２つが同じで１つが異なる場合
４ ６ １８ のケース
４と６の公約数は ➡２
４と１８の公約数は ➡２
６と１８の公約数は ➡６
小さい方の２が最大公約数になる
３）公約数が３つとも異なる場合
６ １０ ３０ のケース
６と１０の公約数は ➡２
６と３０の公約数は ➡６
１０と３０の公約数は ➡１０
一番小さい２が最大公約数になる