關於 輾轉相除法原理 一問

Question

很不幸地知識 會吃字,
所以勞駕您到敝人的blogger
http://vampire-sheep.blogspot.com/
請注意我不是蓄意要衝人數或什麼,
只是對我來說貼到那邊是最快最簡易的方式
我知道問題很基礎,再次感謝

Answer 1

兩正整數 a 和 b ,若將 a 除以 b ,得商數 q ,餘數 r ,即
a = bq＋ r , 0小於等於 r 則
(a,b) = (b,r)

證明:
設 (a,b) = d1, (b,r) = d2, 將證明 d1 = d2
因為 (a,b) = d1,
由 d1| a 且 d1| b, 可得 d1| (a-bq), 即 d1| r
故 d1 也是 b 和 r 的公因數,因此 d1小於等於d2

問題來了,我不懂為何d1"小於"等於d2
等於還可以理解,但是小於就...
請解答,THX
先更正你的符號 d1 | a 表示 d1 可以整除 a
d1/a 是分數 "a分之 d1" 的意思
回到你的問題
當我們設 (b, r) = d2 時, 表示 d2 是 b 和 r 的最大公因數
也就是說: 所有 b 和r 的公因數 都會是 d2 的因數
而且會小於等於 d2
試看 (12, 16) = 4
4 是12 和16 的最大公因數
而 1, 2, 4 都是12 和16 的公因數
它們都是 4 的因數, 其中 1, 2 小於4,而4 等於 4.
另一點
當我們說 d1 小於等於 d2 時 是指 d1小於 或 等於 d2
這樣在往後繼續的證明裡
你會得到 d2 小於等於 d1
然後得到最後的結論 d1 = d2
如果有問題, 請來函討論. 不然, 我可能會錯失你再補充的疑點.