数论：整数的整除

一、概念

若整数b除以非零整数a，商为整数，且余数为零，b为被除数，a为除数，即a|b（“|”是整除符号），读作“a整除b”或“b能被a整除”。a叫做b的约数（或因数），b叫做a的倍数。整除属于除尽的一种特殊情况。

二、常用整除

一个数被3、9、7、11整除特性：

1.一个正整数的各位数字之和能被3整除， 那么这个正整数能被3 整除；

2. 一个正整数的各位数字之和能被9整除， 那么这个正整数能被9 整除；

3. 一个正整数的奇数位数字之和与偶数位数字之和的差能被11整除， 那么这个正整数能被 11 整除；

4. 一个正整数的末三位数字组成的数与末三位数字之前的数字组成的数之差能被7 (或 11) 整除, 那么这个正整数能被7(或11) 整除。

三、带余除法（欧式除法算式）

一般地, 设 a, b为整数, 且b≠0.则存在惟一的一对整数q和r， 使得a=bq+r,0≤r<|b|. 

补充知识：

多项式带余除法定理

任意非零多项式g(x) 除f(x) ，其商式余式一定存在，且余式是惟一满足关系式f(x)=g(x)q(x)+r(x) 的零多项式，或次数小于q(x) 的一个多项式。

多项式除以多项式

多项式除以多项式一般用竖式进行演算

（1）把被除式、除式按某个字母作降幂排列，并把所缺的项用零补齐；

（2）用被除式的第一项除以除式的第一项，得商式的第一项；

（3）用商式的第一项去乘除式，把积写在被除式下面（同类项对齐），消去相等项，把不相等的项结合起来；

（4）把减得的差当作新的被除式，再按照上面的方法继续演算，直到余式为零或余式的次数低于除式的次数时为止。被除式=除式×商式+余式。如果一个多项式除以另一个多项式，余式为零，就说这个多项式能被另一个多项式整除。

四、素数（质数）

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

质数的个数是无穷的。

欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：

假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn。

如果N+1为素数，则N+1 要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。

如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除。

所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。

100以内的素数有：2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97共有25个素数.