【 ユークリッドの互除法が成り立つ理由の証明につい

質問

【 ユークリッドの互除法が成り立つ理由の証明について】

実教出版数学Aのp89に記載されている、以下の定理と証明で
G＝G'
となる理由について、私の解釈が数学的に正しいのか、その他アドバイス等、ご教示よろしくお願いします。
ただし、Thm．1を前提としています。

【Thm．1 割ったときのあまりと公約数】

自然数a，bについて，aをbで割った余りをrとするとき
1.aとbの公約数は、rの約数になっている。
2.bとrの公約数は、aの約数になっている。

【Thm2．割ったときのあまりと最大公約数】

自然数a,bについて、aをbで割ったときのあまりをrとするとき、aとbの最大公約数的Gと、bとrの最大公約数Gは等しい。

Pf．aとbの最大公約数Gもrの約数となるから、Gはbとrの公約数である。bとrの最大公約数はG'であるから
G≦G'……(1)
同様に、bとrの最大公約数G'はaの約数であるから
G'≦G……(2)
(1)，(2)より
G＝G'証明終

【解釈】
証明したいのはG＝G'である。
(1)はG＜G' または G＝G'という意味である。
また、(2)はG'＜G または G'＝Gという意味である。
(1)，(2)より
G'＜G＜G' または G＝G'かつG'＜G＜G' または G'＝Gがいえる。
または、というのはどちらか一方が成り立てば良いという意味である。ここでもし、G＝G' またはG'＝Gが成り立てば命題が証明できたことになるが、どちらも成り立たないとすると、
G'＜G＜G' または G＜G'＜G…☆
が成り立たなければならない。
ところが、☆が成り立つときもG＝G'が成り立つので、結局
G＝G'である。
証明終
具体的な例で示すと、G'＝3のとき
3＜G＜3
つまりG＝3
G＝3より
3＜G'＜3
つまりG'＝3
したがって、
G＝G'
であることがいえる。

数学が得意な方には言語化せずにもわかることかもしれませんが、記号の意味を正しく理解して使いたいと思い、掘り下げて考えてみました。
誤りの指摘や、今後の学習に関するアドバイスなどをいただければ幸いです。

回答No.6

178-tall

錯誤訂正。

　…
ならば、生き残りは B = D だといえませんか…。

回答No.5

178-tall

ANo.3 への「補足」にて、a≦b かつ b≦a → a＝b　を示すのに、
>a≦bについて
>A．a＜b
>B．a＝b
>b≦aについて
>C．b＜a
>D．b＝a
… という「組み合わせ」(場合分け) を提示なさってますネ。

{ A または B } と { C または D } の共通セットは何？
… というのが狙いですネ。

一見して、B と D は同義。また、A は B, C と両立不能。
ならば、生き残りは A = D だといえませんか…。

回答No.4

f272

a≦bかつb≦aとなるようなa，bはa＝bしかない
ということですね。
元の問題に戻っても，G≦G'かつG'≦Gなのだから，G＝G'となって証明終です。

回答No.3

tmppassenger

ああ、前の質問でも確かにそう書いていましたが、つまりそもそも

> a＜b＜aとなるようなbは明らかにb＝aのみ
要は、「b=aの時はa<b<aが成り立つ」、つまり「a<a<aは正しい」、よって「a<aは正しい」と考えているのですね？そもそもこれが間違っている。

#2さんが書いたことも参考にしてください。

補足

確かに、おっしゃる通り不等号の意味がおかしいです。論理にこだわるあまり明らかに誤りであることに気がつきませんでした。ご教示感謝します。

私の知識ではa≦bは
a＜b または a＝b
と教わったものしかありませんし、この「または」というのは「少なくともどちらか一方が成り立つ」という意味で使用しています。
したがって，「どちらか一方が成り立つ」場合と「どちらも成り立つ」場合について考えたのです。ところが，ご指摘の通りa＜bとa＝bが同時に成り立つことはありえませんね。

とすると，先の命題
『a≦bかつb≦aならばa＝bが成り立つ』はどのように証明したら良いのでしょうか。
証明，といいますか自分が納得したいというのが目的なのですが，≦を流用する形で
b≦a≦b かつ a≦b≦a
とすれば，≦が正しく使えているので，（恐らく）a＝bとなるのだと思います。
しかし，≦とは＜または＝という意味ではないか？と考えて，あえて＜と＝にわけてそれぞれのありうる場合を考えました。
ところで，ご指摘いただいた通り
a＜bとa＝bは同時に成り立たないので，a≦bかつb≦aのとき，次の4通り考えられます。

a≦bについて
A．a＜b
B．a＝b
b≦aについて
C．b＜a
D．b＝a

それぞれの組み合わせを順番に見ていきます。
［1］ AとC
a＜b かつ b＜a
［2］AとD
a＜b かつ b＝a
［3］BとC
a＝b かつ b＜a
これらはいずれも成り立ちません。
［4］BとD
a＝b かつ b＝a
これは成り立ちます。
したがって，
『a≦bかつb≦aならばa＝bが成り立つ。』
というのは，証明，というよりも
a≦bかつb≦aとなるようなa，bは
a＝bしかない，ということを言いたかったのでしょうか。

