习题 11 · 离散数学

本节对应原书 PDF 第 279–283 页。习题题干逐字取自教材；原解答逐字取自《离散数学习题解答与学习指导（第 3 版）》第 11 章「习题解答与分析」（PDF 第 190–202 页，印刷第 178–190 页）。原解答不进折叠块；仅在确实需要补充答案书跳过的中间步骤时才加折叠块。

11.1 判断下述各命题是否为真。

3 \mid 7,\ 5 \mid -35,\ -7 \mid -21,\ 12 \mid 4,\ 2 \mid 0,\ 0 \mid 2,\ 0 \mid 0

解答　假, 真, 真, 假, 真, 假, 假.

11.2 给出 24 的全部因子。

解答　\pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 8, \pm 12, \pm 24.

11.3 对下述每一对数做带余除法，第一个数是被除数，第二个是除数。

（1）35,4　（2）5,8　（3）12,3　（4）-4,3　（5）-28,7　（6）-6,-4

解答　(1) 35=8\times 4+3. (2) 5=0\times 8+5. (3) 12=4\times 3+0. (4) -4=-2\times 3+2. (5) -28=-4\times 7+0. (6) -6=2\times(-4)+2.

11.4 设 a,b,c,d 均为正整数，下述各命题是否为真？若为真，请给出证明；否则，请给出反例。

（1）若 a \mid c，b \mid c，则 ab \mid c。

（2）若 a \mid c，b \mid d，则 ab \mid cd。

（3）若 ab \mid c，则 a \mid c。

（4）若 a \mid bc，则 a \mid b 或 a \mid c。

解答　(1) 假. 反例: 4\mid 12, 6\mid 12, 但 4\times 6\nmid 12. (2) 真. 证明: 由题设, 存在整数 k_1, k_2, 使得 c=k_1a, d=k_2b, 从而有 cd=k_1k_2ab, 得证 ab\mid cd. (3) 真. 证明: 存在整数 k, 使得 c=k(ab)=(kb)a, 得证 a\mid c. (4) 假. 反例: 4\mid 2\times 6, 但 4\nmid 2, 4\nmid 6.

11.5 给出下述正整数的素因子分解。

126，256，1092，6325，20!

解答　126=2\times 3^2\times 7, 256=2^8, 1092=2^2\times 3\times 7\times 13, 6325=5^2\times 11\times 23, 20!=2\times 3\times 2^2\times 5\times(2\times 3)\times 7\times 2^3\times 3^2\times(2\times 5)\times 11\times(2^2\times 3)\times 13 \quad\times(2\times 7)\times(3\times 5)\times 2^4\times 17\times(2\times 3^2)\times 19\times(2^2\times 5) =2^{18}\times 3^{8}\times 5^{4}\times 7^{2}\times 11\times 13\times 17\times 19

11.6 判断下述正整数是素数，还是合数。

113，221，527，2^{13}-1

解答　提示: 根据主教材中的定理 11.4 的推论, 为了判断正整数 n(n>1) 是素数还是合数, 只需检查所有小于等于 \sqrt{n} 的素数是否整除 n. 解: \sqrt{113}<11, 2, 3, 5, 7 都不能整除 113, 故 113 是素数. \sqrt{221}<15, 2, 3, 5, 7, 11 不能整除 221, 但 221=13\times 17, 故 221 是合数. \sqrt{527}<23, 2, 3, 5, 7, 11, 13 不能整除 527, 但 527=17\times 31, 故 527 是合数. 2^{13}-1=8191, \sqrt{8191}<91, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 都不能整除 8191, 故 8191 是素数.

11.7 设计用埃拉托斯特尼筛法求正整数 N 以内的所有素数的算法。

解答　Sieve(n,P). 输入: 正整数 n. 输出: 小于等于 n 的所有素数 P. ① if n=1 then P\leftarrow\varnothing, 计算结束; ② P\leftarrow\{2\}; ③ a\leftarrow 2; ④ if n=a then 计算结束; ⑤ b\leftarrow\min\{a^2,n\}; ⑥ Q\leftarrow\{x\mid a<x\leqslant b\}; ⑦ for P 中的每一个 x ⑧ \quad for Q 中的每一个 y ⑨ \quad\quad if x\lfloor y/x\rfloor=y then 从 Q 中删去 y; ⑩ P\leftarrow P\cup Q; ⑪ a\leftarrow b; ⑫ 转④.

11.8 证明：对任意的整数 n，

（1）6 \mid n(n+1)(n+2)。

（2）\frac{1}{5}n^5+\frac{1}{3}n^3+\frac{7}{15}n 是整数。

解答　(1) 6\mid n(n+1)(n+2)\Leftrightarrow 2\mid n(n+1)(n+2)\wedge 3\mid n(n+1)(n+2). n 与 n+1 中有一个被 2 整除, 故 2\mid n(n+1)(n+2). 再设 n=3k+i, i=0,1,2. 若 i=0, 则 3\mid n; 若 i=1, 则 3\mid n+2; 若 i=2, 则 3\mid n+1. 总有 3\mid n(n+1)(n+2). 证毕. (2) 要证 15\mid 3n^5+5n^3+7n. 为此只需证 3\mid 5n^3+7n 且 5\mid 3n^5+7n. 证 3\mid 5n^3+7n. 注意到 5n^3+7n 是奇函数, 只需证对非负整数 n 成立. 用归纳法. 当 n=0 时, 3\mid 0, 结论成立. 假设当 n=k(k\geqslant 0) 时结论成立, 则

5(k+1)^3+7(k+1)=(5k^3+7k)+3(5k^2+5k+4)

由归纳假设, 3\mid 5k^3+7k, 故有 3\mid 5(k+1)^3+7(k+1), 即当 n=k+1 时结论也成立. 类似可证 5\mid 3n^5+7n.

11.9 证明：对任意的整数 n>1，1+\frac{1}{2}+\cdots+\frac{1}{n} 不是整数。

解答　设 n!=2^m h, h 是奇数, 又设 2^k\leqslant n<2^{k+1}, k\geqslant 1. 假若 1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}=1+\dfrac{1}{n!}\sum_{a=2}^{n}\dfrac{n!}{a} 是整数, 则 n!\mid\sum_{a=2}^{n}\dfrac{n!}{a}. 当然有 2^k\mid\sum_{a=2}^{n}\dfrac{n!}{a}, 更有 2^{k+1}\mid\sum_{a=2}^{n}\dfrac{n!}{a}. 对所有的 2\leqslant a\leqslant n 且 a\neq 2^k, a=2^i s, s 是奇数, i<k. 于是, \dfrac{1}{a}=2^{-i}t, t 是奇数, 从而 2^{k+1}\mid\dfrac{n!}{a}. 但是, 对 a=2^k, \dfrac{n!}{a}=2^m h 不能被 2^{k+1} 整除, 矛盾, 故 1+\dfrac{1}{2}+\cdots+\dfrac{1}{n} 不是整数.

11.10 （1）设全体素数从小到大顺序排列为：p_1 = 2，p_2 = 3，p_3，p_4，\cdots。试证明：

p_n \leqslant 2^{2^{n-1}} \quad n = 1,2,\cdots

（2）证明：\pi(x)>\log_2\log_2 x，x \geqslant 2。

解答　(1) 用归纳法. 当 n=1 时, p_1=2^0, 结论成立. 假设对 n(n\geqslant 1) 结论成立. 由主教材中定理 11.2 的证明和归纳假设, 得

p_{n+1}\leqslant p_1p_2\cdots p_n+1\leqslant 2^{2^0}2^{2^1}\cdots 2^{2^{n-1}}+1=2^{2^n-1}+1<2^{2^n}

得证, 对 n+1 结论也成立. (2) 由 (1) \log_2\log_2 p_{n+1}\leqslant n. 设 \pi(x)=n, 则 x<p_{n+1}. 于是

n\geqslant\log_2\log_2 p_{n+1}>\log_2\log_2 x

解读：这里的关键是用「前 n 个素数之积再加 1」造出一个不被它们中任何一个整除的数，从而拿到第 n+1 个素数的上界；指数 2^{2^0}\cdots 2^{2^{n-1}} 相加正好是 2^n-1，比目标 2^{2^n} 小一点，估计因此闭合。

