1 最大公約数の基本
1.1 定義と記法
最大公約数（さいだいこうかんすう、英: greatest common divisor, gcd）は、整数のうち複数の数をすべて割り切る正の整数のうち最大のものを指す。2つの整数a, bについてはgcd(a, b)のように表す。複数個の整数に対しては、そのすべてを割り切る最大の正の整数として定義される。
整数を入力として扱う場合、負の数を含めても割り切り条件は同様に意味を持つが、最大公約数は正の値として定めるのが一般的である。
1.2 性質（割り切りと最大性）
最大公約数は次の2点で特徴づけられる。第一に、最大公約数dは各入力整数を割り切る。すなわちa = d·x、b = d·yのように表せる。第二に、これを満たす正の整数のうちdより大きいものは存在しない。別の言い方をすると、共通の約数全体の集合には最大要素があり、それが最大公約数に一致する。
また、最大公約数は「共通の約数の最大」という観点から、約分や数の分解などにおける共通部分抽出の基本量として働く。
1.3 基本例と確認問題
基本例として、gcd(12, 18)は12と18の両方で割り切れる最大の正の整数である。12の約数は1, 2, 3, 4, 6, 12、18の約数は1, 2, 3, 6, 9, 18であり、共通部分は1, 2, 3, 6となる。最大は6なのでgcd(12, 18) = 6。
確認の観点としては、(1) 共通の約数を列挙して最大を取る、(2) 実際に割り算で余りが0になることを検算する、(3) その約数がそれ以上の値では成り立たないことを確かめる、の3つを押さえると理解が安定する。
2 求め方
2.1 約数の列挙
| 最も直接的な方法は、入力のうち小さい方の絶対値以下の整数を順に調べ、両方を割り切るものを見つけることである。探索範囲は通常、min( | a | , | b | )までで十分である。共通の約数が見つかったら最大を更新し、最後に得られた値が最大公約数となる。 |
|---|
この方法は概念を掴むのに適する一方、入力が大きい場合には試行回数が増えやすい。改善のために、割り切り判定は素早くできるが、それでも「候補をどれだけ調べるか」が計算量を左右する。
2.2 素因数分解による求め方
素因数分解を用いる方法では、各整数を素数の冪の積として表す。例えば a = p1^α1 · p2^α2 · …、b = p1^β1 · p2^β2 · … のようにすると、共通する素数のうち冪指数が小さい方を取った積が最大公約数になる。具体的には gcd(a, b) = p1^min(α1, β1) · p2^min(α2, β2) · … という形で計算できる。
この手法は、素因数分解が容易な場合に有効である。大きい数に対しては分解が難しくなりやすいため、実用上は次節の互除法のような手法がよく用いられる。
2.3 ユークリッドの互除法
2.3.1 互除法の手順
ユークリッドの互除法は、最大公約数が剰余に不変であるという性質を利用する。a ≥ b > 0とし、aをbで割ったときの余りをrとする（a = qb + r、0 ≤ r < b）。このときgcd(a, b)はgcd(b, r)に等しい。これをrが0になるまで繰り返す。
具体的には、(a, b)→(b, r1)→(r1, r2)→…と状態が更新され、最後に得られる非零の剰余が最大公約数である。
この流れは「割り算の連鎖」であり、素因数分解を必要としないため、多くの状況で効率がよい。
2.3.2 合計計算量と実用性
計算量の目安としては、互除法は入力の桁数に対して比較的速く収束することが知られている。各段階で数が小さくなり、剰余の連鎖が短い長さで終わりやすいため、実装に向く。
実務でも、整数演算としての「除算と剰余」だけで完結する点が利点である。さらに、同じ考え方は複数個の数にも拡張できる。例えばgcd(a, b, c)はgcd(gcd(a, b), c)として計算できる。
3 他の概念との関係
3.1 最小公倍数との関係
最大公約数と最小公倍数には基本的な関係がある。正の整数a, bについて a·b = gcd(a, b) · lcm(a, b) が成り立つ。ここでlcmは最小公倍数を表す。
この関係は、数の共通部分（最大公約数）と包含部分（最小公倍数）が、積の形で互いに補完し合うという見方を与える。素因数分解の観点でも、最大公約数は各素数に対する指数の最小、最小公倍数は指数の最大で表され、積が指数の和になることから整合する。
3.2 互いに素との関係
2つの整数が「互いに素」とは、最大公約数が1であることを意味する。つまりgcd(a, b) = 1ならaとbは互いに素である。
この性質は合同式や逆元の存在と結びつく。互いに素であることにより、ある種の数式操作が一意に戻せるようになるため、暗号理論や初等整数論の多くの場面で中心的な役割を担う。
さらに、互いに素かどうかは、最大公約数が1かどうかという比較的簡単な判定へ落とし込める点が実用上の利点である。
3.3 ベズーの等式とのつながり
ベズーの等式は、最大公約数が線形結合として表現できることを述べる。整数a, bの最大公約数をdとすると、ある整数x, yが存在して ax + by = d が成り立つ。
特に互いに素の場合（d = 1）には、ax + by = 1となる組x, yが存在する。これは「1を作れる」ことを意味し、合同式における逆元の構成へ直結する。互除法を拡張した計算により、x, y自体も求められることが多い。
4 応用
4.1 分数の約分
分数の約分は、分子と分母に共通する最大の因子を取り除く操作として理解できる。分数a/bに対して、d = gcd(a, b)とし、a' = a/d、b' = b/dと置くと、a'/b'は同じ値を表しつつ、分子と分母がこれ以上同じ正の整数で割れない形になる。
このとき、約分後の分子と分母は互いに素である。最大公約数はこの「これ以上約分できない状態」を作るための基準として機能する。
4.2 数の分解（共通部分の抽出）
最大公約数を用いると、複数の整数に共通する因子を体系的に抽出できる。例えばaとbをdで割った部分は、それぞれa/d、b/dであり、共通因子が取り除かれた残りが得られる。
この操作は、連結的な計算を簡潔にするだけでなく、整数の構造を見通し良くする。共通因子の有無や大きさが分かった時点で、以後の整理（比の簡約、比率の比較、式の共通因子の削除）が自然に進む。
4.3 合同式・合同の基礎での役割
合同式の理論では、ある整数で割った余りが等しいことを扱う。最大公約数は、その合同式がどのような解を持つか、あるいは逆元が存在するかを決める指標として現れる。
例えば、互いに素な関係があるとき、法（合同の基準となる数）に対して逆元が作れる。逆元があると方程式の形を両辺に「戻す」操作が可能になるため、線形合同式の解法が成立する。
4.4 実生活・アルゴリズムでの利用例
最大公約数は計算機上で頻出の基本演算である。例えば、周期の調整では複数の周期の同時一致を求める際に、最小公倍数が現れるが、そこでも最大公約数との関係が利用される。周波数やスケジュールの整合性、時間割の整列などの問題は、整数比として扱える範囲でこの枠組みによって整理できる。
また、整数の約分や比の簡約はデータの整形段階で繰り返されることがあり、最大公約数はその中心的な道具となる。さらに、互除法のような手法はライブラリに組み込まれていることが多く、実装容易性と堅牢性の両面から、広い応用領域で使われている。