最大公約数とは – 最大公約元 | 0でない整域の元たちのgcdを考える

2023年4月3日

最大公約数とは " 最大公約元 “の定義から解説し、整域 R の 0 でない元たちの最大公約元をイデアルで考えます。

加法群 Z が一元生成の巡回群であることから、通常の整数についての gcd にも触れ、その後で一般的な整域についての最大公約元についての定理を証明します。

環における二項演算は、有限個について行うことも注意です。定理を証明するときに、有限個を除いて 0 という言い方を使います。

このブログ記事では、環 R は乗法単位元 1 をもつ可換な整域として議論をしています。

まずは、最大公約元に関連する用語や記号から説明します。

記事の後半では、素因数分解の証明を述べています。

最大公約数とは 最大公約元 :定義と記号

【定義１】

整域 R の元 a と b ≠ 0 に対して、ある r ∈ R が存在し、a = br となっているとき、a を b の倍元（b を a の約元）という。

a が b の倍元であるとき、b | a と表す。

通常の整数環 Z における割り切れるということの一般化です。

例えば、
4 | 8 だと、8 が 4 の倍元ということになります。

さらに、同伴という用語が使われることもあるので、定義を述べておきます。

単元という環論で使われる用語と合わせて押さえておくと良いかと思います。

【定義２】

整域 R の 0 でない元 x が、乗法についての逆元をもつとき、x を R の単元という。

そして、0 ではない a, b ∈ R について、

a | b かつ b | a であるとき、a と b は同伴であるという。

この同伴については、次の言い換えができます。

同伴という言葉が使われるかどうかは別として、この内容は環論を学習していると目にする機会があるかと思いますので、取り挙げておきます。

＜証明＞

a = bx を満たす単元 x ∈ R が存在したとします。

単元は 0 でないので、今、b | a

また、乗法逆元 x^-1 を両辺に乗じると、

ax^-1 = b です。

すなわち、a | b でもあるので、a と b は同伴となっています。

逆に、a と b が R において同伴だとします。

a | b かつ b | a なので、ある x, y ∈ R が存在して、b = ax, a = by

よって、a = ayx より、a(1 － yx) = 0

R が整域であり、b が 0 でないという前提なので、1 － yx = 0

つまり、xy = 1 なので、これは x の乗法逆元が y ということを示しています。

そのため、x は単元なので、

a = bx を満たす単元 x ∈ R が存在するということになります。【証明完了】

では、ここから最大公約元の定義です。

最大公約元の定義

【定義３】

R を整域とします。

{a_λ ∈ R | λ ∈ Λ} に対して、d ∈ R が、次の (1) と (2) をともに満たすとき、d を {a_λ} の最大公約元 (gcd) という。

(1) 各 λ ∈ Λ に対して、d | a_λ

(2) r ∈ R が各 λ ∈ Λ に対して、
r | a_λ であるならば、r | d

乗法単位元 1 をもつ可換な整域 R という設定なので、通常の整数と違って大小関係は考えていますが、約元を利用して最大公約元を定義しています。

通常の整数のときの最大公約数の一般化で、しかも添数集合が無限集合のときも考慮した定義になっています。

無限個の元たちの最大公約元の定義を述べましたが、準備運動の感覚で、整数についての有限個の最大公約元についての命題を証明します。
※ ほとんどアーベル群の練習ですが。

その後で、最大公約元が存在すれば、単元倍を除いて一意的であることを示します。

最大公約元 :有限個の整数で練習

【命題２】

整数 x1, … , xn の最大公約数を d とすると、
有る整数 z1, … , zn が存在し
z1x1+…+znxn = d と表すことができる。

ねじれ群より

※ この【命題２】の証明は、リンク先の記事で述べています。

整数環における乗法逆元をもつ元は 1 か －1 のみという特殊な内容ですが、可換環論の入門に良い内容かと思います。

同伴を意識するのが、最大公約元が存在すれば、単元倍を除いて一意的ということです。

命題として、これを証明します。

最大公約元と単元倍

【命題３】

R を整域とし、
{a_λ ∈ R | λ ∈ Λ} の最大公約元を d とする。

