【導入】ユークリッドの互除法

「最大公約数を求めなさい」と言われれば、どうやって計算するでしょうか。一番基本的なやり方は、2で割れるか、3で割れるか、と小さい数字から順番に割っていき、割れる数字のうち共通するものを探していく、という方法だと思います。

例えば、21と35であれば、小さい数字から順に割っていき、「21は3で割れる、でも35は3で割れない。21は7で割れる、35も7で割れる。これ以上大きい数では割れないから、最大公約数は7だな」という流れで出していくと思うんですよね。

しかし、数が大きくなるとこの方法では大変です。例えば「1649と221の最大公約数」を考えてみると、大変さがわかると思います。

このように小さい数字から順番に割っていく方法よりも、もっと早く最大公約数を求める方法があります。それが「ユークリッドの互除法」という計算方法です。

「ユークリッドの互除法」の元になる考え方などは、別ページの【基本】ユークリッドの互除法の使い方で説明するとして、このページでは計算方法だけを紹介し、計算量がどれくらい少ないかを見るにとどめておきます。

「1649と221の最大公約数」を考えます。「ユークリッドの互除法」では、次のように計算していきます。まず、1649を221で割ってその余りを求めます。計算すると、余りは102になります。次に、今度は221を102で割り、余りを求めます。このように、余りが0になるまで計算していきます。

221を102で割った余りは17です。続いて、102を17で割った余りを求めると、これはちょうど割り切れて余りが0になります。このときの最後の数字「17」、これが実は最大公約数になるんですね。

小さい数字から順番に割っていくやり方に比べると、ずいぶん簡単に求められることがわかると思います。順番に割っていく方法だと、「17」にたどり着くまでにかなり計算しないといけません。もっと数字が大きくなるとさらに大変になります。

除法というのは、割り算のことです。互除法というのは、上のように、「お互い割っていく」という方法なんですね。

【基本】ユークリッドの互除法の使い方以降のページでは、ユークリッドの互除法の考え方や具体的な計算方法について、解説していきます。