11.11 如果整系数代数方程 a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n = 0 有非零整数解 u，则 u \mid a_n。

解答　设 a_0u^n+a_1u^{n-1}+\cdots+a_{n-1}u+a_n=0 且 u\neq 0, 由 a_n=-(a_0u^{n-1}+a_1u^{n-2}+\cdots+a_{n-1}), 即可得到 u\mid a_n.

11.12 下述方程是否有整数解？若有整数解，试求出所有的整数解。

（1）x^2-x+1 = 0。

（2）x^4+x^2-4x-4 = 0。

（3）x^4+5x^3-2x^2+7x+2 = 0。

（4）2x^4+5x^3+9x = 0。

解答　分析: 0 是方程 a_0x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n=0 的解当且仅当 a_n=0. 当 a_n\neq 0 时, 由上题, 只需检查 a_n 的因子是否是方程的解. (1) x^5-x+1=0. 1 有 2 个因子 1 和 -1, 经检查它们都不是方程的解, 故方程无整数解.

解读（原书此处疑似笔误）：题干（教材 11.12）印的是 x^2-x+1=0，答案册此处印成 x^5-x+1=0。两者都无整数解（1 的因子 \pm 1 均不满足），结论一致，此处照抄答案册原文。

(2) x^3+x^2-4x-4=0. -4 的因子为 \pm1, \pm2, \pm4, 经检查, -1, 2, -2 是方程的解.

解读（原书此处疑似笔误）：题干印的是 x^4+x^2-4x-4=0（4 次），答案册此处印成 x^3+x^2-4x-4=0（3 次）。答案给出的 -1,2,-2 恰是 3 次版本的三根，故答案与它所印的方程自洽，此处照抄答案册原文。

(3) x^4+5x^3-2x^2+7x+2=0. 2 的因子为 \pm1, \pm2. 经检查它们都不是方程的解, 故方程无整数解. (4) 2x^4+5x^3+9x=0. 0 是方程的解. 再考虑方程 2x^3+5x^2+9=0, 9 的因子为 \pm1, \pm3, \pm9, 经检查, -3 是解. 故原方程有整数解 0 和 -3.

11.13 利用素因子分解，求下述每一对数的最大公约数和最小公倍数。

（1）175,140　（2）72,108　（3）315,2200

解答　(1) 175=5^2\times 7, 140=2^2\times 5\times 7. \gcd(175,140)=5\times 7=35, \mathrm{lcm}(175,140)=2^2\times 5^2\times 7=700. (2) 72=2^3\times 3^2, 108=2^2\times 3^3. \gcd(72,108)=2^2\times 3^2=36, \mathrm{lcm}(72,108)=2^3\times 3^3=216. (3) 315=3^2\times 5\times 7, 2200=2^3\times 5^2\times 11. \gcd(315,2200)=5, \mathrm{lcm}(315,2200)=2^3\times 3^2\times 5^2\times 7\times 11=138\,600.

11.14 求满足 \gcd(a,b) = 10 且 \mathrm{lcm}(a,b) = 100 的所有正整数对 a,b。

解答　解法1 \gcd(a,b)=2\times 5, \mathrm{lcm}(a,b)=2^2\times 5^2. 设 a=2^{i_1}\times 5^{j_1}, b=2^{i_2}\times 5^{j_2}, 则有

\min(i_1,i_2)=1,\quad \max(i_1,i_2)=2,\quad \min(j_1,j_2)=1,\quad \max(j_1,j_2)=2.

有下述 4 种可能: ① i_1=1,i_2=2,j_1=1,j_2=2,a=10,b=100. ② i_1=1,i_2=2,j_1=2,j_2=1,a=50,b=20. ③ i_1=2,i_2=1,j_1=1,j_2=2,a=20,b=50. ④ i_1=2,i_2=1,j_1=2,j_2=1,a=100,b=10. 解法2 可以证明 (见题 11.20 和题 11.21): 设 d=\gcd(a,b),m=\mathrm{lcm}(a,b), 则 a=da_1,b=db_1,m=da_1b_1, 其中 a_1 与 b_1 互素. 本题 a=10a_1,b=10b_1,100=10a_1b_1, 即 a_1b_1=10, 且 a_1 与 b_1 互素. 有下述 4 种可能: ① a_1=1,b_1=10,a=10,b=100. ② a_1=10,b_1=1,a=100,b=10. ③ a_1=2,b_1=5,a=20,b=50. ④ a_1=5,b_1=2,a=50,b=20.

11.15 设 p 是素数，a 是整数，则当 p \mid a 时，\gcd(p,a) = p；当 p \nmid a 时，\gcd(p,a) = 1。

解答　当 p\mid a 时, 结论显然成立. 当 p\nmid a 时, 记 d=\gcd(p,a), d\mid p, 根据素数的定义, d=1 或 d=p, 而 p\nmid a, 故 d=1.

11.16 对任意的整数 x,y,u,v，有 \gcd(a,b) \leqslant \gcd(xa+yb,ua+vb)。

解答　记 d=\gcd(a,b), 有 d\mid a 且 d\mid b. 由性质 11.1.1 (见主教材 286 页), d\mid xa+yb 且 d\mid ua+vb, 即 d 是 xa+yb 和 ua+vb 的公因子, 故必有 d\leqslant\gcd(xa+yb,ua+vb).

11.17 用辗转相除法求下述每一对数的最大公约数。

（1）85,125　（2）231,72　（3）45,56　（4）154,64

解答　(1) 125=85+40, 85=2\times 40+5, 40=8\times 5, \gcd(125,85)=5. (2) 231=3\times 72+15, 72=4\times 15+12, 15=1\times 12+3, 12=4\times 3, \gcd(231,72)=3. (3) 56=1\times 45+11, 45=4\times 11+1, 11=11\times 1, \gcd(45,56)=1. (4) 154=2\times 64+26, 64=2\times 26+12, 26=2\times 12+2, 12=6\times 2, \gcd(154,64)=2.

11.18 下述每一对数 a,b 是否互素？若互素，试给出整数 x 和 y 使 xa+yb = 1。

（1）24,35　（2）63,91　（3）450,539　（4）1024,729

解答　用辗转相除法. (1) 35=1\times 24+11, 24=2\times 11+2, 11=5\times 2+1, \gcd(24,35)=1, 故 35 与 24 互素.

\begin{aligned} 1 &= 11-5\times 2=11-5\times(24-2\times 11)=-5\times 24+11\times 11 \\ &= -5\times 24+11\times(35-24) \end{aligned}

得 -16\times 24+11\times 35=1. (2) 91=63+28, 63=2\times 28+7, 28=4\times 7, \gcd(63,91)=7, 故 63 与 91 不互素. (3) 539=450+89, 450=5\times 89+5, 89=17\times 5+4, 5=4+1, 450 与 539 互素.

\begin{aligned} 1 &= 5-4=5-(89-17\times 5)=18\times 5-89=18\times(450-5\times 89)-89 \\ &= 18\times 450-91\times 89=18\times 450-91\times(539-450) \end{aligned}

得 109\times 450-91\times 539=1. (4) 1024=729+295, 729=2\times 295+139, 295=2\times 139+17, 139=8\times 17+3, 17=5\times 3+2, 3=2+1, 1024 与 729 互素.

\begin{aligned} 1 &= 3-2=3-(17-5\times 3)=6\times 3-17=6\times(139-8\times 17)-17 \\ &= 6\times 139-49\times 17=6\times 139-49\times(295-2\times 139) \\ &= 104\times 139-49\times 295=104\times(729-2\times 295)-49\times 295 \\ &= 104\times 729-257\times 295=104\times 729-257\times(1024-729) \end{aligned}

得 -257\times 1024+361\times 729=1.

11.19 求下述每一对数的最大公约数，其中 n 是整数，k 是正整数。

（1）2n-1,2n+1　（2）2n,2(n+1)　（3）kn,k(n+2)

