最大公約数を利用して最小公倍数を求める

「最大公約数」と問われると「ユークリッドの互除法！」とただちに着想が湧くようにはなってきた。

　その一方で「最小公倍数」と問われたら、「おや…」と思いながら調べ直さざるをえない自分がいた。

　この記事できちんと整理して、記憶に定着させたい。

定理

正整数に[tex:{\displaystyle a}], [tex:{\displaystyle b}]に対して、[tex:{\displaystyle a}]と[tex:{\displaystyle b}]の最大公約数[tex:{\displaystyle \mathrm {gcd} (a,\ b)}]と最小公倍数[tex:{\displaystyle \mathrm {lcm} (a,\ b)}]との間には [tex:{\displaystyle \mathrm {gcd} (a,\ b)\cdot \mathrm {lcm} (a,\ b)=ab}] という関係がある。¹

実践

　つまりAとBの最小公倍数LCMは、AとBの最大公約数GCDを使ってこう書ける。

[tex:{\displaystyle \mathrm {lcm} (a,\ b)=\frac{ab} {\mathrm {gcd} (a,\ b)}}]

　要するに、まずは最大公約数をユークリッドの互除法で求めてから、単純計算で最小公倍数を求めればよい。[tex:{\displaystyle A \geq B}] として、

#include <iostream>

int main() {
  int A = 24, B = 18;
  int a = A, b = B, r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }

  int gcd = b;
  int lcm = A * B / gcd;

  printf("%d\n", lcm);
  return 0;
}

　全体の計算量はユークリッドの互除法の計算量に従って O(logn) となる。