固定q并对n用数学归纳法.
1. n=0时, 由定义知,0=0q+0.取m=0, r=0且r满足0<=r<q.
2. 假设n=k时, 存在m和r,且0<=r<q,并有k=mq+r.下面证明当n=k+1时, 存在m'和r'且0<=r'<q,并有k+1=m'q+r'.
由k=mq+r得k+1=mq+(r+1).
分类讨论:
1' 若r+1<q, 则取m'=m, r'=r+1,r'满足0<=r'<q且k+1=m'q+r'.
2' 若r+1=q, 则k+1=mq+(r+1)=mq+q=(m+1)q+0.取m'=m+1, r'=0满足0<=r'<q且k+1=m'q+r'.
3' 由r<q知r+1<=q[命题2.2.12(e)],由序的三歧性知,r+1>q不成立.
1. n=0时, 由定义知,0=0q+0.取m=0, r=0且r满足0<=r<q.
2. 假设n=k时, 存在m和r,且0<=r<q,并有k=mq+r.下面证明当n=k+1时, 存在m'和r'且0<=r'<q,并有k+1=m'q+r'.
由k=mq+r得k+1=mq+(r+1).
分类讨论:
1' 若r+1<q, 则取m'=m, r'=r+1,r'满足0<=r'<q且k+1=m'q+r'.
2' 若r+1=q, 则k+1=mq+(r+1)=mq+q=(m+1)q+0.取m'=m+1, r'=0满足0<=r'<q且k+1=m'q+r'.
3' 由r<q知r+1<=q[命题2.2.12(e)],由序的三歧性知,r+1>q不成立.
