実装例あり!最大公約数gcd・最小公倍数lcmを求める

最近(半年前くらい)プログラミングコンテストに参加し始めた。
その中で最大公約数だったり最小公倍数だったりを使う問題が結構たくさんあるのだが、
忘れんぼさんで毎回毎回何だったけなぁとなって、その度に調べていていい加減めんどくさくなってきたので、
自分の理解を一度アウトプットしておいて理解の定着を図ることにした。
未来の自分と、このブログにたまたまたどり着いた幸運な(?)読者の方に参考になれば幸いです。

また、競プロ関連の記事は他にも書いています。今後必要なことを拡充していきたいと思いますので参考にしてみて下さい！
→「プログラミングコンテスト」一覧

最大公約数
最大公約数を求める~Euclidの互除法~
gcdをc++で実装してみた
最小公倍数
最小公倍数を求める
lcmを求める関数の実装
まとめ

最大公約数

最大公約数とは、少なくとも一つが0ではない複数の整数の公約数のうち最大のものである。(Wikipedia)
例えば6(\(=2\times 3\))と12(\(=2^{2}\times 3\))の最大公約数は6だし、792(\(=2^{3}\times 3^{2}\times 11\))と9108(\(=2^{2}\times 3^{2}\times 11\times 23\))だったら396である。
整数\(a\)と\(b\)の最大公約数をgcd\(\left(a,b\right)\)と書く。

最大公約数を求める~Euclidの互除法~

Euclidの互除法とは2つの整数の最大公約数を求める方法である。(Wikipedia)

任意の整数\(a\)は商\(q\)と剰余\(r\)を用いて

\(\begin{eqnarray} a = bq+r \end{eqnarray}\)

と書ける。ここで、\(b\in\mathbb{Z}\)である。

この時、以下のような重要な性質がある。すなわち、

\(a\)と\(b\)の最大公約数は\(b\)と\(r\)の最大公約数になっている

という性質である。
Euclidの互除法はこの性質を利用して最大公約数を求める方法である。

この性質を証明してみよう。
まず、\(a\)と\(b\)の公約数を\(f\)と書く。
この時、整数\(k,k’\)を用いて\(a = kf\), \(b = k’f\)と書けるので、先ほどの式に代入して

\(\begin{eqnarray} kf &=& k’fq+r \\ r &=& f(k-k’q) \end{eqnarray}\)

よって\(a\)と\(b\)の公約数\(f\)は\(r\)の約数でもあることが分かった。
\(f\)を\(a\)と\(b\)の最大公約数にとると、それは\(r\)の約数にもなっていることが分かるので

\(\begin{eqnarray} {\rm gcd}\left(a,b\right)\leq{\rm gcd}\left(b,r\right) \end{eqnarray}\)

逆に\(b\)と\(r\)の公約数を\(g\)と書くと同様にして

\(\begin{eqnarray} {\rm gcd}\left(a,b\right)\geq{\rm gcd}\left(b,r\right) \end{eqnarray}\)

以上2つの不等式より、

\(\begin{eqnarray} {\rm gcd}\left(a,b\right) = {\rm gcd}\left(b,r\right) \end{eqnarray}\)

すなわち、\(a\)と\(b\)の最大公約数は\(b\)と\(r\)の最大公約数に等しいことが分かった。

実際にEuclidの互除法をやるときは与えられた一方の整数をもう一方でどんどん割っていって、割り切れた数字が最大公約数である。
流れ的には以下のような感じ。

\(\begin{eqnarray} a &=& bq+r \\ r &=& bq’+r’ \\ r’ &=& bq”+r” \\ \vdots \end{eqnarray}\)

gcdをc++で実装してみた

上の手続きを実装すると以下のようになる¹。

long long gcd(long long a, long long b){
  if(a< b) swap(a,b); //aが常に大きいようにしておく

  if(a % b == 0) return b;
  return gcd(a % b, b);
}

最小公倍数

