1.設a, b, c, d皆為正整數, 已知a = 1271b + 2294, b = 6882c - 6216, 則a與b的最大
公因數為何？
書上解法：
a = 1271b + 2294
=> (a,b) = (b,2294)
b = 6882c-6216 = 2294 * 3c - 6216
=> (b,2294) = (2294,6216) =74
但我有點疑問
輾轉相除法原理(照課本龍騰版課本上的敘述打上來的)
兩正整數a和b,
若將a除以b, 得商數q, 餘數r,
即a=bq+r, 0<＝r<b,
則(a,b) = (b,r)
那b = 2294 * 3c - 6216
是不是要改寫成b= 2294 * 3(c-1) +666
(b, 2294) = (2294, 666) = 74 這樣子做嗎?
還是說輾轉相除法不限制餘數要正數嗎?
那a與b也要正整數嗎?還是整數也可?
高一上-輾轉相除法1題
2011-01-05 2:29 am
回答 (2)
2011-01-05 5:42 am
✔ 最佳答案
a=bq+r，其中0 <= r < b，則(a,b)=(b,r)但(b,r)=(b,r+b)嗎？因為r+b=b*1+r，其中0 <= r < b，
即(r+b)除以b，商為1，餘數為r，
所以(r+b,b)=(b,r)用減的也一樣
(b,r)=(b,r-b)嗎？
因為r-b=b*(-1)+r，其中0 <= r < b，
即(r-b)除以b，商為(-1)，餘數為r，
所以(r-b,b)=(b,r)所以(a,b)=(b,r)=(b,r+b)=(b,r+2b)=(b,r+3b)=(b,r-b)=(b,r-2b)=(b,r-3b)=....=(b,r+nb)
我們的確可以從"0 <= 餘數 < 除數"這個限制推論出餘數不在這個範圍內也符合的。
2011-01-05 4:31 am
要有相同 g.c.d. 不限制取正常的 "餘數".
但實務上都按正常除法取餘數.
但實務上都按正常除法取餘數.
收錄日期: 2021-05-04 01:44:11
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20110104000016KK04898