【7】整除性与余数

定义7.1 $a,b$ 是整数 $a\ne 0$ ，若存在整数 $k$ 使 $b=ka$ ，则称整数 $a$ 能整除整数 $b$ ，或称 $b$ 能被 $a$ 整除，记作： $a\mid b$ 。否则，称整数 $a$ 不能整除整数 $b$ ，或称 $b$ 不能被 $a$ 整除，记作： $a\nmid b$ 。
请根据以上定义判断以下每对数是否整除：

表7.1.1

题7.2 以下说法是否正确：
(1) 一个数同时能被3与7整除，它一定能被21整除。
(2)一个数同时能被6与9整除，它一定能被54整除。

定义7.3 $a,b$ 是整数且 $a>0$ ，如果存在整数 $q,r$ ，满足 $0\le r<a$ 且 $b=qa+r$ ，则称 $r$ 为 $b$ 除以 $a$ 的余数，记作 $r=b\%a$ 。其中 $q$ 为商。
根据以上定义，求：
(1) $89188\%17$
(2) $3^{2022}\%10$
(3) $(3^{2022}+2^{2022})\%5$

题7.4 证明：
(1) 3个除以5余3的整数相乘，其积除以5余2。
(2) 一个整数的平方，除以4不能余2。
证明 (1) 设这三个数为 $x,y,z$ ，根据题意，存在 $a,b,c\in \mathbb Z$ ，满足：
$x=5a+3\\ y=5b+3\\ z=5c+3$
所以， $xyz=(5a+3)(5b+3)(5c+3)=(25ab+15a+15b+9)(5c+3)\\ =125abc+75ab+75bc+75ca+45a+45b+45c+27\\ =5(25abc+5ab+5bc+5ca+9a+9b+9c+5)+2$
所以， $xyz\%5=2$
(2) 讨论奇偶性：(a) 如果此数为偶数，它的平方被4除余0；(b)如果此数是奇数，它的平方被4除余1。综上，任意的整数的平方被4除不余2。

题7.6 对于任意的整数 $x$ ，若 $2|x^2$ ，那么 $2|x$ 。
证明以下使用反证法：
假设命题不成立，则 $x$ 是奇数，即存在整数 $k$ ，使 $x=2k+1$ ，所以：
$x^2=(2k+1)^2\\ =4k^2+4k+1\\ =2(2k^2+2k)+1$
可见 $x^2 \%2 =1$ ，与条件矛盾。所以假设不成立，命题成立。 $\blacksquare$

题7.7 $n\in \mathbb Z$ ，证明：
(1) $6|n(n+1)(n+2)$
(2) $n(n+1)(n+2)(n+3)+1$ 是平方数。
证明 (1) $n,n+1,n+2$ 中，必有一个偶数，所以2|n(n+1)(n+2);
$n,n+1,n+2$ 中，必有一个是3的倍数，所以3|n(n+1)(n+2)。
综上， $6|n(n+1)(n+2)$ 。

(2) $n(n+1)(n+2)(n+3)+1=(n^2+3n+1)^2$

评注7.8 题7.7(2)的思路如下：
令 $b_n=n(n+1)(n+2)(n+3)+1=a_n^2$ ，可以验证：
$b_1=5^2\\ b_2=11^2\\ b_3=19^2\\ b_4=29^2\\...$
所以， $a_1=5,a_2=11=a_1+6,a_3=19=a_2+8,...,a_n=a_{n-1}+2(n+1)$ ，所以：
$a_2-a_1=6\\ a_3-a_2=8\\ ...\\$

题7.9 (1) 1000之内，能被3整除的正整数有多少个?
(2) 2022之内的正整数中，既是8的倍数，又是18的正倍数有多少个？
(3) 2022之内的正整数中，3的倍数、8的倍数、18的倍数共有多少个？
解 (1) $\frac{1000}3 = 333....1$ ，所以1000之内，能被3整除的正整数有333个。
(2) $[8,18]=72$ ，且 $2022/72=28...6$ ，所以它们共同的倍数有28个。
(3) 根据容斥原理计算：
$\lfloor2022/3\rfloor+\lfloor2022/8\rfloor+\lfloor2022/18\rfloor-\lfloor2022/[3,8]\rfloor-\lfloor2022/[8,18]\rfloor-\lfloor2022/[18,3]\rfloor+\lfloor2022/[3,8,18]\rfloor\\ =674+252+112-84-28-112+28=842$
所以，满足条件的整数有 $842$ 个。
$\blacksquare$

题7.10 9000的所有因数有_________个，它们的和是___________
解 $9000=2^3\times 3^2\times 5^3$ ，所以，它的因数有 $4\times 3\times 4=48$ 个，其和为 $(1+2+4+8)(1+3+9)(1+5+25+125)=15\times 13\times 156=30420$
$\blacksquare$

定理7.11 整除有如下性质：
(1) $a|b,b|c\rightarrow a|c$
(2) $a|b,a|c\rightarrow\forall m,n\in \mathbb Z,a|(mb+nc)$
解 (1) 由条件得，存在整数 $k_1,k_2$ ，满足 $b=k_1a,c=k_2b$ ，所以 $c=k_1k_2a$ ，所以 $a|c$ 。
(2) 由条件得，存在整数 $k_1,k_2$ ，满足 $b=k_1a,c=k_2a$ ，所以 $mb+nc=mk_1a+nk_2a=(mk_1+nk_2)a\\$
所以 $,a|(mb+nc)$
$\blacksquare$
定义7.12 记 $(a,b)$ 是 $a,b$ 的最大公约数， $[a,b]$ 是 $a,b$ 的最小公倍数。
(30,45)=_____,[30,45]=_____, $(30,45)\times[30,45]$ =_____, $30\times45$ =_____

