10-01互除法で最大公約数を求める(難易度1)

$623$と$427$の最大公約数を互除法で求めよ

互除法を使おう

$623=427+196$
$427=196\times2+35$
$196=35\times5+21$
$35=21\times1+14$
$21=14\times1+7$
$14=7\times2$
つまり、最大公約数は$7$

大きい数の最大公約数は、共通の約数を見つけるのが直感的にわからないので、
互除法を使い求めます。
計算方法は、図のようにひっ算の形式で計算していくとやりやすいです。
$2$つの数を割ったあまりを求め、そのあまりで割った数を割るということを繰り返していきます。
 

シェアする

  • このエントリーをはてなブックマークに追加

フォローする