【ユークリッドの互除法】最大公約数の計算

ユークリッドの互除法で最大公約数を求めるアルゴリズムをまとめました。

ユークリッドの互除法

「ユークリッドの互除法」とはｍ２つの自然数 a，b の最大公約数を効率的に計算する方法で、世界最古のアルゴリズムとしても有名です。

ユークリッドの互除法では、「aをbで割ったときの余りrとすると、aとbの最大公約数とbとrの最大公約数が等しくなる」性質を用いています。

ユークリッド互除法で2つの自然数a, bの最大公約数を求める手順は以下の通りです。

※2つの自然数a, bのうち大きい方をa, 小さい方をbとする

例題

ユークリッド互除法の計算例として、「54545454」と「121212」の最大公約数を求めてみます。

54545454 ÷ 121212 = 450 余り 54
121212 ÷ 54 = 2244 余り 36
54 ÷ 36 = 1 余り 18
36 ÷ 18 = 2 余り 0

余りr=0になったときのb(割られる数)は18なので、最大公約数は18となります。