解答　(1) 2n+1=(2n-1)+2, \gcd(2n+1,2n-1)=\gcd(2n-1,2)=1. (2) 由 \gcd(n,n+1)=1, 得 \gcd(2n,2(n+1))=2. (3) \gcd(n,n+2)=\gcd(n,2)=\begin{cases}1 & n\text{ 为奇数} \\ 2 & n\text{ 为偶数}\end{cases} 得

\gcd(kn,k(n+2))=\begin{cases}k & n\text{ 为奇数} \\ 2k & n\text{ 为偶数}\end{cases}

11.20 设 a,b 是两个不为 0 的整数，d 为正整数，则 d = \gcd(a,b) 当且仅当存在整数 x 和 y 使 a = dx，b = dy 且 x 与 y 互素。

解答　必要性: 设 a=dx,b=dy. 根据主教材中的定理 11.7, 存在整数 u、v 使得 ua+vb=d, 即 udx+vdy=d. 因为 d>0, 可消去 d 得 ux+vy=1. 由定理 11.7, 得证 x 与 y 互素. 充分性: 记 d'=\gcd(a,b), 因为 d 是 a 和 b 的公因子, 故有 d\mid d'. 设 d'=kd, 有 kd\mid dx 且 kd\mid dy, 得 k\mid x 且 k\mid y. 而 x 与 y 互素, 必有 k=1, 得证 d=\gcd(a,b).

11.21 证明：对任意的正整数 a 和 b，ab = \gcd(a,b)\mathrm{lcm}(a,b)。

解答　记 d=\gcd(a,b), 由上题, a=dx,b=dy, x 与 y 互素. 于是, \mathrm{lcm}(a,b)=\mathrm{lcm}(dx,dy)=d\cdot\mathrm{lcm}(x,y)=dxy, 得证 \gcd(a,b)\cdot\mathrm{lcm}(a,b)=d\cdot dxy=ab.

11.22 证明：如果 a \mid bc，且 a,b 互素，则 a \mid c。

解答　设 bc=ka, 由 a,b 互素, 根据主教材中的定理 11.8, 存在整数 x,y 使得 xa+yb=1. 于是, c=xac+ybc=xac+yka=(xc+yk)a, 得证 a\mid c.

11.23 设 a,b 互素，证明：

（1）对任意的整数 m，\gcd(m,ab) = \gcd(m,a)\gcd(m,b)。

（2）当 d>0 时，d \mid ab 当且仅当存在正整数 d_1,d_2 使 d = d_1d_2，d_1 \mid a，d_2 \mid b，并且 d 的这种表示是唯一的。

解答　(1) 设 d_1=\gcd(m,a),d_2=\gcd(m,b). 因为 a 与 b 互素, d_1 与 d_2 也互素. 又设 m=d_1m_1, 根据上题, 由 d_2\mid d_1m_1 且 d_1 与 d_2 也互素, 推得 d_2\mid m_1, 从而 d_1d_2\mid m, 故 d_1d_2 是 m 和 ab 的公因子. 设 d=\gcd(m,ab),d=kd_1d_2,k\geqslant 1. 由 d_2\mid b 和 a 与 b 互素, d_2 也与 a 互素, 从而由 kd_1d_2\mid ab, 可推得 kd_1\mid a. 于是, kd_1 是 m 和 a 的公因子, 故 k=1. 得证 d=d_1d_2. (2) 充分性显然. 必要性: 设 d\mid ab, 取 d_1=\gcd(d,a),d_2=\gcd(d,b), 自然有 d_1\mid a,d_2\mid b. 由 d\mid ab, 有 \gcd(d,ab)=d. 根据 (1), d=\gcd(d,a)\gcd(d,b)=d_1d_2. 下面证明唯一性. 设正整数 c_1,c_2, 使得 d=c_1c_2 且 c_1\mid a,c_2\mid b, 由于 c_1 是 d 和 a 的公因子, 必有 c_1\leqslant d_1. 同理, c_2\leqslant d_2. 得 d=c_1c_2\leqslant d_1d_2=d, 得证 c_1=d_1,c_2=d_2.

解读：a,b 互素这一条是整题的支点——它保证 d_1=\gcd(m,a) 与 d_2=\gcd(m,b) 互素，于是两者的乘积才是 m 的因子；去掉互素条件，\gcd(m,ab) 就会大于 \gcd(m,a)\gcd(m,b)。

11.24 设 a,b 是整数，证明：11 \mid a^2+5b^2 当且仅当 11 \mid a 且 11 \mid b。

解答　充分性显然. 必要性: 0^2\equiv 0(\bmod\ 11), 1^2\equiv 1^2\equiv 1(\bmod\ 11), 2^2\equiv 9^2\equiv 4(\bmod\ 11), 3^2\equiv 8^2\equiv 9(\bmod\ 11), 4^2\equiv 7^2\equiv 5(\bmod\ 11), 5^2\equiv 6^2\equiv 3(\bmod\ 11), 从而

a^2\equiv 0,1,3,4,5,9(\bmod\ 11),\quad 5b^2\equiv 0,5,4,9,3,1(\bmod\ 11)

不难验证: 只有当 a^2\equiv 5b^2\equiv 0(\bmod\ 11) 时, 有 a^2+5b^2\equiv 0(\bmod\ 11). 得证 a\equiv b\equiv 0(\bmod\ 11).

11.25 下述命题是否为真。

（1）758 \equiv 246(\bmod\ 18)　（2）365 \equiv -3(\bmod\ 7)

（3）-29 \equiv 1(\bmod\ 5)　（4）352 \equiv 0(\bmod\ 11)

解答　(1) 假. (2) 假. (3) 真. (4) 真.

11.26 给出使下述同余式成立且大于 1 的正整数 m。

（1）35 \equiv 14(\bmod\ m)　（2）10 \equiv -1(\bmod\ m)

（3）-7 \equiv 21(\bmod\ m)　（4）37^2 \equiv 30^2(\bmod\ m)

（5）8 \equiv 2(\bmod\ m) 且 7 \equiv -2(\bmod\ m)

解答　(1) 35\equiv 14(\bmod\ m), m\mid 35-14, 即 m\mid 21, 故 m=3,7,21. (2) 10\equiv-1(\bmod\ m), m\mid 10+1, 即 m\mid 11, 故 m=11. (3) -7\equiv 21(\bmod\ m), m\mid-7-21, 即 m\mid-28, 故 m=2,4,7,14,28. (4) 37^2\equiv 30^2(\bmod\ m), m\mid 37^2-30^2, 即 m\mid 67\times 7, 故 m=7,67,469. (5) 8\equiv 2(\bmod\ m) 且 7\equiv-2(\bmod\ m), m\mid 6 且 m\mid 9, 6 和 9 大于 1 的公因子为 3, 故 m=3.

11.27 写出 \mathbf{Z}_7 的全部元素以及 \mathbf{Z}_7 上的加法表和乘法表。

解答

\begin{array}{c|ccccccc} + & [0] & [1] & [2] & [3] & [4] & [5] & [6] \\ \hline {[0]} & [0] & [1] & [2] & [3] & [4] & [5] & [6] \\ {[1]} & [1] & [2] & [3] & [4] & [5] & [6] & [0] \\ {[2]} & [2] & [3] & [4] & [5] & [6] & [0] & [1] \\ {[3]} & [3] & [4] & [5] & [6] & [0] & [1] & [2] \\ {[4]} & [4] & [5] & [6] & [0] & [1] & [2] & [3] \\ {[5]} & [5] & [6] & [0] & [1] & [2] & [3] & [4] \\ {[6]} & [6] & [0] & [1] & [2] & [3] & [4] & [5] \end{array}

\begin{array}{c|ccccccc} \times & [0] & [1] & [2] & [3] & [4] & [5] & [6] \\ \hline {[0]} & [0] & [0] & [0] & [0] & [0] & [0] & [0] \\ {[1]} & [0] & [1] & [2] & [3] & [4] & [5] & [6] \\ {[2]} & [0] & [2] & [4] & [6] & [1] & [3] & [5] \\ {[3]} & [0] & [3] & [6] & [2] & [5] & [1] & [4] \\ {[4]} & [0] & [4] & [1] & [5] & [2] & [6] & [3] \\ {[5]} & [0] & [5] & [3] & [1] & [6] & [4] & [2] \\ {[6]} & [0] & [6] & [5] & [4] & [3] & [2] & [1] \end{array}

