本稿は大きい数同士の最大公約数を素早く求めることの出来る計算方法である「ユークリッドの互除法」についてのまとめと(Python3.x系で)実装スクリプトを自分用に記事にしたものです。

勉強中のため記述内容に間違い等あるかもしれません。その場合、申し訳ありませんがコメント等でご指摘いただけると幸いです。
※Zennにも筆者本人が転載済み。

ユークリッドの互除法とは？

ユークリッドの「互除法」とは**「割り切れるまであまりで互いに割り（除法）続ける」という意味。これを使って大きな数字たちの最大公約数を素早く計算する方法。**
(計算量がなぜO(log2N)になるのかについては後日加筆予定。)

前提1 最大公約数とは

2つ以上の正の整数の共通の約数のうち最大の数字。

例えば12と18の最大公約数は6。9と120の最大公約数は3。¹

前提2 ユークリッドの互除法はなぜ成り立つのか

aとbの最大公約数をgcd(a, b)とする。²

例えばgcd(12, 18) = 6

割り算の等式：a = b * q + r
上記が成り立つ時
gcd(a, b) = gcd(b, r)

上記がなぜ成り立つのでしょうか？

3段階にわけて考えればわかります。

割り算の等式：a = b * q + r
があるとき、gcd(a, b) = G1, gcd(b, r) = G2とします。

(1)
r = a - b * q = G1(a' - b' * q')と変形できます。
つまりrの約数にはG1があるわけです。gcd(b, r)はbとrの最大公約数なので下記が言えます。
gcd(r, b) >= gcd(a, b)
つまり、G2 >= G1

(2)
a = G2(b'' * q''　+ r'')と変形できます。
つまりaの約数にはG2があるわけです。gcd(a, b)はaとbの最大公約数なので下記が言えます。
gcd(a, b) >= gcd(r, b)
つまり、G1 >= G2

(3)
上記ふたつより、G1 = G2が言えます。

使い方

実際に3355と2379の最大公約数を求めてみるのを

紙に書いてやってみましょう。(下記はスタディサプリさんの解説サイトから引用。)

すぐにわからない方は上記と前提で述べた条件を付き合わせて考えてみましょう。

a ÷ b = q あまり r ⇒ gcd(a, b) == gcd(b, r)

b ÷ r = q'あまりr' ⇒ gcd(b, r) == gcd(q', r')

これを上記の画像と同じ具体例に当てはめると、


3355 ÷ 2379 = 1 あまり 976 ⇒ gcd(3355, 2379) == gcd(2379, 976)

2379 ÷ 976 = 2 あまり 427 ⇒ gcd(2379, 976) == gcd(976, 427)

...省略

122 ÷ 61 = 2あまり0 ⇒ gcd(122, 61) == gcd(61, 0) == 61

遡って考えればgcd(3355, 2379) == 61。つまりgcd(a, b)は最後まで割り切ったときの割る数と等しいことがわかります。

まずは最大公約数を普通にだす

普通に出してみましょう。これでも小さい数なら時間がかからず解けます。

# first, secondのうち小さい方を最大値としてそこから-1ずつして両方を割り切れるものを探す
def boring_gcd_method(first, second):
    limit = min(first, second)
    # print("limit", limit)  # debug
    for i in range(limit, 0, -1):
        # print("i", i)  # debug
        if first % i == 0 and second % i == 0:
            return i  # int

ユークリッドの互除法で出す

上記のやり方でも良いのですが、例えば239520000と1293400200の最大公約数を求めるのとかだと時間がかかって面倒そうです。

# a = b * q + r, gcd(a, b) == gcd(b, r)
def euclidean_algo(first, second): # good
    while second:
        first, second = second, first % second
        # print("first, second", first, second)  # debug
    return first  # int

参考サイト

Studyplus ユークリッドの互除法

高校数学の美しい物語ユークリッドの互除法の証明と不定方程式

ちなみに(今回は関係ないが)「互いに素」とは最大公約数が1である数字同士であるということ。例えば3と10は最大公約数が1なので互いに素であると言える。 ↩
Greatest common divisorの略 ↩