最大公約数の計算

ある数(正の整数とします)aがあったとき、aを割り切る数のことをaの約数と呼びます。
たとえばaが10ならば、aを割り切る数は、1, 2, 5, 10 になります。これらが10の約数です。

では、ある数aとbがあったときはどうでしょうか。aとbを割り切る数もありますね。これをaとbの公約数とよびます。
たとえばaが10で、bが15だったとします。aを割り切る数は、1, 2, 5, 10。bを割り切る数は、1, 3, 5, 15。なので、aとbの公約数は、1と5です。

公約数のなかで一番大きなものを最大公約数と呼びます。さきほどの例(10と15)であれば、最大公約数は5です。

最大公約数を計算してみます。

最大公約数はです。

最大公約数の計算は、

「aとbのうち、大きいほうから小さいほうを引く」を繰り返す=>いつか同じになるので、その値が最大公約数
という方法を取っています。(中学校の数学の授業では異なる方法かもしれません。)

関連計算式