11.28 写出 \mathbf{Z}_8 的全部元素以及 \mathbf{Z}_8 上的加法表和乘法表。

解答

\begin{array}{c|cccccc} + & [0] & [1] & [2] & [3] & [4] & [5] \\ \hline {[0]} & [0] & [1] & [2] & [3] & [4] & [5] \\ {[1]} & [1] & [2] & [3] & [4] & [5] & [0] \\ {[2]} & [2] & [3] & [4] & [5] & [0] & [1] \\ {[3]} & [3] & [4] & [5] & [0] & [1] & [2] \\ {[4]} & [4] & [5] & [0] & [1] & [2] & [3] \\ {[5]} & [5] & [0] & [1] & [2] & [3] & [4] \end{array}

\begin{array}{c|cccccc} \times & [0] & [1] & [2] & [3] & [4] & [5] \\ \hline {[0]} & [0] & [0] & [0] & [0] & [0] & [0] \\ {[1]} & [0] & [1] & [2] & [3] & [4] & [5] \\ {[2]} & [0] & [2] & [4] & [0] & [2] & [4] \\ {[3]} & [0] & [3] & [0] & [3] & [0] & [3] \\ {[4]} & [0] & [4] & [2] & [0] & [4] & [2] \\ {[5]} & [0] & [5] & [4] & [3] & [2] & [1] \end{array}

11.29 利用例 11.8 中给出的计算公式，计算珍珠港日 1941 年 12 月 7 日是星期几。

解答　Y=1941,C=19,X=41,M=10,d=7. w\equiv 41+\lfloor 41/4\rfloor+\lfloor 19/4\rfloor-2\times 19+2\times 10+\lfloor(10+\lfloor 10/7\rfloor)/2\rfloor+\lfloor 10/12\rfloor+7 \quad\equiv 41+10+4-38+20+5+0+7\equiv 0(\bmod\ 7) 珍珠港日是星期日.

11.30 验证 M 月 1 号的星期数与当年 3 月 1 日的星期数 w_Y 之差为 \lfloor (13M-11)/5 \rfloor (\bmod\ 7)。从而得到 y 年 m 月 d 日星期数的另一个更简便一点的计算公式

w \equiv 2-2C+X+\lfloor X/4 \rfloor+\lceil C/4 \rceil+\lfloor (13M-11)/5 \rfloor+d(\bmod\ 7)

其中，M = (m-3)\bmod 12+1，Y = y-\lfloor M/11 \rfloor = 100C+X。

解答　由 30 mod 7=2, 星期数每个月加 2, 大月再多加 1.

\begin{array}{c|cccccccccccc} m & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 1 & 2 \\ \hline M & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline \text{应加的星期数} & 0 & 3 & 5 & 8 & 10 & 13 & 16 & 18 & 21 & 23 & 26 & 29 \\ \hline \lfloor(13M-11)/5\rfloor & 0 & 3 & 5 & 8 & 10 & 13 & 16 & 18 & 21 & 23 & 26 & 29 \end{array}

11.31 证明同余关系是等价关系，即同余关系具有

（1）自反性。a \equiv a(\bmod\ m)。

（2）传递性。a \equiv b(\bmod\ m)，b \equiv c(\bmod\ m) \Rightarrow a \equiv c(\bmod\ m)。

（3）对称性。a \equiv b(\bmod\ m) \Rightarrow b \equiv a(\bmod\ m)。

解答　(1) 自反性. 因为 m\mid a-a, 故 a\equiv a(\bmod\ m). (2) 传递性. 设 a\equiv b(\bmod\ m), b\equiv c(\bmod\ m), 有 m\mid a-b, m\mid b-c. 而 a-c=(a-b)+(b-c), 故 m\mid a-c. 得证 a\equiv c(\bmod\ m). (3) 对称性. 设 a\equiv b(\bmod\ m), 有 m\mid a-b, 自然又有 m\mid b-a, 故 b\equiv a(\bmod\ m).

11.32 模算术运算。设 a \equiv b(\bmod\ m)，c \equiv d(\bmod\ m)，则 a \pm c \equiv b \pm d(\bmod\ m)，ac \equiv bd(\bmod\ m)。

解答　设 a\equiv b(\bmod\ m), c\equiv d(\bmod\ m), 有 m\mid a-b, m\mid c-d. 而 (a+c)-(b+d)=(a-b)+(c-d), 故 m\mid(a+c)-(b+d). 得证 a+c\equiv b+d(\bmod\ m). 类似可证 a-c\equiv b-d(\bmod\ m). 由 a\equiv b(\bmod\ m), c\equiv d(\bmod\ m), 存在整数 x、y, 使得 a=xm+b, c=ym+d. 于是, ac=(xym+xd+yb)m+bd, 故有 ac\equiv bd(\bmod\ m).

11.33 证明：（1）设 d \geqslant 1，d \mid m，则 a \equiv b(\bmod\ m) \Rightarrow a \equiv b(\bmod\ d)。

（2）设 d \geqslant 1，则 a \equiv b(\bmod\ m) \Leftrightarrow da \equiv db(\bmod\ dm)。

（3）设 c 与 m 互素，则 a \equiv b(\bmod\ m) \Leftrightarrow ca \equiv cb(\bmod\ m)。

解答　(1) 设 a\equiv b(\bmod\ m), 有 m\mid a-b. 又已知 d\mid m, 由性质 11.1.2 (见主教材 286 页), 得 d\mid a-b. 故有 a\equiv b(\bmod\ d). (2) 因为 d\neq 0, 根据性质 11.1.3 (见主教材 287 页), m\mid a-b\Leftrightarrow dm\mid d(a-b), 从而 a\equiv b(\bmod\ m)\Leftrightarrow da\equiv db(\bmod\ dm). (3) 由 m\mid a-b\Rightarrow m\mid ca-cb, 有 a\equiv b(\bmod\ m)\Rightarrow ca\equiv cb(\bmod\ m). 反之, 设 ca\equiv cb(\bmod\ m), 有 m\mid ca-cb. 已知 c 与 m 互素, 由题 11.22, 必有 m\mid a-b, 得证 a\equiv b(\bmod\ m).

11.34 下述命题是否为真？若为真，试证明之。若为假，试给出反例。

（1）若 a^2 \equiv b^2(\bmod\ m)，则 a \equiv b(\bmod\ m) 或 a \equiv -b(\bmod\ m)。

（2）若 a \equiv b(\bmod\ m)，则 a^2 \equiv b^2(\bmod\ m)。

（3）若 a^2 \equiv b^2(\bmod\ m^2)，则 a \equiv b(\bmod\ m)。

（4）若 a \equiv b(\bmod\ mn)，则 a \equiv b(\bmod\ m) 且 a \equiv b(\bmod\ n)。

（5）若 a \equiv b(\bmod\ m) 且 a \equiv b(\bmod\ n)，则 a \equiv b(\bmod\ mn)。

解答　(1) 假. 反例: 4^2\equiv 2^2(\bmod\ 4), 但 4\not\equiv 2(\bmod\ 4), 4\not\equiv-2(\bmod\ 4). 分析: a^2\equiv b^2(\bmod\ m)\Leftrightarrow m\mid a^2-b^2\Leftrightarrow m\mid(a+b)(a-b), 不一定有 m\mid a-b 或 m\mid a+b. (2) 真. 由模乘运算 (题 11.32) 立即可得. (3) 假. 反例: 5^2\equiv 3^2(\bmod\ 4^2), 但 5\not\equiv 3(\bmod\ 4). (4) 真. 由上题 (1) 立即可得. (5) 假. 反例: 12\equiv 0(\bmod\ 4), 12\equiv 0(\bmod\ 6), 但 12\not\equiv 0(\bmod\ 4\times 6).

