| のぼりんさんの説明は正しいのですが、もし単さんイデアル論をご存知ならこの問題の質問を されないのではないでしょうか?
イデアルI = (a[1],a[2],・・・・・・,a[n])とおくと、整数bがb ∈ Iならば、 b = x[1]*a[1]+x[2]*a[2]+・・・・・・+x[n]*a[n]となる整数x[1],x[2],・・・・・・,x[n]が存在します。 上記はイデアルの定義のようなものですから、単さんに勉強して頂くこととして、
GCM(a[1],a[2],・・・・・・,a[n]) = dとするとき、「d ∈ I」が示せないということではないでしょうか? # イデアル論的には、上記は(a[1],a[2],・・・・・・,a[n]) = (d)であることと同値です。
以下、上記の証明です。
Iに属する最小の正の整数をgとします。 # このようなgの存在は公理(ペアノの公理)で、数学的帰納法の正当性(?)と同値です。
b ∈ Iとなる整数bをgで割った余りを考えます。 b = q*g+r, 0 ≦ r < gです。r = b-q*g ∈ Iとなりますから、もしr > 0ならgの最小性に矛盾します。 # bもgもIに属すので、整数u,vに対して、ub+vgという形の数はIに属します。
よってr = 0で、Iに属す整数はgで割り切れることが分かります。 またgの全ての倍数はIに属しますので、Iはgの倍数全体と一致し、I = (g)であることが分かります。
題意よりdは正の整数です。 kを1 ≦ k ≦ nである整数とするとa[k] ∈ Iですので、a[k]はgの倍数です。 # 0*a[1]+0*a[2]+・・・+1*a[k]+・・・+0*a[n] ∈ Iです。 よって、gはa[1],a[2],・・・・・・,a[n]の公約数となります。 dはa[1],a[2],・・・・・・,a[n]の最大公約数ですから、g ≦ dとなります。
a[1],a[2],・・・・・・,a[n]はdの倍数ですから、a[k] = A[k]*dとおくと、 x[1]*a[1]+x[2]*a[2]+・・・・・・+x[n]*a[n] = (x[1]*A[1]+x[2]*A[2]+・・・・・・+x[n]*A[n])*d ∈ Iです。 すなわちIに属す整数はdの倍数でもあります。 よってgもdの倍数なので、g ≧ dです。
g ≦ dかつg ≧ dであるの必要があるので、g = dすなわちI = (d)となります。
以下、のぼりんさんの説明通りです。
|