- ベストアンサー
整数論基礎：最大公約数の証明
- 整数a,bの最大公約数dについて、d=ra+sbの形で表現できることの証明について質問があります。
- この証明では、イデアルIを使ってd=ra+sbの形を示します。
- 具体的なステップごとに説明がありますが、最後の(5)が理解できません。
- みんなの回答 （8）
- 専門家の回答
質問者が選んだベストアンサー
流れは、A No.5 に書いといたんだがなあ… 結論である「ディオファントスの定理」を使わずに、 (2) の根拠を示せばいいんですよ。 Z の (0) 以外で任意のイデアル I について、 I の任意の元 x をとると、x∈I かつ -x∈I であり、 x>0 または -x>0 でもあります。 すなわち、I は少なくともひとつ正の元を持ちます。 I の正の元のうち最小のものを a と置きましょう。 再び I の任意の元 x をとると、a での除算 x=aq+r, q は整数, r は 0≦r＜a の整数 が成り立ちます。 r=x-aq∈I であることから、r>0 と仮定すると r が I の正で最小の元であることに矛盾します。 よって、r=0。 I の任意の元は a の倍数であり、 Z が単項イデアル整域であることが示せました。 こうして、「ディオファントスの定理」を経由せずに Z が単項イデアル整域であることが示せましたから、 ここから (2) での c の存在が言えて、 循環論法なく、質問文中の証明が完成します。 そこから逆に、Z がユークリッド整域であることを 示すこともできるでしょう。何だか、遠回りな気も しますが。 御手許の教科書にも、何らかの方法で、 Z が単項イデアル整域であることが証明してあった ハズです。ちゃんと読みましたか？
その他の回答 (7)
- kabaokaba
- ベストアンサー率51% (724/1416)
No.4です どーでもいいんだけど・・ ディオファンティウスって・・・普通の日本語の本だったら ディオファントスって書いてない？ 英語だったら Diophantus...ディオファントゥスか。。。 原語のギリシア語のスペルはΔιόφαντοςだからディオファントスなんだよねー ベズーにしても，代数曲線の交点数のベズーの定理を思い出す人の方が多いと思うなー 何を言いたいのかというと，名前つきで書くなら誤解のないようにということ 閑話休題 >わざわざイデアルを利用してディオファンティウスの定理の証明をしようとしているのは、 >ユークリッド互助法と、それに絡む、a,b,が互いに素である時、 >sa+rb=1となることの必要十分性を証明しようとして、四苦八苦しているというのが原点にあります。 >ユークリッド互助法は実際にやってみるのは簡単なのですが、 >証明などに使おうとするとうまく言語化できないんですよね… ということは「分かってない」んです 話を整理しないとダメです． すでにalice_44さんのご指摘がありますが I=(a)+(b)と定めようがこれは精密化には寄与大ですが，本質ではありません 本質は 「I=(c)となるようなcが存在する」（(2)のこと） です． これの根拠はなんですか？ そもそも，あなたは何を根拠にして何を証明しようとしてるのか？です． イデアルを使って証明するために，I=(c)とかけることを使うのであれば I=(c)できることの根拠は「Zが単項イデアル整域」ということでしょう． しかし，あなたは（教科書にあるであろう）定義を知らないという． I=(c)の根拠として・・・ >aとbの2数を生成元としているのですから、おのずと「aの倍数」と「bの倍数」の加算によって、 >Iは生成されているはずです。ですから、Iはaとbの公約数を、同時にその元として持つはずです。 としていますが，これは違います． 「同時に」というのも意味不明だけど aとbの公約数の方が「小さい」のだから公約数がIに入るとはこれからはいえない 例えば，(10)は10の倍数，(2)は2の倍数 12は(2)の元だけど(10)の元ではない． aとbの公約数をgとおくとI=(a)+(b)⊂(g)というのが引用部分の帰結であって話が逆です． 適当な公約数gでI=(a)+(b)⊃(g)となるものはあるというのはどうやって示しますか？ ここが本質． ============== a<bとしましょう．割り算して b=qa+r (0<=r<a) aとbの最大公約数をd，aとrの最大公約数をd'としましょう 明らかに，d'はbの約数で，d'はaの約数だから，d'はaとbの公約数となり d'<=d r=b-qaだから，明らかにdはrの約数だから，dはaの約数でもあるからdはaとrの公約数． したがって，d<=d'です． よって，d=d' a,bの最大公約数を(a,b)と書きましょう ユークリッドの互除法は b=q1a+r1 a=q2r1+r2 r1=q3r2+r3 と割り算していくと r1>r2>・・・・>rn>・・・>=0 (a,b)=(a,r1)=(r1,r2)=・・・・=(rn-1,rn) となる列r1,r2,...rn,... が得られるが，0で打ち止めになるので，いつかは必ず0になるのです． つまり b=q1a+r1 a=q2r1+r2 r1=q3r2+r3 ... rn-2=qn rn-1 + rn rn-1=qn+1 rn + rn+1 rn=qn+2 rn+1 となるのです．rnとrn+1の最大公約数(rn,rn+1)はrn+1なのはOKですね． となると (a,b)=rn+1です． ここで，この割り算の列を逆に追いかけていけばいいのです 簡単のためr3から r3 = r1 -q3 r2 = r1 -q3 (a-q2r1) = r1(1+q3q2) -q3 a = (b-q1a)(1+q3q2) -q3 a = (1+q3q2) b - (q1(1+q3q2)+q3) a 式で書くと汚いけど，適宜置き換えればもっとすっきりするでしょう r3=sa+tbの形になるけど 同様にr4，r5とどんどん直せるでしょう？ これで終わり． (a,b)=sa+tbと表せる I=(a)+(b)とすると，d=(a,b)とおけば dはIの元になるので (d)⊂I 一方，I⊂(d)なのは明らかなのでI=(d) こういうわけです．
- alice_44
- ベストアンサー率44% (2109/4759)
←A No.5 補足 (1)の文面は、「元 (a) 、元 (b) による」を 「元 a、元 b による」または「イデアル (a)、 イデアル (b) による」に修正するべきであり、 補足によって、記述の細部が正確になったことは よいことだと思います。 しかし、その自明な書き間違いの訂正では、 (1)の意味も、証明の欠陥も、全く変わりません。 (2)の根拠は、どうなりましたか？
補足
該当の証明部分(今回の(1)～(5))は、教科書の記述をそのまま引いたものですが、教科書によると、(2)の根拠は結合法則による、とのことです。 この記述は私自身理解できておらず、よって、次の解釈をしていました。 ・(a)+(b)=(c)が成立する条件について考察する。 イデアルIの元が(a)+(b)であるならば、その元は任意の整数r,sによってra+saとおくことができる。 (∵イデアルの定義より。例として、(2)を元として持つイデアルJは、0に任意の回数、2を加算または減算した数の集合である。) そうした数の集合をKとおく時、その集合は、aとbの共通因数(=公約数)を元とするイデアルとなる(∵イデアルの定義より。) これより、(2)が言える。 しかし、これはご指摘の通り、証明しようとするベズーの等式が利用されているようです。 仰るとおり、証明としての順序が異なるように思われます。 教科書の執筆者に手紙を出し、内容の真意を確認いたします。 尚、教科書では、このディオファントゥスの定理(ベズーの等式)をユークリッドの互助法の証明に用いています。 他にイデアルの側面からこの問題について記述した資料を持っていないため、イデアルについての別の教科書を入手し、ベズーの等式についての何らかの記述がないか探して見ます。
- alice_44
- ベストアンサー率44% (2109/4759)
とりあえず、単項イデアル整域の定義くらいは、 教科書で確認されたらいかがですか？ 任意のイデアルが単項生成であるような環を 「単項イデアル整域」と呼びます。 任意の整数 a,b に対して (2) の c が存在することは、 整数環 Z では事実ですが、決して自明とは言えません。 多くの教科書では、Z がユークリッド環であることから、 互除法を使ってベズーの等式(貴方の言う「ディオファンティウスの定理」) の成立を証明し、A No.3 の [X] と [Y] が同値なことから Z が単項イデアル整域であることを証明する…という 手順をとります。その流儀に慣れた者の目には、質問文中の 証明は奇異に写ります。(2) はどこから出てきたのか？と。 A No.3 4 で言われているのは、そういう話です。 (a)+(b)=(c) となる c が存在すること自体は、Z が 結果的に単項イデアル整域であることから、真ではあります。 (a)+(b)⊆(c) であることから、(4) の考察により c|d。 (a)+(b)⊇(c) であることから、c=ra+sb となる r,s が 存在し、A No.2 にあるように (5) の d|c が導けます。 よって、c=d。この部分は単純なのですが、証明全体を見ると、 (2) の根拠を述べていない点に、まだ論証の飛躍があります。 貴方は、「ディオファンティウスの定理」を経由せずに (2) の c の存在を示す方法を見つけたのでしょうか？ そうであれば、問題はないのですが。 下記質問の A No.3 が、ユークリッドの互除法を使って ベズーの等式を示す方法の参考になるでしょうか？ http://okwave.jp/qa/q7600423.html
補足
教科書によると「ディオファントゥスの定理」ですね。 調べたところ、一般的には、仰るとおり、ベズーの恒等式と呼ばれるもののようです。 ここまで引き伸ばして非常に申し訳ないのですが、教科書の証明をもう一度確認したところ、 もとの証明ではイデアル I = (a) + (b) と定義していました。 これで意味が変わってくるかと思います。大変失礼をいたしました。
- kabaokaba
- ベストアンサー率51% (724/1416)
＞(2) (a)+(b)=(c)とおく。c=ra+sbとおける。 ここの前半になぜ疑問がないのかが分からない． Zがユークリッド整域であって， ユークリッド整域ならば単項イデアル整域となるのは既習？ >((2)の時点で、rもしくはsが負の数であれば、aまたはbより小さいことになります。) これは無意味．rやsの符号なんて勝手に決められません． ついでにいうと `` | ''は使わないできちんと言葉で書けば案外分かると思う． そうすればNo.1さんの「自明」もすぐ納得できます． ========== けど，これって別にイデアル使う意味はないというか 「ユークリッド整域が単項イデアル整域」ってのは（(2)の言及） 本質はユークリッドの互除法そのものだった気がする
補足
>>ここの前半になぜ疑問がないのかが分からない． >>Zがユークリッド整域であって， >>ユークリッド整域ならば単項イデアル整域となるのは既習？ Zがユークリッド正域であるのは理解していますが、単項イデアル整域についてはよく分かっていません。 疑問を持っていない理由は、No3の方に補足回答させていただいています。 (その理解が間違っている可能性はありますが…) >>別にイデアル使う意味はない お察しの通り、わざわざイデアルを利用してディオファンティウスの定理の証明をしようとしているのは、ユークリッド互助法と、それに絡む、a,b,が互いに素である時、sa+rb=1となることの必要十分性を証明しようとして、四苦八苦しているというのが原点にあります。 ユークリッド互助法は実際にやってみるのは簡単なのですが、証明などに使おうとするとうまく言語化できないんですよね…
- ramayana
- ベストアンサー率75% (215/285)
（５）を、 「d|a,d|bなら、（２）により、d|c」 とすれば疑問が解消しませんか？ また、（４）は、「よってc≦d」を「よってc|d」に変える方が良いと思います。 あとは、余談です。この証明で最も違和感があるのは、（２）をいきなり出しているところです。 [X] 「a,bの最大公約数は、ra+sbの形で表現できる」 [Y] 「あるcが存在して、(a)+(b)=(c)と表現できる」 という2つの命題を考えます。示された証明は、[Y]を前提にして[X]を導いていますが、 [Y]は、どのようにして導かれたのでしょうか。[X]を使わずに[Y]をいきなり証明するのは、結構難しそうです。
お礼
再検討する中でそのように読み替えています。ありがとうございます。 ご指摘の疑問ですが、(c)は、イデアルIの生成元である、というくらいの意味です。 aとbの2数を生成元としているのですから、おのずと「aの倍数」と「bの倍数」の加算によって、Iは生成されているはずです。ですから、Iはaとbの公約数を、同時にその元として持つはずです。 (ただし、ここではcがどのような公約数であるのか、全く限定していません。)
- アウストラロ ピテクス（@ngkdddjkk）
- ベストアンサー率21% (283/1290)
a＝xd、b＝ydとおいたら、cの式にdが含まれませんか？
お礼
理解できました。単純でしたね…
- アウストラロ ピテクス（@ngkdddjkk）
- ベストアンサー率21% (283/1290)
自明な話では？
補足
他人にとって自明なことが、自分にとってとてつもなく難解だということがよくあるものです…
お礼
ご指摘ありがとうございます。途中から記述を変えています。ディオファントゥスです。 また、単項イデアルという「単語」そのものが参照した教科書に載っていませんでした。(I=(a)として利用していた意味については把握しており、副読本として利用している別の代数学入門書で単項イデアルという単語を確認しました。) 何度も書いていますが、証明そのものは整数論入門の教科書に書いてある内容です。そして、(2)の詳細は教科書には書かれていません。教科書では、ユークリッドの互助法をディオファントゥスの定理から証明しています。 ともあれ、本題の証明はユークリッドの互助法を使って地道にやるのが正道ということで、そのことは理解いたしました。また、(2)については、教科書の執筆者に問い合わせてみます。