本节介绍整除的概念，带余除法定理及其相关应用.按照惯例，分别用Z，Q，R，C表示整数集，有理数集，实数集和复数集.
定义1.1.1 设a，b∈Z.称b整除a，记作b|a，若存在q∈Z使得a=qb.此时称b是a的因数，而称a是b的倍数.否则，称b不整除a，记作
下面的命题是明显的.
命题1.1.2 设a，b，c，ai，xi∈Z，i=1，2，…，n.则
（1）若b|a，则±b|±a.
（2）若a|b，b|c，则a|c.
（3）若b|ai，i=1，2，…，n，则b|a1x1+…+anxn.特别的，若b|a，b|c，则b|a±c.
（4）若b|a，则bc|ac.
（5）若b|a，则|b|≤|a|或a=0.
例1.1.3 设a，b，c∈Z且a-c|ab+cd.则a-c|ad+bc.
证明 由事实a-c|（a-c）（b-d）=ab+cd-（ad+bc）及已知条件立得结论.证毕.
命题1.1.4 设a，b，m∈Z，m＞0.则a-b|am-bm.若m还是奇数，则a+b|am+bm.
证明 前一结论可由等式
am-bm=（a-b）（am-1+am-2b+…+abm-2+bm-1）
获得，而后一结论可由等式
am+bm=（a+b）（am-1-am-2b+…-abm-2+bm-1）
获得.证毕.
例1.1.5 设m是非负整数，x是正整数，则x2+x+1|xm+2+（x+1）2m+1.
证明 当m=0时结论显然成立.下设m＞0.据命题1.1.4，有
x2+x+1=x2+2x+1-x|（x2+2x+1）m-xm.
故由
xm+2+（x+1）2m+1=x2xm+xm（x+1）+（x2+2x+1）m（x+1）-xm（x+1）
=xm（x2+x+1）+（x+1）（（x2+2x+1）m-xm）
可知结论成立.证毕.
例1.1.6 设r是正奇数，n是正整数，则n+2不能整除
证明 记
则2s=2+（2r+nr）+…+（nr+2r）.据命题1.1.4，有
n+2|2r+nr，n+2|3r+（n-1）r，…，n+2|nr+2r.(www.xing528.com)
于是n+2|2s-2，从而n+2不能整除s.证毕.
下面介绍初等数论中具有基本意义的带余除法定理.
定理1.1.7（带余除法定理） 设a，b∈Z，b＞0，则存在唯一的整数对（q，r）使得
a=qb+r，0≤r＜b.
此时，称q为a被b除得到的商，而称r为a被b除得到的余数.
证明 对任意整数i，用符号［ib，（i+1）b＞表示大于等于ib而小于（i+1）b的整数构成的集合.则
由a∈Z知存在q∈Z，使得qb≤a＜（q+1）b.于是0≤a-qb＜b.记r=a-qb.则有
a=qb+r，0≤r＜b.
若有q，q′，r，r′∈Z，使得a=qb+r=q′b+r′，0≤r，r′＜b.则-b＜rr′＜b，b|r-r′.据命题1.1.2（5）知r=r′，进而有q=q′.证毕.
例1.1.8 求235和-235被17除得到的商和余数.
解 由235=13×17+14，0≤14＜17和-235=-14×17+3，0≤3＜17知235被17除得到的商和余数分别是13和14；-235被17除得到的商和余数分别是-14和3.解毕.
例1.1.9 任意100个整数中，必有两个整数之差能被99整除.
证明 任取100个整数，则这些数被99除的余数只能是0到98这99个数中之一.故这100个数中必有两个数被99除所得余数相同.显然，这两个数的差就能被99整除.证毕.
若一个整数是某个整数的平方，则称这个数为完全平方数，简称平方数.下面的命题给出了平方数的许多有趣性质.
命题1.1.10 平方数有如下性质：
（1）平方数的个位数码只能是0，1，4，5，6，9.
（2）偶平方数能被4整除，奇平方数被4除余1.
（3）偶平方数被8除余0或4，奇平方数被8除余1.
（4）对任意正整数n，n2与（n+1）2之间无其他平方数.
例1.1.11 设x，y是正整数.证明x2+y+1与y2+4x+3不能同时是平方数.
证明 若x≥y，则
x2＜x2+y+1≤x2+x+1＜（x+1）2.
因此x2+y+1不是平方数.设x＜y，则y2＜y2+4x+3＜（y+2）2.若y2+4x+3是平方数，则y2+4x+3=（y+1）2，从而y=2x+1.此时，
（x+1）2＜x2+y+1=x2+2x+2＜（x+2）2，
故x2+y+1不是平方数.证毕.
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