解读：五个小题的分水岭在于模数能否拆开：m\mid(a+b)(a-b) 时 (a+b) 与 (a-b) 的因子可以「各分一半」给 m，所以 (1) 不成立；而 m 与 n 不互素时，a\equiv b 在两个模下成立也推不出在乘积模下成立，(5) 因此为假。

11.35 下述一次同余方程是否有解？若有解，试给出它的全部解。

（1）9x \equiv 3(\bmod\ 6)。

（2）4x \equiv 3(\bmod\ 6)。

（3）3x \equiv -1(\bmod\ 5)。

（4）8x \equiv 2(\bmod\ 4)。

（5）20x \equiv 12(\bmod\ 8)。

解答　提示: ax\equiv c(\bmod\ m) 有解的充分必要条件是 \gcd(a,m)\mid c. 设 x_0 是方程的解, 则所有与 x_0 模 m 同余的数都是方程的解, 从而只需对模 m 的每一个等价类取一个代表, 验证是否使方程成立, 就能找到方程的所有解. (1) 9x\equiv 3(\bmod\ 6). \gcd(9,6)=3,3\mid 3, 方程有解. 检查 0,\pm 1,\pm 2,3 是否是方程的解, 得 x\equiv\pm 1,3\equiv 1,3,5(\bmod\ 6). (2) 4x\equiv 3(\bmod\ 6). \gcd(4,6)=2,2\nmid 3, 方程无解. (3) 3x\equiv-1(\bmod\ 5). \gcd(3,5)=1,1\mid-1, 方程有解. 检查 0,\pm 1,\pm 2 是否是方程的解, 得 x\equiv-2\equiv 3(\bmod\ 5). (4) 8x\equiv 2(\bmod\ 4). \gcd(8,4)=4,4\nmid 2, 方程无解. (5) 20x\equiv 12(\bmod\ 8). \gcd(20,8)=4,4\mid 12, 方程有解. 检查 0,\pm 1,\pm 2,\pm 3,4 是否是方程的解, 得 x\equiv\pm 1,\pm 3\equiv 1,3,5,7(\bmod\ 8).

11.36 对下述每一组 a,b,m，验证 b 是 a 的模 m 逆。

（1）5,3,7　（2）8,7,11　（3）11,11,12　（4）6,11,13

解答　(1) 5\times 3-1=14,7\mid 14, 故 5\times 3\equiv 1(\bmod\ 7), 得 5^{-1}\equiv 3(\bmod\ 7). (2) 8\times 7-1=55,11\mid 55, 故 8\times 7\equiv 1(\bmod\ 11), 得 8^{-1}\equiv 7(\bmod\ 7).

解读（原书此处疑似笔误）：上一步已证 8\times 7\equiv 1(\bmod\ 11)，模数应为 11，答案册此处印成 \bmod\ 7。照抄原文。

(3) 11\times 11-1=120,12\mid 120, 故 11\times 11\equiv 1(\bmod\ 12), 得 11^{-1}\equiv 11(\bmod\ 12). (4) 6\times 11-1=65,13\mid 65, 故 6\times 11\equiv 1(\bmod\ 13), 得 6^{-1}\equiv 11(\bmod\ 13).

11.37 对下述每一对数 a 和 m，是否有 a 的模 m 逆？若有，试给出。

（1）2,3　（2）8,12　（3）18,7　（4）12,21　（5）-1,9

解答　提示: a 的模 m 逆存在当且仅当 a 与 m 互素. 当 a 与 m 互素时, 求 a^{-1} 的一般做法是, 先用辗转相除法, 再通过回代求得整数 x 和 y, 使得 xa+ym=1, 则 a^{-1}\equiv x(\bmod m)。当数值比较小时可通过观察直接求得。

（1）2 与 3 互素，故 2 的模 3 逆存在。由 2\times2\equiv1(\bmod 3)，得 2^{-1}\equiv2(\bmod 3)。

（2）8 与 12 不互素，故 8 的模 12 逆不存在。

（3）18 与 7 互素，故 18 的模 7 逆存在。解法 1 用辗转相除法 18=2\times7+4,7=4+3,4=3+1。回代 1=4-3=4-(7-4)=-7+2\times4=-7+2\times(18-2\times7)=2\times18-5\times7，得 18^{-1}\equiv2(\bmod 7)。

解法 2 18\equiv4(\bmod 7),2\times4\equiv1(\bmod 7)，得 18^{-1}\equiv2(\bmod 7)。

（4）12 与 21 不互素，故 12 的模 21 逆不存在。

（5）-1 与 9 互素，故 -1 的模 9 逆存在。由 (-1)^2\equiv1(\bmod 9)，得 (-1)^{-1}\equiv-1\equiv8(\bmod 9)。

11.38 解下述一次同余方程组。

（1）x \equiv 1(\bmod\ 3)，

x \equiv 2(\bmod\ 4)，

x \equiv 3(\bmod\ 5)。

（2）x \equiv 1(\bmod\ 3)，

x \equiv -1(\bmod\ 5)，

x \equiv 2(\bmod\ 7)，

x \equiv -2(\bmod\ 11)。

（3）3x \equiv 1(\bmod\ 5)，

4x \equiv 3(\bmod\ 11)。

解答　提示：中国剩余定理的证明（见主教材中定理 11.11 证明）是构造性的，给出了一次同余方程组的求解方法。设 m_1,m_2,\cdots,m_k 两两互素，一次同余方程组

\begin{aligned} &x\equiv a_1(\bmod m_1)\\ &x\equiv a_2(\bmod m_2)\\ &\quad\vdots\\ &x\equiv a_k(\bmod m_k) \end{aligned}

的求解步骤如下： ① 计算 m=m_1m_2\cdots m_k； ② 计算 M_i=m/m_i 及 M_i 的模 m_i 逆 M_i^{-1},i=1,2,\cdots,k； ③ 方程组的解为 x\equiv a_1M_1^{-1}M_1+a_2M_2^{-1}M_2+\cdots+a_kM_k^{-1}M_k(\bmod m)。

（1）m_1=3,m_2=4,m_3=5 两两互素，m=3\times4\times5=60。 M_1=4\times5=20， M_1\equiv2(\bmod 3)， M_1^{-1}=2 M_2=3\times5=15， M_2\equiv3(\bmod 4)， M_2^{-1}=3 M_3=3\times4=12， M_3\equiv2(\bmod 5)， M_3^{-1}=3 得 x\equiv1\times20\times2+2\times15\times3+3\times12\times3\equiv-2(\bmod 60)。

（2）m_1=3,m_2=5,m_3=7,m_4=11 两两互素，m=3\times5\times7\times11=1155。 M_1=5\times7\times11=385，M_1\equiv(-1)\times1\times(-1)\equiv1(\bmod 3)，M_1^{-1}=1 M_2=3\times7\times11=231，M_2\equiv(-2)\times2\times1\equiv-4\equiv1(\bmod 5)，M_2^{-1}=1 M_3=3\times5\times11=165，M_3\equiv3\times(-2)\times(-3)\equiv4(\bmod 7)，M_3^{-1}=2 M_4=3\times5\times7=105，M_4\equiv6(\bmod 11)，M_4^{-1}=2 得 x\equiv1\times385\times1-1\times231\times1+2\times165\times2-2\times105\times2\equiv394(\bmod 1155)。

（3）先将方程组化成中国剩余定理中的标准形式。3^{-1}\equiv2(\bmod 5),4^{-1}\equiv3(\bmod 11)，方程两边分别乘这 2 个数，得

\begin{aligned} &x\equiv2(\bmod 5)\\ &x\equiv9(\bmod 11) \end{aligned}

m_1=5,m_2=11 互素，m=5\times11=55。M_1=11,M_1\equiv1(\bmod 5),M_1^{-1}=1；M_2=5， M_2^{-1}=9。得

x\equiv2\times11\times1+9\times5\times9\equiv42(\bmod 55)

11.39 把一次同余方程 19x \equiv 559(\bmod\ 1155) 化成模较小的一次同余方程组并求解之。

解答　1155=3\times5\times7\times11。因为 3,5,7,11 两两互素，故 19x\equiv559(\bmod\ 1155) 等价于下述方程组

