GCD

最大公約数（GCD）は、2 つ以上の整数を割り切る最大の正の整数であり、ユークリッドの互除法で効率的に計算できる。

目的

整数の最大共通因数を求める。約分や整数論で使用される。

メカニズム

ユークリッドの互除法：gcd(a,b) = gcd(b, a mod b) を b=0 まで繰り返す。拡張ユークリッドの互除法は ax+by=gcd(a,b) を満たすベズー係数 x,y も求め、モジュラ逆数に用いられる。lcm(a,b) = |a×b|/gcd(a,b)。

ユースケース

分数の約分（reduce）
モジュラ逆数の計算
RSA 鍵の検証
有理数（レシオナル）の演算

例

入力
```
gcd(48, 18)
```
Output
```
6
```
48=6×8, 18=6×3

よくあるエラー

gcd with 0 left unhandled: gcd(a,0)=|a|, gcd(0,0)=0

関連用語

最小公倍数（LCM）は、2 つ以上の整数の公倍数である最小の正整数である。GCD を介して計算される。

Modular Arithmetic

合同算術（モジュラ演算）は整数演算の剰余を取り、結果を[0, n)の範囲に保つ。数論と暗号理論の基礎である。

素数とは、1と自分自身でのみ割り切れる1より大きい自然数である。数論の構成要素であり、すべての整数は素数の積として一意に分解される。

関連ツール

高精度計算ツール

High-precision arithmetic calculator. No floating-point errors。無料、プライベート、100%クライアントサイド。

References