引用:
原帖由 wushing 於 2007-9-28 03:11 PM 發表 
let a and b be integers with b>0. then there exist unique integers q and r with the property that a = bq+r, where 0 < r < b or 0 ...
這是數論裡面整數的除法原理，
幾乎數論的書(至少英文的啦)都會有證明
如果手邊沒有書的話可以參考
http://en.wikipedia.org/wiki/Division_algorithm
簡述上面維基百科的證明(請參見原文討論較詳細)，
要證明 a 被 d 除，一定可以找到商數 q 與餘數 r ，使得 a = qd + r ，
首先證商數與餘數的存在性，
令
不管 d>0 or d<0 ，都可以根據阿基米得原理知道 S 必包含有非負的整數為元素，
再根據良序法則，自然數的非空子集必包含有最小元素，故令此元素為 r ，
可得 r 是 a - nd 的最小正元素，令此時的 n 為 q ，則可得 a = qd +r
接下來，要證: 0 ≤
r < |
d|
0 ≤
r 的部分，根據 r 當初選許的特性(正整數集合的非空子集的最小元素)，恆成立。
若 r ≧ |
d| ，則分開討論若 d >0 or d<0 ，都可以選取新的商數 q' ，使得 r 並非
裡面的最小正元素。
故，對任意的整數 a, 非零整數 d ，皆
存在 q 與 r ，使得 a = qd +r ，且 0 ≤
r < |
d|
接下來，後半段證明: q 與 r 的唯一性。
假設 a 被 d 除，有兩組 q,r, Q, R 皆滿足 a = qd +r ，且 0 ≤
r < |
d| ，a = Qd +R ，且 0 ≤
R < |
d|
不失一般性，可以假設 q ≤ Q ，因為 a = qd +r = Qd +R ，移項，得 d(Q-q) = (r-R) ，
若 d 為正數，因為 d 與 Q-q 皆非負，所以 r-R 非負，故 r≧R ，
但因為 0 ≤
r < |
d| = d 且 0 ≤
R < |
d| = d ，所以 0 ≤ r-R < d (前半塊的 0 ≤ 是由於上面那行 r-R 非負)
同理，若 d <0 討論可得 0 ≤ |r-R| < |d| ，但因為 d(Q-q) = (r-R) ，表示 r-R 是 d 的倍數 ，
故 |r-R|=0 ，也就是 r-R =0 ，也就是 r=R ，帶入 d(Q-q) = (r-R) = 0 ，因為 d 非零，所以 Q-q =0
也就是 Q=q ，唯一性由此得證。
或是參見
WILLIAM CHEN 教授 在網站上提供的講義，
http://www.maths.mq.edu.au/%7Ewchen/lnentfolder/ent01-df.pdf
第一頁的第一個定理(及證明)就是了