\begin{cases} 19x\equiv559(\bmod 3)\\ 19x\equiv559(\bmod 5)\\ 19x\equiv559(\bmod 7)\\ 19x\equiv559(\bmod 11) \end{cases}

化简，得

\begin{cases} x\equiv1(\bmod 3)\\ -x\equiv-1(\bmod 5)\\ -2x\equiv-1(\bmod 7)\\ -3x\equiv-2(\bmod 11) \end{cases}

即

\begin{cases} x\equiv1(\bmod 3)\\ x\equiv1(\bmod 5)\\ 2x\equiv1(\bmod 7)\\ 3x\equiv2(\bmod 11) \end{cases}

而 2^{-1}\equiv4(\bmod 7)，3^{-1}\equiv4(\bmod 11)，故方程组又等价于

\begin{cases} x\equiv1(\bmod 3)\\ x\equiv1(\bmod 5)\\ x\equiv4(\bmod 7)\\ x\equiv8\equiv-3(\bmod 11) \end{cases}

在上题(2)中已求得 M_1=385,M_1^{-1}=1,M_2=231,M_2^{-1}=1,M_3=165,M_3^{-1}=2,M_4=105， M_4^{-1}=2。于是，得

x\equiv1\times385\times1+1\times231\times1+4\times165\times2-3\times105\times2\equiv151(\bmod 1155)

11.40 某人每工作 8 天后休息 2 天。一次他恰好是周六和周日休息。问：这次之后他至少要多少天后才能恰好赶上周日休息？

解答　设至少 x 天后。10 天一个周期，最后两天休息，可表示成 x+1\equiv9(\bmod 10) 或 x+1\equiv0(\bmod 10)。恰好是周日可表示成 x+1\equiv0(\bmod 7)。于是有

\begin{cases} x\equiv8(\bmod 10)\\ x\equiv-1(\bmod 7) \end{cases}\tag{1}

或

\begin{cases} x\equiv-1(\bmod 10)\\ x\equiv-1(\bmod 7) \end{cases}\tag{2}

m_1=10,m_2=7,m=70,M_1=7,M_1^{-1}=3,M_2=10,M_2\equiv3(\bmod 7),M_2^{-1}=5。方程组 (1)的解为

x_1\equiv8\times7\times3-1\times10\times5\equiv48(\bmod 70)

方程组(2)的解为

x_2\equiv-1\times7\times3-1\times10\times5\equiv-1\equiv69(\bmod 70)

故至少要在 48 天后(即周日休息后的第 49 天)恰好能在周日休息。

解读：把「第几天休息、第几天是周日」都换算成对同一起点的天数取余，两个周期条件就变成同一未知数 x 的两个同余式；休息日落在周期的最后两天，因此有两个可能式子，要分别解出再取较小的非负解。

11.41 求 4 个相邻整数，它们依次可被 4,9,25,49 整除。

解答　设第 1 个数为 x，有

\begin{cases} x\equiv0(\bmod 4)\\ x+1\equiv0(\bmod 9)\\ x+2\equiv0(\bmod 25)\\ x+3\equiv0(\bmod 49) \end{cases}

即

\begin{cases} x\equiv0(\bmod 4)\\ x\equiv-1(\bmod 9)\\ x\equiv-2(\bmod 25)\\ x\equiv-3(\bmod 49) \end{cases}

m_1=4， m_2=9， m_3=25， m_4=49， m=4\times9\times25\times49=44\ 100 M_1=9\times25\times49=11\ 025， M_1\equiv1\times1\times1\equiv1(\bmod 4)， M_1^{-1}=1 M_2=4\times25\times49=4900， M_2\equiv4\times(-2)\times4\equiv4(\bmod 9)， M_2^{-1}=7 M_3=4\times9\times49=1764， M_3\equiv4\times9\times(-1)\equiv-11(\bmod 25)， M_3^{-1}=9 M_4=4\times9\times25=900， M_4\equiv18(\bmod 49)， M_4^{-1}=-19 解得 x\equiv0\times11\ 025\times1-1\times4900\times7-2\times1764\times9-3\times900\times(-19) \equiv-14\ 752(\bmod 44\ 100)\equiv29\ 348(\bmod 44\ 100)

4 个相邻的整数为 29\ 348+44\ 100k,29\ 349+44\ 100k,29\ 350+44\ 100k,29\ 351+44\ 100k，其中 k=0,\pm1,\pm2,\cdots

11.42 给定模 m_1 = 9，m_2 = 7，m_3 = 5，设 x = 17，y = 8，

（1）给出 x,y 的模表示。

（2）计算 x+y，x-y 和 xy 的模表示。

（3）利用(2)的结果计算 x+y，x-y 和 xy。

解答　（1）x=(8,3,2),y=(8,1,3)。

（2）x+y=(7,4,0),x-y=(0,2,4),xy=(1,3,1)。

（3）分别解下述一次同余方程组：

\begin{cases} z_1\equiv7(\bmod 9)\\ z_1\equiv4(\bmod 7)\\ z_1\equiv0(\bmod 5) \end{cases} \quad \begin{cases} z_2\equiv0(\bmod 9)\\ z_2\equiv2(\bmod 7)\\ z_2\equiv4(\bmod 5) \end{cases} \quad \begin{cases} z_3\equiv1(\bmod 9)\\ z_3\equiv3(\bmod 7)\\ z_3\equiv1(\bmod 5) \end{cases}

m_1=9,m_2=7,m_3=5,m=9\times7\times5=315,M_1=7\times5=35,M_1\equiv-1(\bmod 9)， M_1^{-1}=-1,M_2=9\times5=45,M_2\equiv3(\bmod 7),M_2^{-1}=-2,M_3=9\times7=63,M_3\equiv3(\bmod 5)， M_3^{-1}=2。解得

z_1\equiv7\times35\times(-1)+4\times45\times(-2)+0\times63\times2\equiv25(\bmod 315) z_2\equiv0\times35\times(-1)+2\times45\times(-2)+4\times63\times2\equiv9(\bmod 315) z_3\equiv1\times35\times(-1)+3\times45\times(-2)+1\times63\times2\equiv136(\bmod 315)

得 x+y=25，x-y=9，xy=136。

11.43 下述方程是否有整数解？若有，试给出所有的整数解。

（1）3x+2y = 6。

（2）12x-9y = 8。

解答　（1）3x+2y=6。

考虑一次同余方程 3x\equiv6(\bmod 2)，即 x\equiv0(\bmod 2)。它的解为 x=2k，其中 k 是任意整数。代入原方程 6k+2y=6，得 y=3-3k。故方程的解为 x=2k,y=3-3k，其中 k 是任意整数。

（2）12x-9y=8。

方法 1 如果方程有解，则解必满足 12x\equiv8(\bmod 9)。而 \gcd(12,9)=3,3\nmid8,12x\equiv8(\bmod 9)无解，故原方程无解。

方法 2 如果方程有解，则等式左边 12x-9y 能被 3 整除，而等式右边 8 不能被 3 整除，矛盾，故原方程无解。

11.44 设 m>0，d = \gcd(a,m) 且 d \mid c，则一次同余方程 ax \equiv c(\bmod\ m) 在模 m 下有 d 个解。

解答　设 a=da_1,m=dm_1，其中设 a_1,m_1 互素。根据主教材中定理 11.8，存在 x_0 使 ax_0\equiv c(\bmod m)。又设 x 是方程的解，即 ax\equiv c(\bmod m)。于是，a(x-x_0)\equiv0(\bmod m)。它等价于 a_1(x-x_0)\equiv0(\bmod m_1)。而 a_1 与 m_1 互素，故有 x-x_0\equiv0(\bmod m_1)。因此，方程在模 m 下恰好有 d 个解 x\equiv x_0+km_1(\bmod m),k=0,1,\cdots,d-1。

11.45 设 m>1，ac \equiv bc(\bmod\ m)，d = \gcd(c,m)，则 a \equiv b(\bmod\ m/d)。

解答　记 c=dc_1,m=dm_1，其中 c_1,m_1 互素。由 ac\equiv bc(\bmod m)，有 m\mid ac-bc，即 dm_1\mid d(a-b)c_1，从而有 m_1\mid(a-b)c_1。又 c_1,m_1 互素，故 m_1\mid a-b，得证 a\equiv b(\bmod m_1)，即 a\equiv b(\bmod m/d)。

