最大公約数と最小公倍数、計算のお話し

[ つぎ | うえ ]

本節では、コンピュータで最大公約数(G.C.D、Greatest Common Divisor)と最小公倍数(L.C.M、Least Common Multiple)を計算する方法を説明しましょう。

まず、例えば、18 と 24 の最大公約数と最小公倍数を求めてみましょう。最初に、各々を素因数分解します。

18 = 21×32

24 = 23×31

各素数の指数に注目します。18 の場合は、2(素数)に対して1、3(素数)に対して2 であり、24 の場合は、2に対して3、3に対して1 ということになります。

対応する(素数の)指数の小さい方をとって、21×31=6 が最大公約数、逆に、大きい方をとって、23×32=72 が最小公倍数となります。

対応する素数がないように見える場合でも、例えば、18 と 27 の最大公約数と最小公倍数を考えた時に、

27 = 33

は、

27 = 20×33

のように考え、20×32=9 が最大公約数、21×33=54が最小公倍数となります。以上が、人間が「数学」の手順として最大公約数、最小公倍数を求めるやり方です。


では、どうして?

最大公約数とは、2つの整数の各約数で共通なものの最大値でした。では、約数とは、素因数分解したときの以下のような組み合わせとなります。例えば、18 の約数とは、

18 = 21 × 32

で、20 × 30、20 × 31、20 × 32、21 × 30、21 × 31、21 × 32 となり、1、3、9、2、6、18 となります。この様に、素因数分解が係わっています。表にして表すと、以下のようになります。

素数 2 3
指数 0 0
指数 1 1
指数 2

以上の組み合わせで、2×3=6個の約数があることが分かる。

簡単には、最大公約数は、共通なうちで最大の数を求めればよいのだから、指数のうちで小さい方の数を集めてこればよいわけです。例えば、(上の)18 と 24 を考えると、

18 = 2        × 3 × 3

24 = 2 × 2 × 2 × 3

で 2 × 3 が共通となり、21 × 31 = 6 が最大公約数となります(G.C.D)。

最大公約数は、上の2つの数字をみて、空欄を埋めればよい。つまり、

    2 × 2 × 2 × 3 × 3 = 23 × 32 = 72

となります。これは、各指数の大きい方を採用したに過ぎません。以上から、入力する2つの整数A、Bに対して、

        A × B
L.C.M = -------------
         G.C.D

が成立することが分かります。


上の計算方法をコンピュータで実行することを考えると、

  1. 素因数分解をする。
  2. 各素数の指数を検査し、小さい指数を集める。
  3. 各素数を掛け算の形にして計算する。
  4. 結果を出力する。-> 最大公約数
  1. 素因数分解をする。
  2. 各素数の指数を検査し、大きい指数を集める。
  3. 各素数を掛け算の形にして計算する。
  4. 結果を出力する。-> 最大公約数

となりますが、結局、素因数分解をする計算が必要であることがわかります。実際、素因数分解は、コンピュータで計算する場合は大変難しい。実際、セキュリティの分野で採用されているほどです。他の方法を考えよう。ここで、上のような計算の手順アルゴリズム(algorithm)といいます。以下では、アルゴリズムという言葉を使います。

アルゴリズムとは、割り算の筆算のように、「どうして、そうなるの?」(数学的に証明すること)ということが理解できなくても、手順に従って計算することにより答えを求めることができる、という特徴があります。そのため、(コンピュータに知能がなく、人間(プログラマ)に数学的センスがなくても)コンピュータに「埋め込む」ことができるのです。

これは、小学生の時に習った、掛け算、割り算の筆算は、「どうして、答えを求めることができるか?」が理解できなくても答えを求めることができる、ことと同じことです。


最大公約数と最小公倍数を求めるアルゴリズム

最大公約数と最小公倍数を求めるアルゴリズムとして、ユークリッドの互除法を紹介しましょう。

まず、上と同じように 1824 の最大公約数を求めてみよう。

18 と 24 で大きい数、24 から 小さい数 18 を引きます。答えを r0 としよう。

r0 = 24 - 18 = 6

0 と、小さい数18 で、さらに、大きい数から小さい数を引きます。この場合は r0 = 6 と 18 ですから、

r1 = 18 - 6 = 12

となりr1 とします。同様に r1 と 6 から r2 を計算します。

r2 = 12 - 6 = 6

さらに r3 を計算します。

r3 = 6 - 6 = 0

ここで、ri (i>0) が 0 となります。つまり ri (i>0)は、いづれ 0 になります。この0になるひとつ前のrが、最大公約数となります。


この手順をアルゴリズムとして記述すると、

  1. 2つの整数を入力する。i0とする。
  2. 大きい方を、小さい方をBとする。
  3. A-B=ri を計算する。
  4. ri が0の場合5へ、その他の場合は、2つの数をB と riとし、i = i + 1 として 2へ飛ぶ(繰り返し)。
  5. ri-1が最大公約数となり、表示(出力)する。

となり、手順として表すことができます。


次に、最小公倍数

最小公倍数は、以下の公式により簡単に求めることができます。最小公倍数(l.c.m)をL とし、入力する整数値をA、B、最大公約数(G.C.D)をGとすると、

    A × B
L = -----------
      G

で定義することができます。


実は、ユークリッドの互除法とは!

上のアルゴリズムで、引き算ではなく、割り算を使う方法でした。

  1. 2つの整数を入力する。i0とする。
  2. 大きい方を、小さい方をBとする。
  3. A ÷ B = C ・・・ ri を計算する。
  4. ri が0の場合5へ、その他の場合は、2つの数をB と riとし、i = i + 1 として 3へ飛ぶ(繰り返し、B>rは明らか)。
  5. ri-1が最大公約数となり、表示(出力)する。

以上のように定義することができます。

こちらのアルゴリズムの方が、速く解(最大公約数)を求めることができます。


最後に、どうして?

どうして?を理解することができなくても最大公約数を求めることができたのが、アルゴリズムでした。

しかし、ユークリッドの互除法はどうして最大公約数を求めることができるのでしょう。簡単ですが、説明してみようと思います。

引き算の場合

A - B = ri

のA、B、ri は、同じ約数を持つことが理解できますか。A と B が同じ約数(公約数) D を持つとすると、A/D は整数、B/Dも整数となります。そのため、上の両辺を D で割った、

A/D - B/D = ri/D

の ri/D も整数になります。つまり、整数 - 整数 = 整数のためです(A>Bより正の整数)。よって、ri にも同じ約数Dが存在することが分かります。

そのため、A - B = ri繰り返しでは、公約数を保ちながら値が小さくなっていきます。最後に、0 になるので、その一つ前が、(最大)公約数になります。

18と24の場合は、

<A,B> -> <24,18> -> <18,6> -> <12,6> -> <6,6> -> <6,0>

となります。ここで、24、18、12、6 が同じ公約数 6 をもつことがわかります。

割り算の場合

引き算と同様に説明することができます。A ÷ B = C ・・・ riは、A = B ×C +ri(または、ri = A - B ×C) より、AとBの公約数は ri の約数であることが分かります。両辺を公約数Dで割ったとき、(右辺) = 整数 - 整数 × C より、ri/D は整数になります。

お断り:上の説明は、正確な証明ではないことをお断りしておきます(例えば、ri は最終的には0になることは示していません)。


[ つぎ | うえ ]
yasu@i.hosei.ac.jp