[離散]基礎數論

2012-08-23

想請問第二張圖的最下面四行，想請問為什麼d如果是m,n的公因數，為什麼則d為k的因數呢?又為何可以假設有一個d的絕對值是小於等於k，所以
k為m,n的最大公因數，可以這樣子隨意假設一個d值絕對值小於等於k，則k就是最大公因數嗎?感覺這四行證明怪怪的~

線代離散助教(wynne)2012年8月23日晚上11:32
1. d若是m, n的公因數,
則 m = de, n = df, for some e, f
則 k = ms + nt = des + dft = d(es + ft)
=> d | k
所以結論就是, 若 d 為m, n的公因數,
則 d 為 k 的因數

2. 最後那一段換句話說就是, 既然我們已經證明了所有m, n的公因數都要是 k 的因數, 那這樣就說明了 k 一定要是最大公因數
回覆刪除
回覆
葉子2012年8月25日下午6:04
可是有一點覺得奇怪，即使d為k的公因素，也沒有辦法保證k是最大公因數阿~k也只是m,s的公因數而已不是嗎?
回覆刪除
回覆
線代離散助教(wynne)2012年8月26日凌晨1:34
不是的, 整段要一起看, 因為這裡的結論是一個若p則q的命題, 所以既然我們最後證明了 "d若是m, n的公因數, 則 d 為 k 的因數", 而這句話的意思又是 "所有m, n的公因數都一定要是 k 的因數", 此即說明 k 一定要是最大公因數
回覆刪除
回覆
葉子2012年8月26日下午3:29
恩....謝謝助教...
回覆刪除
回覆