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\)