拙い考えで申し訳ありませんが，ご返答をいただければと思います。

回答No.2

f272

a<bというのは「aはbより小さい」ということだと考えているのですよね。
そういうときに
C．a＜b かつ a＝bが成り立つ
を見て，どう考えますか？「aはbより小さくて，aとbは等しい」と言っているわけです。あり得ないでしょ。

そういう観点で自分の書いたことを読み直してください。

補足

確かに、おっしゃる通り不等号の意味がおかしいです。論理にこだわるあまり明らかに誤りであることに気がつきませんでした。ご教示感謝します。

私の知識ではa≦bは
a＜b または a＝b
と教わったものしかありませんし、この「または」というのは「少なくともどちらか一方が成り立つ」という意味で使用しています。
したがって，「どちらか一方が成り立つ」場合と「どちらも成り立つ」場合について考えたのです。ところが，ご指摘の通りa＜bとa＝bが同時に成り立つことはありえませんね。

とすると，先の命題
『a≦bかつb≦aならばa＝bが成り立つ』はどのように証明したら良いのでしょうか。
証明，といいますか自分が納得したいというのが目的なのですが，≦を流用する形で
b≦a≦b かつ a≦b≦a
とすれば，≦が正しく使えているので，（恐らく）a＝bとなるのだと思います。
しかし，≦とは＜または＝という意味ではないか？と考えて，あえて＜と＝にわけてそれぞれのありうる場合を考えました。
ところで，ご指摘いただいた通り
a＜bとa＝bは同時に成り立たないので，a≦bかつb≦aのとき，次の4通り考えられます。

a≦bについて
A．a＜b
B．a＝b
b≦aについて
C．b＜a
D．b＝a

それぞれの組み合わせを順番に見ていきます。
［1］ AとC
a＜b かつ b＜a
［2］AとD
a＜b かつ b＝a
［3］BとC
a＝b かつ b＜a
これらはいずれも成り立ちません。
［4］BとD
a＝b かつ b＝a
これは成り立ちます。
したがって，
『a≦bかつb≦aならばa＝bが成り立つ。』
というのは，証明，というよりも
a≦bかつb≦aとなるようなa，bは
a＝bしかない，ということを言いたかったのでしょうか。

拙い考えで申し訳ありませんが，ご返答をいただければと思います。

回答No.1

tmppassenger

要は 『 a≦bかつ b≦a ならば a=bが成立する 』ことを証明したいだけですよね。ユークリッドの互除法云々は関係ないですね。

で、≦をどう定義しているかによりますが、a≦bを「a<b又はa=b」と定義しているなら、b≦aは「b<a又はb=a」となりますが、そこから「a<b<aまたはa=bかつa<b<aまたはb=a」というのが、「または」と「かつ」がどこにかかっているのかを含めて良く分からない。きちんと書けば、考えなければならない場合は4通り出て来るはずでしょう？

因みに、「<」（狭義半順序）が満たしている3つの性質（2つにまとめられますが）は理解していますか？（言葉でかけば、「非反射性」「非対称性」「推移性」です）

補足

“要は 『 a≦bかつ b≦a ならば a=bが成立する 』ことを証明したいだけですよね。”
≫その通りです。≦の定義についてですが，a≦bは aはb以下という意味でお願いします(大学レベルの数学は未履修です)。
したがって，
a<b(aはbより小さい)または a=b
として考えました。半順序は離散数学で習うのだと知りましたが、全くわかりません。

以下、自分なりに考えて見たことを書いて見ます。

GとG'はそれぞれa，bと置き換えます。
次の命題を示します。
命題：「a≦bかつ b≦a ならば a=bが成立する 」

a≦bは定義より，
a＜b または a＝b …(1)
b≦aは定義より，
b＜a または b＝a …(2)
(1)，(2)が成り立つとき，a＝bが常に成り立つことを示す。

(1)を場合分けすると次の3通り。
A．a＜bのみ成り立つ
B．a＝bのみ成り立つ
C．a＜b かつ a＝bが成り立つ

(2)を場合分けすると次の3通り。
D．b＜aのみ成り立つ
E．b＝aのみ成り立つ
F．b＜aかつb＝aが成り立つ

したがって，(1)と(2)の組み合わせを考えると全部で9通り。
このうち，a＝b または b＝aを含む8通りに関しては命題が示されたことになる（これは正しいのでしょうか？＝で結ばれているからという理由しか浮かびません）。

また、残りのAとDの組み合わせは
a＜b かつ b＜a
これより，次のことが言える。
aに関して，
b＜a＜b
となるようなaは明らかにa＝bのみ（aとなる区間にbしか存在しない）
bに関して，
a＜b＜a
となるようなbは明らかにb＝aのみ
（bとなる区間にaしか存在しない）
よって，
a＝b が成り立つ。
したがって，9通りのいずれもa＝bが成り立つので命題が証明された。

浅学のためこのようなことしか思いつきません。考えなければならない4通りというのはどういった場合なんでしょうか。ご教示いただければと思います。