Skip main navigation

Euclid’s Algorithm/ユークリッドのアルゴリズム(ユークリッドの互除法)

Euclid's Algorithm/ユークリッドのアルゴリズム(ユークリッドの互除法)
© Keio University

もしかすると、皆さんはすでに小学校の頃に、基本的な考え方は学んだかもしれません。例えば、 (20 = 5times 4)、(15 = 5times 3)であり、20と15の最大公約数は5となります。しかし、問題のサイズが大きくなったときにどのくらい大変な問題であるのかを今一度認識しなくてはなりません。この場合そこまで難しい問題ではありませんが、どのように行うかを学ぶことは非常に有意義です。


(126 – 72 = 54)
(72 – 54 = 18)
(54 – 18 = 36)
(36 – 18 = 18)
(18 – 18 = 0)

そして、最後の0でない値が、最大公約数となります。(126 = 7times 18)と、(72 = 4times 18)のようになります。そのため(mathrm{gcd}(126,72) = 18)と書くことができます。途中で (54 = 3times 18)とすぐ気がつくかもしれませんが、その場合数ステップ早く計算を終わらせることができます。

ユークリッドのアルゴリズムは、美しく視覚化することができます。(mathrm{gcd}(x,y))を見つけるために、(xtimes y)の四角形を作ります。そして、その四角形を入りうるる最も大きな正方形(1つもしくは複数の、辺の長さが(x)と (y)の小さい方の正方形)で埋めていきます。


© Keio University
This article is from the free online


Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education