整除.md

设$a$和$b$是任意整数，若存在整数$c$，使得$a=bc$，则说$a$是$b$的倍数，$b$是$a$的因数。或者说$a$被$b$整除，而$b$整除$a$，记为$b\mid a$

显然，任意数整除$0$

特别地，$0\mid 0$，$1$和$-1$整除任意整数

定理

1. 对于任意整数$a$和$b$，$b\ne 0$存在唯一的一对整数$q$和$r$，使得$0\le r\lt |b|$，$a=qb+r$

   $q$称为（不完全）商数，$r$称为$a$被$b$除的余数（mod）

2. $b\mid a$，$b\ne0$当且仅当$a$被$b$除的余数为$0$

   • 充分性：因为$b\mid a$，存在整数$c$使得$a=bc$，取$q=c,r=0$可满足$a=qb+r$，而根据(1)，这样的$(q,r)$唯一，因此$a$被$b$除的余数为$0$
   • 必要性：因为$a$被$b$除的余数为$0$，所以存在唯一的整数$q$使得$a=qb+0$，于是$b\mid a$

性质

1. 若$a\mid b$，$b\mid c$，则$a\mid c$

2. 若$a\mid b$，则$a\mid bc$

3. 若$a\mid b$，$a\mid c$，则$a\mid b\pm c$

4. 若$a\mid (b_1,\cdots,b_n)$，则$a\mid \lambda_1b_1+\cdots+\lambda_nb_n$，其中$\lambda_i$为任意整数

5. 若一个等式中，除了某项之外，其余各项都是$a$的倍数，则此项也是$a$的倍数

   这是第四条的直接推论 例如，在等式$b-c=-d+e+f$中，设$b$，$c$，$d$，$f$都是$a$的倍数，求证$e$也是$a$的倍数。解出$e$得$e=b-c+d-f$。右边的项全是$a$的倍数，所以根据第四条，它们的线性组合也是$a$的倍数，得证。 ^88f1fb

6. 若$a\mid b$，$b\mid a$，则$b=\pm a$

   $a=b=0$时显然成立，$a\ne 0$且$b\ne 0$时有如下证明 $a\mid b$，则存在整数$c_1$使得$b=c_1a$，同理存在整数$c_2$使得$a=c_2b$，于是$b=c_1c_2b$ 于是$c_1c_2=1$，于是$c_1$和$c_2$要么都是$1$，要么都是$-1$，所以$b=\pm a$

7. 设$a=qb+c$，则$a,b$的公因数和$b,c$的公因数是完全相同的

   对于任意一个$a$和$b$的公因数$x$，$a$是$x$的倍数，$b$是$x$的倍数，于是$qb$也是$x$的倍数，于是由第五条可知，$c$也是$x$的倍数。

   对于任意一个$b$和$c$的公因数$x$，$b$是$x$的倍数，$c$是$x$的倍数，于是$qb$也是$x$的倍数，于是由第五条可知，$a$也是$x$的倍数。

   于是$a,b$的公因数和$b,c$的公因数是完全相同的（！好像蕴含了什么不得了的东西） ^abc9de