他に {a_λ} の最大公約元 d’ が存在したとすると、d’ は d の単元倍である。

最大公約数の定義 (2) より、
「r ∈ R が各 λ ∈ Λ に対して、r | a_λ 」であるならば、r が最大公約元の約元でした。

そのため、d | d’ かつ d’ | d

これは、d と d’ が同伴ということなので、同伴の書き換えである【命題１】より、
ある単元 x ∈ R が存在し、d’ = dx

よって、d の他に最大公約元 d’ が存在したとすると、d’ は d の単元倍ということが示せました。【証明完了】

ここから、たとえ添数集合が無限集合であったとしても、最大公約元を単項イデアルと結びつけて理解する定理を証明します。

最大公約数とは :イデアルを考える

【定理】

R を整域とする。

{a_λ ∈ R | λ ∈ Λ} によって生成される R のイデアルを M とする。

この M が単項イデアル (d) だとすると、
d は、{a_λ} の最大公約元である。

＜証明＞

{a_λ ∈ R | λ ∈ Λ} によって生成される R のイデアルを M とすると、
M = (d) の元 d は、

d = Σ_λ r_λa_λ … ★ という形です。

ただし、r_λ ∈ R たちは、有限個を除いて 0 という有限和です。

※ 無限級数とは違い、Λ が無限集合のときは有限和です。

よって、r ∈ R で、各 λ ∈ Λ について、
r | a_λ となるものが存在したとすると、r は★の右辺の約元となっているので、★の左辺である d の約元になっています。

つまり、この r について r | d となるので、生成元 d は最大公約数の定義の条件 (2) を満たしています。

さらに、各 λ ∈ Λ について、
a_λ ∈ M = (d) なので、一元生成イデアルの定義から、
ある h ∈ R が存在して、a_λ = dh

つまり、d | a_λ

これで、d は最大公約元の定義の条件 (1) も満たしたので、d は、{a_λ} の最大公約元です。【証明完了】

{a_λ ∈ R | λ ∈ Λ} によって生成される R のイデアルを M は、有限和の形で表されているということが効きました。

部分集合で生成されるイデアルについては、有限和ということが他の内容でも使われるときがあるので、この定理の証明で慣れておくと良いかと思います。

イデアルの積という記事で、有限和についての内容を扱っています。

ここまでの環論に関連して、整数環についての素因数分解の証明を述べておきます。

最大公約元からの整数論

【素数の定義】
2 以上の自然数で、正の約数が 1 と、その数自身の 2 個しかないものを素数という。

【合成数の定義】
2 以上の自然数で、1 と、その数以外の正の約数をもつものを合成数という。
※ 2 以上の自然数で、素数でないものが合成数ということです。

合成数の定義が、難しそうですが、具体例で見てみます。

6 は、2 以上の自然数です。 6 の正の約数として、2 と 3 が考えられます。1 と 6 以外に正の約数が存在しているので、6 は素数ではありません。

そのため、2 以上の自然数である 6 は合成数ということになります。

議論を始めるときの定義のままだと、合成数というものが、分かりづらいですが、素因数分解の証明が完成すると、もっと合成数が分かりやすくなります。

まず、合成数についての命題を証明します。この命題には、大学の数学で学習する内容が根本に使われます。

それは、自然数全体の任意の空ではない部分集合には、必ず最小値（最小元）が存在するということです。これは、自然数全体が整列集合となっているということです。

※ 超限帰納法というブログ記事で、自然数全体が整列集合であることを証明しています。クリックすると、リンク先の記事に移動します。

それでは、この自然数全体がもつ性質を使って、次の命題を証明します。
自然数全体を N, 整数全体を Z と表すことにします。

合成数は素数を約数にもつ

【命題】

a を合成数とする。
このとき、a は必ず素数を正の約数としてもつ。

＜証明＞

{x ∈ N | x は合成数だが素数を約数にもたない} という自然数全体 N の部分集合を S と置きます。

この S が空集合であるということを示せば、どの合成数も必ず素数を約数としてもつということになります。そのため、S が空集合ではないと仮定して、矛盾を導きます。

