標籤: 暫無標籤

對任意整數a,b且b≠0,存在唯一的整數q,r,使a=bq+r,其中0≤r<|b|,這個事實稱為帶余除法定理,是整除理論的基礎。若c|a,c|b,則稱c是a,b的公因數。若d是a,b的公因數,且d可被a,b的任意公因數整除則稱d是a,b的最大公因數。當d≥0時,d是a,b公因數中最大者。若a,b的最大公因數等於1,則稱a,b互素。累次利用帶余除法可以求出a,b的最大公因數,這種方法常稱為輾轉相除法。又稱歐幾里得演算法。
帶余除法的證明:【存在性】作整數序列
…,-3b,-2b,-b,0,b,2b,3b,…
則a必在上述序列的某兩項之間,即存在一個整數q使得
qb≤a<(q+1)b
成立。令a-qb=r,即證存在性。
【唯一性】設q1、r1是滿足a=bq+r,0≤r<b的另一對整數,因為
bq1+r1=bq+r,
於是
b(q-q1)=r1-r
b|q-q1|=|r1-r|
由於r及r1都是小於b的非負整數,所以上式右邊是小於b的。
如果q≠q1,則上式左邊≥b,這是不可能的。即證唯一性。
上一篇[除式]    下一篇 [《初次與你相遇》]

相關評論

同義詞:暫無同義詞