最大公約数

Last-modified: 2021-10-20 (水) 23:51:29

最大公約数とは、少なくとも一つが0ではない複数の整数公約数のうち最大の数を指す。具体的にはユークリッドの互除法?により求めることができる。
英語では一般的にgreatest common divisorと言うが、しばしば「G.C.D.」や「G.C.M. (Greatest Common Measure)」「G.C.F. (Greatest Common Factor)」「H.C.F. (Highest Common Factor)」等の省略形で記述される。

最大公約数の求め方

共通に割れるだけ割っていく方法

最大公約数を求める最も簡易的な方法の1つは,共通な数で割れるだけ割っていく方法である。このとき、共通に割れる数の積が最大公約数になる。
(例)12と18の最大公約数を求める場合、それぞれ偶数で2で割り切れることが分かるので割ると6と9になる。さらに、それらは3で割り切れるので割ると2と3になり、1以外の約数は無くなる。ここで割り切れた2と3を掛けた数字6が最大公約数となる。手間がかかるが算数・中学数学の一部はこれで代用可能。

素因数分解を利用して共通な指数を探す方法

上記の通り、素因数分解を利用する方法。高校数学では通常この方法が用いられる。最大公約数を求めるには、共通な素因数に一番小さい指数をつける。
例えば、a=216, b=324の最大公約数を求めるには、最初にa, bを素因数分解して
a=2×2×2×3×3×3=2³×3³
b=2×2×3×3×3×3=2²×3⁴
素因数2について、2³と2²の
「公約数」は、1, 2, 2²、「最大公約数」は、2²
同様にして素因数3について、3³と3⁴の
「公約数」は、1, 3, 3², 3³、「最大公約数」は、3³

結果としてaと bの最大公約数は2²×3³=108

ユークリッドの互除法

詳細は「ユークリッドの互除法?」を参照。

多項式の最大公約数

多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、x³-x と x³+x²-x-1 の最大公約数は x²-1 である。
多項式の最大公約数は、定数倍を除いて一意に決まる。

関連項目

最大公約数と最小公倍数 - 高精度計算サイト - Keisan - CASIO
2つ以上の数の最大公約数 G.C.D.と最小公倍数 L.C.M.を求められる。

最大公約数を求める計算機 - Nap.st
最大5つの数に対して計算可能。負荷の都合上、入力値は最大5桁までの整数に限られる。

コメント欄

  • 小学校のころ学校では割れるだけわる方法で求めさせられて塾では素因数分解させられたぞ -- あさかはじゅん 2021-10-20 (水) 23:51:18

閲覧者数

今日?
昨日?
合計?

タグ

Tag: 数学