この記事は英語版の
対応するページ を翻訳することにより充実させることができます。(2024年6月)翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
英語版記事を
日本語へ機械翻訳したバージョン (Google翻訳)。
万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針
G-3 に基づき、削除される可能性があります。
信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
履歴継承 を行うため、
要約欄 に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、
Wikipedia:翻訳のガイドライン#要約欄への記入 を参照ください。
翻訳後、((
翻訳告知 |en|Greatest common divisor|…))を
ノート に追加することもできます。
Wikipedia:翻訳のガイドライン に、より詳細な翻訳の手順・指針についての説明があります。
自然数 の整除 関係を図示した無限グラフ(ハッセ図 )の一部。たとえば8と12の最大公約数は4であり、4と6の最大公約数は2である。最大公約数 (さいだいこうやくすう、英 : greatest common divisor [ 注釈 1] )とは、すべての公約数 を約数 にもつ公約数である。特に正の整数 では、最大公約数は通常の大小関係についての最大の公約数と一致し、その存在性はユークリッドの互除法 により保証される。
以下では、自然数 は
0
{\displaystyle 0}
を含むとし、
a
{\displaystyle a}
が
b
{\displaystyle b}
を割り切る こと(つまり
b
=
c
a
{\displaystyle b=ca}
となる自然数
c
{\displaystyle c}
が存在すること)を
a
∣
b
{\displaystyle a\mid b}
と表す。
写像
gcd
:
N
n
→
N
;
(
a
1
,
…
,
a
n
)
↦
d
{\displaystyle \gcd \colon \mathbb {N} ^{n}\to \mathbb {N} ;(a_{1},\dots ,a_{n})\mapsto d}
を
すべての
1
≦
i
≦
n
{\displaystyle 1\leqq i\leqq n}
に対して
d
∣
a
i
{\displaystyle d\mid a_{i))
であり、
すべての自然数
b
{\displaystyle b}
に対し、すべての
1
≦
i
≦
n
{\displaystyle 1\leqq i\leqq n}
に対して
b
∣
a
i
{\displaystyle b\mid a_{i))
ならば
b
∣
d
{\displaystyle b\mid d}
となる ように定める[ 1] [ 2] [ 3] [ 4] 。
d
{\displaystyle d}
を
a
1
,
…
,
a
n
{\displaystyle a_{1},\dots ,a_{n))
の最大公約数といい、
gcd
(
a
1
,
…
,
a
n
)
{\displaystyle \gcd(a_{1},\dots ,a_{n})}
や
(
a
1
,
…
,
a
n
)
{\displaystyle (a_{1},\dots ,a_{n})}
と表す。
gcd
(
a
1
,
…
,
a
n
)
=
1
{\displaystyle \gcd(a_{1},\dots ,a_{n})=1}
が成り立つことを
a
1
,
…
,
a
n
{\displaystyle a_{1},\dots ,a_{n))
が互いに素 であると言う。
この定義から容易に次のことがわかる。
gcd
(
a
,
b
)
=
gcd
(
b
,
a
)
{\displaystyle \gcd(a,b)=\gcd(b,a)}
が成り立つ。
gcd
(
gcd
(
a
,
b
)
,
c
)
=
gcd
(
a
,
gcd
(
b
,
c
)
)
=
gcd
(
a
,
b
,
c
)
{\displaystyle \gcd(\gcd(a,b),c)=\gcd(a,\gcd(b,c))=\gcd(a,b,c)}
が成り立つ[ 2] 。
最大公約数は存在すれば一意である[ 5] 。
n
=
0
{\displaystyle n=0}
であれば(つまり空集合の)最大公約数は
0
{\displaystyle 0}
である[ 2] 。空積 が
1
=
{
∅
}
{\displaystyle 1=\{\varnothing \))
であることと空虚な真 に注意せよ。
n
=
1
{\displaystyle n=1}
であれば
gcd
(
a
1
)
=
a
1
{\displaystyle \gcd(a_{1})=a_{1))
である。
n
=
2
{\displaystyle n=2}
とし、
0
{\displaystyle 0}
と
0
{\displaystyle 0}
の最大公約数は
0
{\displaystyle 0}
である[ 1] [ 6] [ 7] 。ゆえに、一般には最大公約数は最大の公約数ではない[ 8] 。
n
=
2
{\displaystyle n=2}
とし、
0
{\displaystyle 0}
でない自然数
a
1
{\displaystyle a_{1))
と
0
{\displaystyle 0}
の最大公約数は
a
1
{\displaystyle a_{1))
である自然数が一つ以下の場合は自明なので普通は二つ以上の場合を考えることになるが、二番目の性質により二つの自然数の最大公約数を考えることに帰着する。この定義からアプリオリ[ 9] には任意の二つの自然数に最大公約数が存在するかわからないが、実際には単に存在するだけでなく具体的に計算するアルゴリズムがユークリッドの互除法 として知られており、この重要な応用がベズーの等式 である。
たとえば
333
{\displaystyle 333}
と
57
{\displaystyle 57}
の最大公約数をユークリッドの互除法により求めてみよう。
333
=
57
×
5
+
48
{\displaystyle 333=57\times 5+48}
なので
gcd
(
333
,
57
)
=
gcd
(
57
,
48
)
{\displaystyle \gcd(333,57)=\gcd(57,48)}
である。
57
=
48
×
1
+
9
{\displaystyle 57=48\times 1+9}
なので
gcd
(
57
,
48
)
=
gcd
(
48
,
9
)
{\displaystyle \gcd(57,48)=\gcd(48,9)}
である。
48
=
9
×
5
+
3
{\displaystyle 48=9\times 5+3}
なので
gcd
(
48
,
9
)
=
gcd
(
9
,
3
)
{\displaystyle \gcd(48,9)=\gcd(9,3)}
である。
9
=
3
×
3
+
0
{\displaystyle 9=3\times 3+0}
なので
gcd
(
9
,
3
)
=
gcd
(
3
,
0
)
=
3
{\displaystyle \gcd(9,3)=\gcd(3,0)=3}
であり、最大公約数が
3
{\displaystyle 3}
であることがわかった。
このように最大公約数の定義や計算に素数 や素因数分解 などのような高級な概念は全く必要ない [ 10] のだが、算術の基本定理 が成り立つことを利用して最大公約数を明示的に表すこともできる。つまり、すべての素数から成る集合を
P
r
i
m
e
s
{\displaystyle {\mathfrak {Primes))}
として、
a
1
,
…
,
a
n
{\displaystyle a_{1},\dots ,a_{n))
を
a
i
=
∏
p
∈
P
r
i
m
e
s
p
e
p
(
i
)
{\displaystyle a_{i}=\prod _{p\in {\mathfrak {Primes))}p^{e_{p}(i)))
と素因数分解すれば、次が成り立つ[ 11] 。
gcd
(
a
1
,
…
,
a
n
)
=
∏
p
∈
P
r
i
m
e
s
p
min
{
e
p
(
1
)
,
…
,
e
p
(
n
)
}
{\displaystyle \gcd(a_{1},\dots ,a_{n})=\prod _{p\in {\mathfrak {Primes))}p^{\min\{e_{p}(1),\ldots ,e_{p}(n)\))}
たとえば
333
=
3
2
×
37
{\displaystyle 333=3^{2}\times 37}
や
57
=
3
×
19
{\displaystyle 57=3\times 19}
と素因数分解できるので、たしかに
gcd
(
333
,
57
)
=
3
{\displaystyle \gcd(333,57)=3}
となりユークリッドの互除法を用いて得られた値と一致する。
他にも次のような性質が知られている。
gcd
(
a
,
b
)
lcm
(
a
,
b
)
=
a
b
{\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=ab}
(ただし
lcm
{\displaystyle \operatorname {lcm} }
は最小公倍数 )が成り立つ[ 注釈 2] 。この関係によって最小公倍数を計算するのが一般的である。
gcd
(
a
,
lcm
(
b
,
c
)
)
=
lcm
(
gcd
(
a
,
b
)
,
gcd
(
a
,
c
)
)
{\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))}
や
lcm
(
a
,
gcd
(
b
,
c
)
)
=
gcd
(
lcm
(
a
,
b
)
,
lcm
(
a
,
c
)
)
{\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))}
のような分配則 が成り立つ。
gcd
(
a
,
b
)
=
∑
k
∣
a
,
b
φ
(
k
)
{\displaystyle \gcd(a,b)=\sum _{k\mid a,b}\varphi (k)}
(ただし
φ
(
k
)
{\displaystyle \varphi (k)}
はオイラーのトーシェント関数 )が成り立つ。
gcd
(
a
,
b
)
=
a
f
(
b
/
a
)
{\displaystyle \gcd(a,b)=af(b/a)}
(ただし
f
{\displaystyle f}
はトマエ関数 )が成り立つ。
正の奇数
a
{\displaystyle a}
と自然数
b
{\displaystyle b}
に対して
gcd
(
a
,
b
)
=
log
2
∏
k
=
0
a
−
1
(
1
+
e
−
2
π
i
k
b
/
a
)
{\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2\pi ikb/a})}
が成り立つ[ 12] 。
gcd
(
a
,
b
)
=
∑
k
=
1
a
e
2
π
i
k
b
/
a
∑
d
∣
a
c
d
(
k
)
d
{\displaystyle \gcd(a,b)=\sum _{k=1}^{a}e^{2\pi ikb/a}\sum _{d\mid a}{\frac {c_{d}(k)}{d))}
(ただし
c
d
(
k
)
{\displaystyle c_{d}(k)}
はラマヌジャン和(英語版 ) )が成り立つ[ 13] 。
gcd
(
n
a
−
1
,
n
b
−
1
)
=
n
gcd
(
a
,
b
)
−
1
{\displaystyle \gcd(n^{a}-1,n^{b}-1)=n^{\gcd(a,b)}-1}
が成り立つ[ 14] 。
∑
k
=
1
n
gcd
(
k
,
n
)
=
n
∏
p
∣
n
(
1
+
v
p
(
n
)
(
1
−
p
−
1
)
)
{\displaystyle \sum _{k=1}^{n}\gcd(k,n)=n\prod _{p\mid n}(1+v_{p}(n)(1-p^{-1}))}
(ただし
v
p
(
n
)
{\displaystyle v_{p}(n)}
は
n
{\displaystyle n}
の
p
{\displaystyle p}
進付値 )が成り立つ。特に重要な事実として、組
(
N
,
∣
)
{\displaystyle (\mathbb {N} ,\mid )}
は半順序集合 であるのでハッセ図を書くことができ、さらに
lcm
{\displaystyle \operatorname {lcm} }
と
gcd
{\displaystyle \gcd }
をそれぞれ結びと交わり とすれば完備分配束 を成し[ 1] 、
1
{\displaystyle 1}
が最小元、
0
{\displaystyle 0}
が最大元になる。したがって圏論 的には
lcm
{\displaystyle \operatorname {lcm} }
と
gcd
{\displaystyle \gcd }
はそれぞれ余積 と積 に対応する。
初等的な議論では自然数に限定したが、環 論的な文脈では上の定義を一般の環(ここでは単位的可換環とする)に置き換えることになる[ 15] 。よくある定義では条件2の
b
∣
d
{\displaystyle b\mid d}
が
b
≦
d
{\displaystyle b\leqq d}
となっている[ 注釈 3] ので、通常の大小関係が一般には定義できない環には拡張できないことに注意せよ。一般の環では最大公約数が存在するとは限らない 。たとえば
Z
[
x
2
,
x
3
]
{\displaystyle \mathbb {Z} [x^{2},x^{3}]}
の元
x
5
,
x
6
{\displaystyle x^{5},x^{6))
の最大公約数は存在せず[ 16] 、
Z
[
−
5
]
{\displaystyle \mathbb {Z} [{\sqrt {-5))]}
の元
6
,
2
(
1
+
−
5
)
{\displaystyle 6,2(1+{\sqrt {-5)))}
の最大公約数は存在しない。さらに、存在しても一意であるとは限らない 。たとえば有理整数環
Z
{\displaystyle \mathbb {Z} }
では
4
{\displaystyle 4}
と
6
{\displaystyle 6}
の最大公約数は
±
2
{\displaystyle \pm 2}
であり、多項式環
R
[
X
]
{\displaystyle \mathbb {R} [X]}
では
x
3
−
x
{\displaystyle x^{3}-x}
と
x
3
+
x
2
−
x
−
1
{\displaystyle x^{3}+x^{2}-x-1}
の最大公約数は
c
(
x
2
−
1
)
{\displaystyle c(x^{2}-1)}
(
c
∈
R
∖
{
0
}
{\displaystyle c\in \mathbb {R} \setminus \{0\))
) である。しかし考えている環が整域 であれば、最大公約数は存在すれば単元倍を除いて一意 なのでそれぞれ単に
2
{\displaystyle 2}
や
x
2
−
1
{\displaystyle x^{2}-1}
と書いてよい。
このように一般の整域でも最大公約数は存在するとは限らないが、すべての二つの元について最大公約数が存在するような整域をGCD整域 と言い、特に一意分解整域 であればGCD整域である。さらに単項イデアル整域 であれば元
a
1
,
…
,
a
n
{\displaystyle a_{1},\dots ,a_{n))
に対して
(
a
1
,
…
,
a
n
)
=
(
gcd
(
a
1
,
…
,
a
n
)
)
=
(
a
1
)
+
⋯
+
(
a
n
)
{\displaystyle (a_{1},\dots ,a_{n})=(\gcd(a_{1},\dots ,a_{n}))=(a_{1})+\cdots +(a_{n})}
が成り立ち、より強く多項式環やガウス整数環 のようなユークリッド整域 であればユークリッドの互除法を用いて最大公約数を求めることができる[ 1] 。この観点では自然数
a
,
b
{\displaystyle a,b}
の最大公約数が有理整数環
Z
{\displaystyle \mathbb {Z} }
のイデアル
(
a
)
+
(
b
)
{\displaystyle (a)+(b)}
すなわち
(
a
,
b
)
{\displaystyle (a,b)}
の正の生成元であるので、初等的には
gcd
(
a
,
b
)
{\displaystyle \gcd(a,b)}
を
(
a
,
b
)
{\displaystyle (a,b)}
と書くことが正当化されていると解釈できる。特に、空集合 の生成するイデアルが零イデアル であることから、空集合の最大公約数はやはり
0
{\displaystyle 0}
である。
^ 文献によっては highest common factor, greatest common factor, greatest common measure などを用いることもある。
^ この性質は引数が二つ以下の場合でしか一般に成り立たない。たとえば2と6と15であれば、左辺は30で右辺は180となり等号は成り立たない。この事態は素因数分解による表式を考えることにより理解される。
^ たとえば高木貞治(1971)『初等整数論講義』や日本数学会(2012)『岩波数学辞典 第4版』はこの流儀を採用している。