S が空集合でないとすると、S は自然数全体 N の部分集合なので、S には最小値が存在することになります。その最小値を u と置きます。

u ∈ S なので、u は合成数です。

よって、1 < c < u である自然数 c で、u の約数となっているものが存在します。

u を c で割ったときの商を k とすると、
u = ck …★

u と c が自然数なので、k も自然数となっています。

そして、1 < c < u より、1 < k < u

ここで、c は素数か、素数でない（合成数）かのいずれかです。

もし、c が素数だとすると、
1 < k < u なので、素数 c が u の正の約数ということになります。

これは u が素数を約数にもつ合成数ということです。しかし、u は S の元なので、素数を約数としてもたないことに反します。

よって、c は素数ではないということになります。

1 < c だったので、c は合成数です。

ここで、c は素数を約数にもつか、素数を約数にもたないかのいずれかになります。

c が素数を約数にもたないとすると、c は合成数なので、c ∈ S です。

すると、c < u だったので、u が S の最小値だということに反してしまいます。そのため、c は素数を約数にもつことになります。

これより、ある素数 p が存在して、
c = pt (t は自然数) と表すことができます。

これを★に代入すると、
u = (pt)k = p(tk)

これは、素数 p が u の約数であることを示しています。

ところが、u は S の元なので、素数を約数にもちません。そのため、矛盾となります。

以上より、背理法から、S は空集合ということになります。

すなわち、どんな合成数も、素数を必ず約数にもつということが示せました。【証明完了】

この命題によって、合成数というものが、はっきりとしました。

合成数は、2 以上の自然数で、素数を約数にもつものです。

※ 合成数の約数となっている素数のことを、その合成数の素因数といいます。

2 以上の自然数 n について、n が素数か、n が素数ではない合成数かという二択です。

合成数のときには、約数として素数をもつということです。

では、ここまでの内容を踏まえて、素因数分解の証明を行います。

素因数分解の注意点ですが、素数 p 自身は、何もせずとも素因数分解が既に完了しているもの（素数ばかりの積の形）と考えます。

素因数分解の証明

【定理１】

n を 2 以上の自然数とすると、n は素数ばかりの積の形で表すことができる。

＜証明＞

定理が偽だと仮定します。

すると、2 以上の自然数で、素数ばかりの積の形で表すことができない自然数が存在することになります。

S を 2 以上の自然数で、素数ばかりの積の形で表すことができないもの全体だとします。

今、S が空集合ではないということなので、S には最小元が存在します。

x ∈ S を S の最小元とします。

素数は、素数ばかりの積の形に既になっていると考えることになっています。そのため、x は素数ではありません。

すると、x は 2 以上の自然数で素数ではないことから、合成数ということになります。

x は合成数なので、【命題】から、x は素数を約数としてもちます。その x の約数となっている素数を p と置きます。

x を p で割った商を y とすると、
x = py (2 ≦ y < x)

素数 p は 2 以上の自然数なので、y は x よりも小さい自然数です。

そのため、y が素数ばかりの積の形で表せないとすると、2 ≦ y なので、y ∈ S となります。

これは、y < x なので、x が S の最小元であったことに反します。

よって、y は素数ばかりの積の形で表せるということになります。

p₂, … , p_k を y を表す素数たちだとすると、
y = p₂×…×p_k です。

x = py だったので、
x = p×p₂×…×p_k となります。

これは、x が素数ばかりの積で表すことができないということに矛盾しています。

以上より、背理法から、【定理１】の反例が存在しないということが示せたので、定理が示されました。【証明完了】

これで、2 以上の自然数は、必ず素数ばかりの積の形となっていることが示せました。

後は、その素数ばかりの積の表し方が、素因数の順番を適切に並び替えると同じものになっているということを示すことが残っています。

このことを示すために、素数についての重要な性質を証明する必要があります。ここで、除法の定理を使います。

【除法の定理】

x を自然数とし、y を整数とする。

このとき、ある整数 q と r が存在して、
y = xq + r (0 ≦ r < x) と表すことができる。

しかも、この表し方は、ただ一通りである。

ユークリッド整域より

余りが割る数よりも小さくなることを利用して、結論を導きます。

