1.整除，最大公因数和最小公倍数
1.1 整除
若整数 \(b\) 除以非零整数 \(a\) ，商为整数，且余数为零，\(b\) 为被除数，\(a\) 为除数，即\(a|b\)，读作“ $a $整除 $b $ ”或“ $b $能被 $a $ 整除”。
其中，整除具有如下三条性质：
- 整除的传递性，证明如下：
如果 \(a|b,b|c\) ，那么有 \(a|c\) 。
设 \(a=k_1b\), \(c=k_2b\) ，可得 \(c=k_1k_2a\) ，是 \(a\) 的倍数。所以有 \(a|c\) 。
- 整除的可加减性，证明如下：
如果 \(a|b,a|c\) ，那么有 \(a|(b+c),a|(b-c)\)
对于满足题意的 \(a,b,c\) , \({\exists}k_1,k_2\in \mathbb{Z}\) 使得 \(b=k_1a,c=k_2a\) 。
所以 \(a|(b+c)\) 等价于 \(a|(k_1+k_2)a\) 。因为 \(k_1+k_2,k_1-k_2\in \mathbb{Z}\) ，所以 \(b+c=(k_1+k_2)a\) 是 \(a\) 的倍数，有 \(a|(b+c)\) 。可减性同理。
- 整除的可乘性，证明如下：
如果 \(a|b,a|c\) ，那么对于 \(x,y \in \mathbb{Z}\) ， \(a|(bx+cy)\) 。
设 \(b=k_1a,c=k_2a\) , 因为 \(x,y\in \mathbb{Z}\) ，所以有 \(a|k_1xa,a|k_2ya\) ，即 \(a|bx,a|cy\) 。由于整除具有可加减性，那么 $a|(bx+cy) $ 。
例题
1.1.1 如果 \(x+6y\) 是 \(7\) 的倍数，那么 \(5x+2y\) 也是 \(7\) 的倍数。
因为整除的可加减性，由于 \(7|(x+6y)\) ，所以 \(7|(5x+30y)\) 。
又因为 \(7|28y\) ，所以由于整除的可加减性， \(7|(5x+30y-28y)\) ，即 \(7|(5x+2y)\) 。
1.1.2 如果 \(3|x,7|x\) , 则 \(21|x\) 。
设 \(x=3\times 7\times k\) ，并且 \(k \in \mathbb{Z}\) 。由于 \(7k \in \mathbb{Z}\) ，所以一定 \(3|x\) ；由于 \(3k \in \mathbb{Z}\) ，所以一定 \(7|x\) 。
1.1.3 求证：\(8|3^{2n+1}+5\)
原命题等价于 \(8|3\times 9^{n} +5\) 。
当 \(n=1\) 是，\(3\times 9^{n} \equiv 3 (\bmod 8)\)
当 \(n>1\) 时，若 \(3\times 9^{n-1} \equiv 3 (\bmod 8)\) ，那么有 $3\times 9^{n}\equiv 3\times 9 (\bmod 8) $ 。整理得到 $3\times 9^{n}\equiv 3 (\bmod 8) $
那么 \(3\times 9^{n}+5 \equiv 3+5(\bmod 8)\) ,即 \(3\times 9^{n}+5 \equiv 0(\bmod 8)\) 。所以 \(8|3^{2n+1}+5\)