高等算术习题(2) - 同余

高等算术习题(2) - 同余

Fri Dec 24, 2021

这是《高等算术》习题系列的第二篇。 第二章讲了同余关系、同余方程、费马小定理、欧拉函数等。

---

2.1 求证：如果 a≡b(mod2n)，则 a2≡b2(mod4n)。更一般地，如果 a≡b(modkn)，则 ak≡bk(modk2n)。

证明：仅对第二个命题给出证明；取 k=2 就可得到第一个命题。

根据 a≡b(modkn) 可设 a=q1(kn)+rb=q2(kn)+r

则对 ak 用二项式定理展开有 ak=∑i=0k(ki)[q1(kn)]k−iri 式中的每项 (ki)[q1(kn)]k−iri 当 0≤i≤k−2 时具有因子 (kn)2，因此可以被 k2n 整除；当 i=k−1 时为 kq1kn 也可以被 k2n 整除。所以写成同余式只留下最后一项 ak≡rk(modk2n)

同理可证 bk≡rk(modk2n)

所以 ak≡bk(modk2n)，证明完毕。

---

2.2 哪些数字除以 3、4、5、6 得到相应的余数分别是 2、3、4、5？

解法一：设满足条件的数字为 x，则

(1)x≡2(mod3)(2)x≡3(mod4)(3)x≡4(mod5)(4)x≡5(mod6)

由 (1) 可知 x=3p+2，代入 (2) 得 3p≡1(mod4) 解得 p≡3(mod4) 即 x=3(4q+3)+2=12q+11，代入 (3) 得 12q≡3(mod5) 解得 q≡4(mod5) 即 x=12(5r+4)+11=60r+59，代入 (4) 得 60r≡0(mod6) 此为恒等式，r 取任意整数皆可。

所以 x=60r+59.

解法二：设满足条件的数字为 x，则

x+1≡0(mod3)x+1≡0(mod4)x+1≡0(mod5)x+1≡0(mod6)

由此可知 3、4、5、6 都是 (x+1) 的因子，任何满足条件的 x+1 一定是 60 （3、4、5、6的最小公倍数）的整数倍，所以通解可以写成 60k−1。

---

2.4 求解同余方程 97x≡13(mod105)。

解：方程等价于不定方程 97x−105y=13，可用欧几里得算法求解。

(1)105=97×1+8(2)97=8×12+1

由 (1) 得 8=105−97， 代入 (2)得 97×13−105×12=1. 方程两边同乘以 13 得 97×169−105×156=13. 所以 x≡169≡64(mod105).

---

2.5 计算 (10273+55)37 除以 111 的余数。

解： 111=3×37。首先考察该式除以 3 的余数。因为 102 能被 3 整除，所以 10273≡0(mod3)，因此 (1)(10273+55)37≡5537≡137≡1(mod3)

然后考察原式除以 37 的余数。因为 102≡28,55≡18(mod37)，得 (2)(10273+55)37≡28+18≡9(mod37) 这里应用了费马小定理：a72≡a36≡1(mod37)。

根据 (1) 设 x=3q+1，代入 (2) 得 3q≡8(mod37)

注意到 3×12≡−1，所以 q≡−12×8≡15(mod37)。设 q=37r+15，则 x=3(37r+15)+1=111r+46，所以所要求的余数为 46。

---

2.11 求证： n 是质数当且仅当σ(n)+ϕ(n)=nd(n).

证明： 首先证明必要性。如果 n 是质数，那么 σ(n)=n+1ϕ(n)=n−1d(n)=2 由此可见等式成立。

下面证明充分性。当 n=1 时易知等式不成立。只须证明当 n 是合数时等式不成立即可。根据算术基本定理可设 n=∏i=1Npici 其中 pi 是质数，ci≥1。

设 ni=pici，则 σ(ni)ni=1+1p+⋯+1pciϕ(ni)ni=1−1pd(ni)=ci+1 于是 σ(ni)+ϕ(ni)ni=2+1p2+⋯+1pci<2+122+⋯<2+1=3 当 ci=1 时，σ(ni)+ϕ(ni)ni=d(ni)=2。 当 ci≥2 时， d(ni)=ci+1≥3。 综上可知 (1)σ(ni)+ϕ(ni)≤nid(ni) 当且仅当 ci=1 时取“=”。

考虑 ∏i=1N[σ(ni)+ϕ(ni)] 的展开，展开后每项都是正数，如果只保留全是 σ 和全是 ϕ 的两项，可得不等式 (2)∏i=1N[σ(ni)+ϕ(ni)]≥∏i=1Nσ(ni)+∏i=1Nϕ(ni) 当且仅当 N=1 时取“=”。

另一方面，根据函数的积性可知 ∏i=1Nσ(ni)=σ(n)∏i=1Nϕ(ni)=ϕ(n)∏i=1Nnid(ni)=nd(n) 综合 (1)、(2) 得 σ(n)+ϕ(n)≤∏i=1N[σ(ni)+ϕ(ni)]≤∏i=1Nnid(ni)=nd(n).

因为 n 是合数，所以上式中的等号不可能同时取得，所以等式 σ(n)+ϕ(n)=nd(n) 不能成立。

证明完毕。

---

2.12 求证：

1. 如果 p 是奇质数，那么 (p−2)!≡1(modp)；
2. 如果 p>3 是质数，那么 (p−3)!≡(p−1)/2(modp)。

1. 根据 Wilson 定理，(p−1)!≡p−1(modp)。因为 (p−1) 和 p 互质，所以可以约去 (p−1)，得 (p−2)!≡1(modp)。
2. 因为 (p−2)p−12=p−32p+1≡1(modp)所以在前一问的基础上两边同乘以 (p−1)/2 即可。

---

2.13 如果 p 是奇质数，且 a+b=p−1，证明 a!b!+(−1)a≡0(modp)。

由 1≡−(p−1)(modp)2≡−(p−2)(modp)⋮a≡−(p−a)(modp) 得 (1)a!≡(−1)a(p−1)(p−2)⋯(p−a)(modp).

另一方面， (2)b!=(p−1−a)!=(p−1)!(p−1)(p−2)⋯(p−a).

综合 (1)、(2) 得 a!b!≡(−1)a(p−1)!(modp).

根据 Wilson 定理，(p−1)!≡−1，所以 a!b!≡−(−1)a，即 a!b!+(−1)a≡0(modp)。

---

2.15 求解同余方程 x2≡17(mod128)。

解：枚举 64 以内所有自然数即可（一个正数解对应一个负数解）。为了缩小枚举范围，可以考虑以下条件：

1. 17 不是完全平方数，所以不必枚举 12 以下的数。
2. 只须枚举奇数即可，偶数显然不满足条件。
3. 如果 x 是一个解，那么 (64−x) 也是一个解，所以枚举不超过 32 的数即可。

枚举得 232=529≡17(mod128) 所以方程的解是 x≡±23,x≡±41(mod128)。

---

2.16 求解模 19 的同余方程（或证明方程无解）：

1. x3≡3,
2. x3≡7,
3. x3≡11.

解：列出 y=x3 在模 19 算术下的表格：

x| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|
y| 0| 1| 8| 8| 7|11| 7| 1|18| 7|12| 1|18|12| 8|12|11|11|18|

由此可知：

1. x3≡3 无解；
2. x3≡7 的解是 x≡4,6,9；
3. x3≡11 的解是 x≡5,16,17。

---