互除法の利用

最大公約数を求めるとき、素因数分解をすれば求められます。

ただ、37や61などの大きい素数の場合、見つけるのは困難です。

そこで役立つのがユークリッドの互除法です。
単に互除法と言ったりもします。

「ある2つの自然数a、bがあり、aをbで割った商をp、余りをrとしたとき、aとbの最大公約数はbとrの最大公約数に等しい」

この性質を利用することにより、より小さな数で最大公約数を探すことができます。

文字を含む場合にも有効ですよ。