定义7.13 如果 $a,b$ 的最大公约数是1，那么称 $a,b$ 为互质数。

定理7.14
(1) $(a,b)=d$ ，则自然数 $n$ 是 $a,b$ 的公约数，当且仅当 $n|d$
(2) $[a,b]=m$ ，则自然数 $n$ 是 $a,b$ 的公倍数，当且仅当 $m|n$

定理7.15 $a,b$ 是整数， $(a,b)=d$ 当且仅当 $\left(\frac{a}d,\frac{b}d\right)=1$
证明 (1)先证必要性：假设命题不成立，则设 $\left(\frac{a}d,\frac{b}d\right)=d'>1$ 。则存在 $q_1,q_2\in \mathbb Z$ ，满足 $\frac{a}d=q_1d'\\\frac{b}d=q_2d'$
即得 $a=q_1dd',b=q_2dd'$ ，所以 $(a,b)\ge dd'>d$ 矛盾。所以假设不成立，命题成立。
(2) 再证充分性：假设命题不成立，则存在比 $d$ 大的公约数 $d'=kd$ ，其中 $k\in \mathbb Z,k>1$ 。此时又有 $k_1,k_2\in \mathbb Z$ 满足： $a=k_1d'=k_1kd\\b=k_2d'=k_2kd$
于是： $\left(\frac{a}d,\frac{b}d\right)=(k_1k,k_2k)\ge k>1$ 矛盾。所以假设不成立，命题成立。
$\blacksquare$

定理7.16 $a,b$ 是整数， $[a,b]=m$ 当且仅当 $\left(\frac{m}a,\frac{m}b\right)=1$
证明 (1)先证必要性：假设命题不成立，设 $\left(\frac{m}a,\frac{m}b\right)=d>1\\$
于是存在 $k_1,k_2\in \mathbb Z$ ，满足： $m=k_1da=k_2db$
令 $m'=m/d\in \mathbb Z_+$ ，则 $m'=k_1a=k_2b$ ，即 $m'$ 是 $a,b$ 的公倍数且小于 $m$ ，矛盾。所以假设不成立，命题成立。
(2)再证充分性：假设命题不成立，则令 $[a,b]=m'$ ，则存在 $k\in\mathbb Z,k>1,m=km'$
另 $\exists k_1,k_2\in \mathbb Z,m'=k_1a=k_2b$ ，所以 $m=kk_1a=kk_2b$ ，于是： $\left(\frac{m}a,\frac{m}b\right)=(kk_1,kk_2)\ge k>1\\$ 矛盾。所以假设不成立，命题成立。
$\blacksquare$

定理7.17 $(a,b)[a,b]=ab$
证明设 $(a,b)=d$ ，则存在整数 $k_1,k_2$ ，满足 $a=k_1d\\b=k_2d\\(k_1,k_2)=1$
所以 $\tag{7.17.1}ab=k_1k_2d^2$
另外，令 $m=k_1k_2d$ ，则 $k_1=\frac{m}b,k_2=\frac{m}a$ ，所以 $\left(\frac{m}a,\frac{m}b\right)=(k_1,k_2)=1\\$
根据定理7.16得 $m=[a,b]$ ，再由(7.17.1)得 $(a,b)[a,b]=ab$ 。
$\blacksquare$

推论 $a,b$ 互素， $[a,b]=ab$

题7.18 求以下各数的所有因数：
(1) $468$ 的所有因数：________________________
(2) $37^{3}$ 的所有因数：________________________
(3) $3^2 19^4$ 的所有因数：________________________
(4) $15^2 20^3$ 的所有因数：________________________
解 (3) 因为3,19都是因数，所以 $3^2 19^4$ 的所有因数是下式展开后不合并的各项： $(1+3+3^2 )(1+19+19^2+19^3+19^4)=1+19+19^2+19^3+19^4\\+3+3\times19+3\times19^2+3\times19^3+3\times19^4\\+3^2+3^2\times19+3^2\times19^2+3^2\times19^3+3^2\times19^4$
所以，其因数有： $1,19,19^2,19^3,19^4,\\3,3\times19,3\times19^2,3\times19^3,3\times19^4,\\3^2,3^2\times19,3^2\times19^2,3^2\times19^3,3^2\times19^4$

题7.19 求以下各组数的所有公因数：
(1) $170,68$ 的所有公因数：________________________
(2) $2^3 5^{10},2^{20}5^2$ 的所有公因数：________________________
(3) $2^3 3^4 5^8 20^3,630$ 的所有公因数：________________________

定理7.20 $a,b,c$ 是自然数， $(a,b)=1,a,b\ne 0$ ，且 $a|c,b|c$ ，那么 $ab|c$ .
定理7.21 $a,b,c$ 是自然数， $a,b\ne 0$ ，且 $a|c,b|c$ ，那么 $[a,b]|c$ .

【7】整除性与余数

推荐阅读更多精彩内容