最小公倍数とは、0でない複数の整数の公倍数のうち最小の自然数をさす。(Wikipedia)
2と3の最小公倍数は6、12と24と96の最小公倍数は96。
整数\(a\)と\(b\)の最小公倍数をlcm\(\left(a,b\right)\)と書く。

最小公倍数を求める

最大公約数と最小公倍数の間には以下のような関係があり、したがって最小公倍数を最大公約数から求めることが出来る。

2つの整数\(a,b\)に対して最大公約数を\({\rm gcd}\left(a,b\right)\equiv g\),最小公倍数を\({\rm lcm}\left(a,b\right)\equiv l\)と書く。このとき

\(\begin{eqnarray} ab = gl \end{eqnarray}\)

が成り立つ。

この関係式を証明し、c++による実装を紹介してこの記事の終わりとしよう。

\(ab\)は最小公倍数\({\rm lcm}\left(a,b\right)\)の倍数であることに着目する。
\(l \equiv {\rm lcm}\left(a,b\right)\)として

\(\begin{eqnarray} ab = kl\,\left(k\in\mathbb{Z}\right) \end{eqnarray}\)

\(k\)は\(a,b\)の約数であり、従って最大公約数\({\rm gcd}\left(a,b\right)\)を割り切る。

一方、実は\({\rm gcd}\left(a,b\right)\)も\(k\)を割り切るのである。
\({\rm gcd}\left(a,b\right)\equiv g\)に対して\(\frac{ab}{g}\)を考えてみると

\(\begin{eqnarray} \frac{ab}{g} &=& a\frac{b}{g} \\ &=& b\frac{a}{g} \end{eqnarray}\)

\(g\)は\(a,b\)の最大公約数なので\(\frac{a}{g},\frac{b}{g}\in\mathbb{Z}\)であるから、\(\frac{ab}{g}\)は\(a,b\)の公倍数である。
従って\(\frac{ab}{g}\)は\(l\)の倍数である。

\(\begin{eqnarray} \frac{ab}{g} = tl\,\left(t\in\mathbb{Z}\right) \end{eqnarray}\)

ここで\(ab = kl\)なので、

\(\begin{eqnarray} \frac{kl}{g} &=& tl \\ \frac{k}{g} &=& t \\ \end{eqnarray}\)

すなわち\(\frac{k}{g}\in\mathbb{Z}\)、つまり\(g\)も\(k\)を割り切ることがわかる。

\(k\)と\(g\)は互いを割り切るので\(k = g\)が言えて、

\(\begin{eqnarray} ab &=& gl \\ &=& {\rm gcd}\left(a,b\right){\rm lcm}\left(a,b\right) \end{eqnarray}\)

が示せた。

lcmを求める関数の実装

上記関係式より、最小公倍数を求めるときは最大公約数を求める関数gcdを使って

long long lcm(long long a, long long b){
  return (a/gcd(a,b))*b;  
}

のようにして求めることができる。
オーバーフローしないように割り算を先にしている。

まとめ

いかがだったでしょうか。

今回は今後の自分のためと、同じような悩みを抱えている方向けに最大公約数・最小公倍数の求め方をまとめてみました。
約数を求めるという意味では過去にこんな記事も書いているので読んでみて下さい！
→実装例付き!約数列挙アルゴリズムについて

個人的には不等式評価のところが数学っぽいなぁと思いました。(お気持ち)

もっとこんなことを記事にしてほしいなどのご要望がありましたら、このページ上部のお問い合わせフォームまたは下部のコメント欄からご連絡いただくか、以下のメールアドレスでもお待ちしております。

tsunetthi(at)gmail.com

(at)の部分を@に変えてメールをお送りください。

または、twitter(@warotan3)もやってますのでそちらに連絡していただいても良きです。

画像はpixabayさんからダウンロードさせていただきました！
ありがとうございます！

Simplicityすげー。見た目の良いソースコードができた。書き方ちょっとくせがあるけど。こちらは直してませんが実はwordpressでコードを直接書くことが出来ます。→Finding GCD and LCM with C++