11.46 设 p 是素数，若 x^2 \equiv 1(\bmod\ p)，则 x \equiv 1(\bmod\ p) 或 x \equiv -1(\bmod\ p)。

解答　由 x^2\equiv1(\bmod p)，有 p\mid x^2-1，即 p\mid(x-1)(x+1)。而 p 是素数，故有 p\mid x-1 或 p\mid x+1。得证 x\equiv1(\bmod p) 或 x\equiv-1(\bmod p)。

11.47 设正整数 m>n。证明：2^n-1 \mid 2^m-1 当且仅当 n \mid m。

解答　方法 1 充分性。如果 n\mid m，设 m=kn,k 是大于 1 的整数，于是

2^m-1=2^{kn}-1=(2^n-1)(2^{(k-1)n}+2^{(k-2)n}+\cdots+1)

得证 2^n-1\mid2^m-1。

必要性。如果 2^n-1\mid2^m-1，设 2^m-1=(2^n-1)(a_02^{m-n}+a_12^{m-n-1}+\cdots+a_{m-n})，其中 a_i=0 或 1,0\le i\le m-n。将等式的右边展开，比较两边得

\begin{aligned} a_0 &= 1 & a_1 &= \cdots = a_{n-1} = 0\\ a_k - a_{k-n} &= 0 & n &\le k \le m-n\\ a_{m-2n+1} &= \cdots = a_{m-n-1} = 0 & a_{m-n} &= 1 \end{aligned}

除 a_{m-n} 外的 m-n 个系数 a_0,\cdots,a_{m-n-1} 可分成若干组，每组 n 个，第一个为 1，其余 n-1 个为 0，故必有 n\mid m。

方法 2 采用二进制表示，2^m-1=\underbrace{(1\cdots1)_2}_{m\text{个}},2^n-1=\underbrace{(1\cdots1)_2}_{n\text{个}}。根据二进制除法， \underbrace{(1\cdots1)_2}_{n\text{个}}\mid\underbrace{(1\cdots1)_2}_{m\text{个}} 当且仅当 n\mid m。

11.48 设 m,n 是正整数，证明：\gcd(2^m-1,2^n-1) = 2^{\gcd(m,n)}-1。

解答　记 d=\gcd(m,n),m=dm_1,n=dn_1，其中 m_1,n_1 互素。

2^m-1=(2^d-1)(2^{d(m_1-1)}+2^{d(m_1-2)}+\cdots+2^d+1)

2^n-1=(2^d-1)(2^{d(n_1-1)}+2^{d(n_1-2)}+\cdots+2^d+1)

记 A_0=2^{d(m_1-1)}+2^{d(m_1-2)}+\cdots+2^d+1,A_1=2^{d(n_1-1)}+2^{d(n_1-2)}+\cdots+2^d+1。

要证 A_0 与 A_1 互素。

方法 1 由于 m_1,n_1 互素，可设

\begin{aligned} m_1 &= k_1n_1+n_2 & 1 &< n_2 < n_1\\ n_1 &= k_2n_2+n_3 & 1 &< n_3 < n_2\\ &\qquad\vdots\\ n_{r-1} &= k_rn_r+1 \end{aligned}

于是

\begin{aligned} A_0 &= A_1(2^{d(m_1-n_1)}+2^{d(m_1-2n_1)}+\cdots+2^{d(m_1-k_1n_1)})+A_2\\ A_2 &= 2^{d(n_2-1)}+2^{d(n_2-2)}+\cdots+2^d+1\\ A_1 &= A_2(2^{d(n_1-n_2)}+2^{d(n_1-2n_2)}+\cdots+2^{d(n_1-k_2n_2)})+A_3 \end{aligned}

A_3=2^{d(n_3-1)}+2^{d(n_3-2)}+\cdots+2^d+1

\vdots

A_{r-1}=2^{d(n_{r-1}-1)}+2^{d(n_{r-1}-2)}+\cdots+2^d+1

A_r=2^{d(n_r-1)}+2^{d(n_r-2)}+\cdots+2^d+1

A_{r-1}=A_r(2^{d(n_{r-1}-n_r)}+2^{d(n_{r-1}-2n_r)}+\cdots+2^d)+1

根据主教材中定理 11.5，A_0 与 A_1 互素，得证 \gcd(2^m-1,2^n-1)=2^d-1。

方法 2 由于 m_1,n_1 互素，存在整数 a,b，使得 am_1+bn_1=1。不妨设 a>0,b<0。令 c=-b，则

B=2^{d(a-1)m_1}+2^{d(a-2)m_1}+\cdots+2^{dm_1}+1

C=2^{d(c-1)n_1+1}+2^{d(c-2)n_1+1}+\cdots+2^{dn_1+1}+2^d

有

A_0B=2^{d(am_1-1)}+2^{d(am_1-2)}+\cdots+2^d+1

A_1C=2^{d(cn_1-1)}+2^{d(cn_1-2)}+\cdots+2^d=2^{d(am_1-1)}+2^{d(am_1-2)}+\cdots+2^d

从而，A_0B-A_1C=1，根据主教材中的定理 11.8，A_0 与 A_1 互素，得证 \gcd(2^m-1,2^n-1)=2^d-1。

11.49 证明：所有的梅森数两两互素。

解答　根据梅森数的定义和上题可立即得到。

11.50 验证 m_1 = 2^{32}-1，m_2 = 2^{31}-1，m_3 = 2^{29}-1，m_4 = 2^{27}-1，m_5 = 2^{25}-1 两两互素。

解答　32,31,29,27 和 25 两两互素。由题 11.48，2^{32}-1,2^{31}-1,2^{29}-1,2^{27}-1,2^{25}-1 两两互素。

11.51 设 F_n = 2^{2^n}+1，n = 0,1,2,\cdots。证明：对任意的 n \neq m，F_n 与 F_m 互素。

解答　不妨设 n<m，于是

2^{2^m}+1=(2^{2^n}+1)(2^{2^m-2^n}-2^{2^m-2\cdot2^n}+2^{2^m-3\cdot2^n}-\cdots+2^{2^m-(2^{m-n}-1)2^n}-1)+2

由主教材中定理 11.5，\gcd(F_m,F_n)=\gcd(F_n,2)。注意到 F_n 是奇数，\gcd(F_n,2)=1，得证 \gcd(F_m,F_n)=1，从而 F_m 与 F_n 互素。

11.52 证明：存在无穷多个 n 使得 \phi(n)>\phi(n+1)。

解答　设 n 是大于 3 的素数，\varphi(n)=n-1。又 n+1 是偶数，有 \frac{n-1}{2} 个小于 n+1 的偶数，它们均与 n+1 不互素，故 \varphi(n+1)\le n-\frac{n-1}{2}=\frac{n+1}{2}<n-1=\varphi(n)。而大于 3 的素数有无穷多个，证毕。

11.53 证明欧拉函数具有下述性质。

（1）若 m 和 n 互素，则 \phi(mn) = \phi(m)\phi(n)。

（2）设 p 为素数，k 为正整数，则 \phi(p^k) = p^{k-1}(p-1)。

（3）设 n>1，它的素因子分解为 n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}，则

\begin{aligned} \phi(n) &= p_1^{\alpha_1-1}(p_1-1)p_2^{\alpha_2-1}(p_2-1)\cdots p_r^{\alpha_r-1}(p_r-1) \\ &= n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right) \end{aligned}

解答　（1）分析：由于在模 m 同余关系下保持与 m 的互素性，可以令 Z_m^*=\{[a]_m\mid a 与 m 互素\}，|Z_m^*|=\varphi(m)。为了证明 \varphi(mn)=\varphi(m)\varphi(n)，只需给出 Z_m^*\times Z_n^* 到 Z_{mn}^* 的双射函数。

证明：作映射 g:Z_m^*\times Z_n^*\to Z_{mn}^* 如下 g([a]_m,[b]_n)=[an+bm]_{mn}。