素数の性質

【補題】

p を素数とし、a, b を自然数とする。

このとき、p が ab の約数であるならば、「p は a の約数」または「p は b の約数」である。

＜証明＞

p が a の約数だとすると、補題の結論が示せたことになるので、p が a の約数ではない場合について議論を進めます。

{k ∈ N | p は ak の約数} という集合を S と置きます。

p, b ∈ S なので、S は空集合ではない N の部分集合です。そのため、S には最小元 e が存在します。

今、p が a の約数ではないので、e は 2 以上の自然数です。（e = 1 とすると、p が ae = a の約数となってしまうためです。）

t ∈ S を任意に取ると、e と t について、除法の原理から、ある整数 q と r が存在して、
t = eq + r (0 ≦ r < e)

両辺に a を掛けると、at = (ae)q + ar

t, e ∈ S なので、p は at と ae の約数です。
そのため、p は ar の約数になります。

1 ≦ r < e だとすると、 r ∈ S となり、e が S の最小元であることに反してしまいます。そのため、r は 0 でなければなりません。

r = 0 より、
at = (ae)q = a(eq)

無辺を左辺に移項すると、
a(t－eq) = 0 です。

自然数 a ≠ 0 であり、
整数環は整域なので、
t－eq = 0 です。

つまり、t = eq で、e は t の約数となっています。

このため、t として p と b を考えると、e は p と b の約数となっています。

2 ≦ e だったので、e が素数 p の約数であることから、e = p

e は b の約数なので、素数 p が b の約数ということが示せました。【証明完了】

この補題から、素数 p が自然数 a と b の積 ab の約数であれば、p は a または b の約数ということになります。

この補題を使って、素因数分解の素数の積としての表し方が、「素因数の積の順序を除けば、ただ一通りであること」を示します。

積の順序を除けば一通り

【定理２】

n を 2 以上の自然数とする。また、n は素数ばかりの積の形で表したとき、
p₁×…p_k と q₁×…×q_l だったとする。ただし、p_i や q_j は n の素因数。

このとき、k と l は等しく、p₁, … , p_k を並び替えると、q₁, … , q_l となる。

＜証明＞

この定理を成立しない反例が存在したとします。そのような 2 以上の自然数の中で、最小のものを m と置きます。

この m が
p₁×…×p_k と q₁×…×q_l と素因数の積に分解されているとします。

すると、p₁ は n の素因数なので、
q₁×(q₂×…×q_l) の約数となります。

【補題】より、p₁ は、
「q₁ の約数 または q₂×…×q_l の約数」となります。

p₁ が q₁ の約数である場合は、q₁ が素数であることから、p₁ = q₁ となっています。

n を p₁ で割ったときの商は、
p₂×…×p_k = q₂×…×q_l

p₂×…p_k < m なので、m が最小の反例であったことから、p₂×…p_k について定理が成立しています。

そのため、p₂, … , p_k を並び替えると、q₂, … , q_l となり、k と l は等しく、p₁, … , p_k を並び替えると、q₁, … , q_l となります。

これは、m が反例であったことに矛盾します。

よって、p₁ は、q₂×…×q_l の約数ということになります。

【補題】より、p₁ は、q₂, … , q_l のどれかの約数 ということになります。

p₁ が q_i の約数だとすると、
m ÷ p₁ は割り切れるので、
p₂×…×p_k = m ÷ p₁ = m ÷ q_i

m ÷ q_i は、
q₁×…×q_i-1×q_i+1×…×q_l です。

m ÷ q_i < m より、m が最小の反例であったことから、m ÷ q_i について定理の結論が成立します。

そのため、k と l は等しく、p₂, … , p_k を並び替えると、q₁, … , q_i-1, q_i+1 , … , q_l となります。

つまり、p₁, … , p_k を並び替えると、
q₁, … , q_l です。【証明完了】

これで、素因数分解と、その一意性も証明できました。

一意であることの証明は、大学数学のさまざまな内容で出てくるので、証明に慣れておくと良いかと思います。

それでは、これで今回のブログ記事を終了します。

読んで頂き、ありがとうございました。