最大公約数・最小公倍数計算機

2つの正の整数から最大公約数と最小公倍数を求め、ユークリッドの互除法の手順も確認できます。

計算方法

式

\text{GCD}(a,b) = \text{GCD}(b,\; a \bmod b)

\text{LCM}(a,b) = \frac{a \times b}{\text{GCD}(a,b)}

変数、記号、単位

$a$: 1つ目の正の整数
$b$: 2つ目の正の整数

計算方法の説明

まずユークリッドの互除法で最大公約数を求めます。余りを使って割り算を繰り返し、余りが 0 になったところで終了します。その後、積と GCD・LCM の恒等式から LCM を求めます。

ユークリッドの漸化式に従い、 $(a,b)$ を $(b,\; a \bmod b)$ に置き換え、 $b = 0$ になるまで繰り返します。残った $a$ が GCD です。LCM は $a \times b = \text{GCD}(a,b) \times \text{LCM}(a,b)$ から求めます。

よくある質問

最大公約数とは何ですか？

最大公約数は、2つの整数をどちらも余りなく割り切る最大の正の整数です。GCD とも呼ばれます。

最小公倍数とは何ですか？

最小公倍数は、2つの整数のどちらの倍数にもなる最小の正の整数です。LCM とも呼ばれます。

ユークリッドの互除法はどう使いますか？

大きい数を小さい数で割った余りを次の計算に使い、余りが 0 になるまで繰り返します。最後の 0 でない余りが最大公約数です。

GCD と LCM の関係は？

正の整数 a と b では、a x b = GCD(a,b) x LCM(a,b) が成り立ちます。

互いに素とは？

2つの数の最大公約数が 1 のとき、1 以外の共通因数を持たないため、互いに素といいます。

最大公約数・最小公倍数計算機

計算方法

よくある質問

関連する計算機

すべての計算機

計算を始めますか？