首先证明 g 的定义是有效的。若 a\equiv a'(\bmod m),b\equiv b'(\bmod n)，即 m\mid a-a'，n\mid b-b'，则 mn\mid(an+bm)-(a'n+b'm)，即 an+bm\equiv a'n+b'm(\bmod mn)。

又若 a 与 m 互素，b 与 n 互素，则 an+bm 与 mn 互素。假设不然，d=\gcd(an+bm,mn)>1。由于 m 与 n 互素，d=d_1d_2,d_1\mid m,d_2\mid n,d_1,d_2 中至少有一个大于 1，并且当 d_1>1 时 d_1 与 n 互素，当 d_2>1 时 d_2 与 m 互素。不妨设 d_1>1，有 d_1\mid an+bm，得到 d_1\mid an，而 d_1 与 n 互素，故 d_1\mid a，与 a,m 互素矛盾。这就证明了 g 的定义是有效的。

其次证明 g 是单射。若 an+bm\equiv a'n+b'm(\bmod mn)，即 mn\mid(a-a')n+(b-b')m。当然有 m\mid(a-a')n+(b-b')m，从而 m\mid(a-a')n。而 m 与 n 互素，故 m\mid a-a'，即 a\equiv a'(\bmod m)。同理有 b\equiv b'(\bmod n)。得证 g 是单射。

最后证明 g 是满射。由于 m 与 n 互素，存在整数 x,y 使得 xn+ym=1。对任意的整数 c，若 c 与 mn 互素，则 c 与 m 互素。x 与 m 也互素，故 cx 与 m 互素。从而 [cx]_m\in Z_m^*。同理，[cy]_n\in Z_n^*。而 g([cx]_m,[cy]_n)=[cxn+cym]_{mn}=[c]_{mn}，得证 g 是满射。

因为 g 是双射，故 |Z_m^*|\times|Z_n^*|=|Z_{mn}^*|，即 \varphi(mn)=\varphi(m)\varphi(n)。

（2）当 k=1 时，\varphi(p)=p-1。当 k>1 时，对 0\le x<p^k，x 与 p^k 不互素当且仅当 p\mid x，即 x=px_1,0\le x_1<p^{k-1}，故 0,1,\cdots,p^k-1 中有 p^{k-1} 个与 p^k 不互素，从而有 p^k-p^{k-1}=p^{k-1}(p-1) 个与 p^k 互素，即 \varphi(p^k)=p^{k-1}(p-1)。

（3）由(1)和(2)立即得到。

11.54 证明：当 n \geqslant 3 时，2 \mid \phi(n)。

解答　设 n=2^km,m 是奇数。

若 k\ge2，根据题 11.53(1)和(2)，\varphi(n)=2^{k-1}\varphi(m)。而 k-1\ge1，有 2\mid\varphi(n)。

若 k<2，则 m 含有素因子 p\ge3。根据上题，\varphi(n) 含因子 p-1。而 2\mid p-1，故有 2\mid\varphi(n)。

11.55 设 n>3 是素数，则小于 n 的正整数中除 1 和 n-1 外可分成对，使得每一对中的两个数互为模 n 逆。

解答　因为 n 是素数，每一个 x(1\le x\le n-1) 的模 n 逆 x^{-1}(1\le x^{-1}\le n-1) 存在。

先证明对于 1\le x,y\le n-1，若 x\ne y，则 x^{-1}\ne y^{-1}(\bmod n)。假设不然，x^{-1}\equiv y^{-1}(\bmod n)。两边同乘 xy，得 y\equiv x(\bmod n)，矛盾。注意到，1^{-1}=1,(n-1)^{-1}=n-1，故当 1<x<n-1 时，1<x^{-1}<n-1。

再证明当 1<x<n-1 时，x^{-1}\ne x(\bmod n)。假设不然，x^{-1}\equiv x(\bmod n)。两边同乘 x，得 x^2\equiv1(\bmod n)。已知 n 是素数，由题 11.46，必有 x\equiv1(\bmod n) 或 x\equiv-1\equiv n-1(\bmod n)，与 1<x<n-1 矛盾。

根据上述 2 条，\{2,3,\cdots,n-2\} 可被划分成互不相交的对 (x,x^{-1})。

11.56 证明威尔逊(Wilson)定理：设 n>1，则 n 是素数当且仅当 (n-1)! \equiv -1(\bmod\ n)。

解答　必要性。当 n=2 和 3 时，显然成立。设 n>3 是素数，根据题 11.55，2,3,\cdots,n-2 可两两配对，使得每一对的乘积在模 n 下等于 1。于是，(n-1)!\equiv n-1\equiv-1(\bmod n)。

充分性。设 (n-1)!\equiv-1(\bmod n)，要证明 n 是素数。假设不然，n 是合数，则存在 1<a,b<n，使 n=ab。于是，a\mid(n-1)!。显然 a\nmid(n-1)!+1，即 (n-1)!\not\equiv-1(\bmod a)，而 (n-1)!\equiv-1(\bmod n) 且 n=ab，应有 (n-1)!\equiv-1(\bmod a)，矛盾。

解读：必要性的全部工作量在上题——把 2 到 n-2 的数按「互为模 n 逆」配成对，每对乘积为 1，只剩 1 与 n-1 未被配对，于是阶乘等于 n-1\equiv-1。充分性反过来用：若 n=ab 是合数，a 必整除 (n-1)!，从而不可能整除 (n-1)!+1。

11.57 利用费马小定理计算下列各式。

（1）2^{325}\ \bmod\ 5。

（2）3^{516}\ \bmod\ 7。

（3）8^{1003}\ \bmod\ 11。

解答　（1）2^4\equiv1(\bmod 5),2^{325}\equiv2^{4\times81+1}\equiv2(\bmod 5)，得 2^{325}\bmod 5=2。

（2）3^6\equiv1(\bmod 7),3^{316}\equiv3^{6\times56}\equiv1(\bmod 7)，得 3^{316}\bmod 7=1。

解读（原书此处疑似笔误）：题干印的是 3^{516}，答案册此处印成 3^{316}。因 516=6\times 86 与 316 同为 6 的倍数，两者模 7 都余 1，结论一致，此处照抄答案册原文。

（3）8^{10}\equiv1(\bmod 11),8^{1003}\equiv8^{10\times100+3}\equiv8^3\equiv6(\bmod 11)，得 8^{1003}\bmod 11=6。

11.58 设 m 与 n 互素，则 m^{\phi(n)}+n^{\phi(m)} \equiv 1(\bmod\ mn)。

解答　由欧拉定理，m^{\varphi(n)}\equiv1(\bmod n)，即 n\mid m^{\varphi(n)}-1。同理 m\mid n^{\varphi(m)}-1。从而，mn\mid(m^{\varphi(n)}-1)(n^{\varphi(m)}-1)，即 mn\mid m^{\varphi(n)}n^{\varphi(m)}-(m^{\varphi(n)}+n^{\varphi(m)}-1)。而 mn\mid m^{\varphi(n)}n^{\varphi(m)}，故有 mn\mid m^{\varphi(n)}+n^{\varphi(m)}-1，得证 m^{\varphi(n)}+n^{\varphi(m)}\equiv1(\bmod mn)。

11.59 设 f(x) 是整系数多项式，p 是素数。证明：(f(x))^p \equiv f(x^p)(\bmod\ p)。

解答　由费马小定理，(f(x))^p\equiv f(x)(\bmod p)。又 x^p\equiv x(\bmod p)，从而 f(x^p)\equiv f(x)(\bmod p)。得证 (f(x))^p\equiv f(x^p)(\bmod p)。

11.60 设 p 是素数，p \nmid a。证明：对任意的正整数 k，p^k \mid a^{p^{k-1}(p-1)}-1。

解答　因为 p 是素数且 p\nmid a，故 a 与 p^k 互素。由欧拉定理，a^{\varphi(p^k)}\equiv1(\bmod p^k)，即 p^k\mid a^{\varphi(p^k)}-1。而由题 11.53，\varphi(p^k)=p^{k-1}(p-1)，得证 p^k\mid a^{p^{k-1}(p-1)}-1。