[代數] 最大公因數可被公因數整除

[yyc2008 ()]

大家好
我想請教一個證明

在不動用到質因素分解定理之下

試證:
最大公因數可被所有公因數給整除

可以使用principle of well ordering
以及
整數a可用整數b表達成a = bq + r 其中0 <= r < |b|

謝謝回答

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 128.220.159.5
推 coolbetter33:d|b,d|a ==> d|(a,b)
→ coolbetter33:pf.∃m∃n s.t b=dn,a=dm then (a,b)=(dm,dn)=d(m,n)
推 WINDHEAD    :雖然不知道你要的基本證明到底有多基本,不過既然你
→ WINDHEAD    :提到well order那就可以這樣想:  給定整數a,b
→ WINDHEAD    :考慮 S={am+bn|m,n整數}. 令d為S中最小的正整數
→ WINDHEAD    :任取 S 中元素 t, 考慮除法 t=dq+r 可知 0<=r<d
→ WINDHEAD    : r=t-dq 所以 r 也是S中的元素 , 故r=0
→ WINDHEAD    :所以 d 整除 S中所有元素,簡單說 d 是a,b的公因數
→ WINDHEAD    :但是 d 本身也是S的元素,所以任何a,b的正公因數都要
→ WINDHEAD    :整除 d, 所以不能比d大,也就是說d是a,b的最大公因數
→ yyc2008     :感謝強者們的解答 另外想請問 還有比well ordering更
→ yyc2008     :基本的證明嗎?  感謝WINDHEAD
→ yyc2008     :還有風頭大定義的S有沒有要一定am+bn >= 0 有一點我
→ yyc2008     :解的是為什麼Well order一定要非負整數 包含負整數不
→ yyc2008     :行嗎?
→ WINDHEAD    :負數沒有影響基本上可以不管他,你只看一邊而已
→ WINDHEAD    :S的定義就必然會包含一堆正數了....負的不用管他
→ WINDHEAD    :因為你實際上是靠係數 m,n 的正負來調節的
推 WINDHEAD    :有沒有更基本的我就不懂了,不過你可以看出這個方法
→ WINDHEAD    :很迂迴,但反而得到一些更有結構感的東西
→ WINDHEAD    :這個故事裡面重要的是S而不是a,b. 有時候不同的a,b
→ WINDHEAD    :會給出同樣的S集合....那個S才是重要的
→ yyc2008     :謝謝WINDHEAD大 我覺得這方法最神奇的就是知道最小的
→ yyc2008     :正整數就是d 要不然有時候是r 不是很直觀 感覺有點像
→ yyc2008     :是知道結尾之後 再用一種很神奇看不出所以然的方式寫
→ yyc2008     :出來 難怪叫抽象代數XD 另外我的問題是 這個well-ord
→ yyc2008     :一定非要 非負整數才行嗎 只要有序的話 不是任何整數
→ yyc2008     :集合都應該有效 有一樣的結論吧? 直觀上是這樣
→ WINDHEAD    :well-order只適用於正整數...不過這種抽象的東西可以
→ WINDHEAD    :跳過啦,用直覺想正整數集合一定有最小元素就好啦
→ WINDHEAD    :如果要抽象的話我當初就直接說 S 是a,b生成的理想了
→ yyc2008     :嗯... 等我學到那裏再來請教WINDHEAD
→ yyc2008     :謝謝WINDHEAD大
推 WINDHEAD    :XD
推 jacky7987   :還是校長的理想呢（誤
→ Vulpix      :明明是激進的理想！
→ Vulpix      :(其實不是= =)
→ sneak       : 謝謝WINDHEAD大 https://muxiv.com
→ sneak       : 會給出同樣的S集合.. https://daxiv.com
→ muxiv       : 雖然不知道你要的基本證 https://muxiv.com