2.2

解答题

1

关于欧拉函数，对于 10：$$\phi(10) = 4$$

因此我们知道 $$7^4 \equiv 1 \pmod{10}$$，而 $$2046 \equiv 2 \pmod{4}$$

因此，我们有：$$7^{2046} \equiv 7^2 \equiv 9 \pmod{10}​$$

2

对于 100 有：$$100 = 4*25$$，并且有 $$\phi(25) = 20$$

因此首先有 $$2^{100} \equiv 0 \pmod{4}$$，然后有 $$2^{100} = (2^{5})^{20} \equiv 1 \pmod{25}$$

而存在这样的数 76：$$2^{100} \equiv 76 \pmod{4}, 2^{100} \equiv 76 \pmod{25}$$

因此 $$2^{100} \equiv 76 \pmod{100}$$

3

考虑到 $$\displaystyle (x+4)^5 \overset{二项式展开}{\equiv} x^5 \pmod{4}$$

有因为 $$99 = 4 * 25 - 1 = 4*24 + 3$$

因此我们有：$$1^5 + 2^5 + 3^5 +… + 99^5 \equiv 24 * (1^5 + 2^5 + 3^5) \equiv 0\pmod{4}$$

4

我们知道 $$555 \equiv 2 \pmod{7}$$，

并且有：$$2^3 \equiv 1 \pmod{7}, 555 \equiv 0 \pmod{3}$$

因此：$$555^{555} \equiv 2^{555} \equiv 2^0 \equiv 1 \pmod{7}​$$

5

（1）每个数都是奇数的模 9 完全剩余系：

$${1, 11, 3, 13, 5,15, 7, 17, 9}$$

（2）每个数都是偶数的模 9 完全剩余系：

$${0, 10, 2, 12, 4, 14, 6, 16, 8}$$

6

考虑 $$r_i = 11k+n, n =1,2,…,11$$，

有：$$11k+n \equiv 1\pmod{3} \Rightarrow 11k \equiv 1-n \pmod{3}$$

枚举 n 计算 k 可以得到这样的模 11 完全剩余系：

$$k = {0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1} \overset{剩余系}{\Rightarrow}{1, 13, 25, 4, 16, 28, 7, 19, 31, 10, 22}$$

7

可以通过 sage 中的数论模块计算欧拉函数：

1
2
3

from sage.all import *
print(euler_phi(24), euler_phi(64), euler_phi(187), euler_phi(360))
# (8, 32, 160, 96)

（NOTE：在 Arch Linux 下安装 sage 的命令：yaout sagemath）

也可以用短除法将其素因数分解$$\displaystyle m = p_1^{a_1} p_2^{a_2} … p_s^{a_s}​$$，

然后利用公式 $$\displaystyle \phi(m) = m \prod_{i=1}^s (1 - \frac{1}{p_i})​$$，计算其欧拉函数。比如：

1
2
3

24 ==> 2 2 2 3 ==> 24=(2^3)*(3^1)

phi(24) ==> 24*(1/2)*(2/3) ==> 8

8

费马小定理：若 p 是素数，则对任意整数 a，有：$$a^p \equiv a \pmod{p}$$

（1）

根据费马小定理，我们有：$$9^{73} \equiv 9 \pmod{73}$$

我们又知道：$$794 \equiv 2 \pmod{72}$$

因此我们知道 $$9^{794} \equiv 9^2 \equiv 8 \pmod{73}$$

因为 $$a \in [0, 73)​$$，所以 $$a = 8​$$

（2）

我们有：$$x^{29} \equiv x \pmod{29}, 86 \equiv 2 \pmod{28}$$

因此 $$x^{86} \equiv x^{2} \equiv 6\pmod{29}​$$

1. 穷举 29 以内的所有自然数：

   1 2 3

   for i in range(29): if (i**2)%29 == 6: print(i) # 8 21

2. 也可使用 sage 模块进行求解：

   1 2 3

   from sage.all import * x = SR.symbol('x') solve_mod(x**2==6, 29) # [(8,), (21,)]

所以原同余方程的解为：$$x \equiv 8 \pmod{29}​$$ 或 $$x \equiv 21 \pmod{29}​$$

（3）

同样的：$$x^{13} \equiv x \pmod{13}, 39 \equiv 3 \pmod{12}$$

因此：$$x^{39} \equiv x^{3} \equiv 3 \pmod{13}$$

同样地，穷举 13 以内的所有自然数（大于 13 的数仍无法成立已在第三题中证明）：

1

for i in range(13): if (i**3)%13 == 3: print(i) # <没有输出>

所以该同余方程没有解

9

可以直接使用 gmpy2 中的 invert 函数进行计算：

1
2

import gmpy2
print(gmpy2.invert(229, 281)) # mpz(27)

另外，笔算可以使用欧几里得扩展算法，

因为考虑到贝祖等式成立：$$ax + by = gcd(a, b)$$

令 $$a = 229, b = 281 \Rightarrow gcd(a, b) =1$$，那么 x 即为 a 关于模 281 的逆元：

$$\begin{pmatrix} 281 \ 229\end{pmatrix} = \begin{pmatrix} 1 & 1 \ 1 & 0\end{pmatrix}\begin{pmatrix} 4 & 1 \ 1 & 0\end{pmatrix}\begin{pmatrix} 2 & 1 \ 1 & 0\end{pmatrix}\begin{pmatrix} 2 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix} 10 & 1 \ 1 & 0\end{pmatrix} \begin{pmatrix} 1 \ 0\end{pmatrix} ​$$

$$\Rightarrow \begin{pmatrix} 281 \ 229\end{pmatrix} = \begin{pmatrix} 281 & 27\ 229 & 22\end{pmatrix}\begin{pmatrix} 1 \ 0\end{pmatrix} \Rightarrow \begin{pmatrix} -22 & 27 \ 229 & -281\end{pmatrix} \begin{pmatrix} 281 \ 229\end{pmatrix} = \begin{pmatrix} 1 \ 0\end{pmatrix}$$

因此我们有：$$229^{-1} = 27 \pmod{281}$$

10

设对于 m：$$\displaystyle m = 2^{a_1} p_2^{a_2} … p_s^{a_s}​$$，其中 $$\alpha_1​$$ 为非负整数，其他 $$\alpha_i​$$ 为正整数

显然有 $$p_i, i = 2,3,…,s$$ 为奇数。

根据欧拉函数的计算有： $$\displaystyle \phi(m) = m (\frac{1}{2})^{\alpha_1>0}\prod_{i=2}^s (1 - \frac{1}{p_i}) = m (\frac{1}{2})^{\alpha_1>0}\prod_{i=1}^s \frac{p_i - 1}{p_i}$$

1. 若 $$s > 0​$$，那任意的 i，总有 $$p_i \equiv 1 \pmod{2}, p_i -1 \equiv 0 \pmod{2}​$$，所以此时 $$\displaystyle \prod_{i=2}^s \frac{p_i - 1}{p_i}​$$ 总有一个 2 的因子。
2. 若 $$s =0​$$，那么 $$\displaystyle \phi(m) = \frac{m}{2} ​$$，为了使 $$ m > 3​$$，一定有 $$\displaystyle \frac{m}{2}​$$ 存在 2 的因子。

11

设命题 M：$$\phi(m)$$ 能被 4 整除；$$\overline{M}$$：$$\phi(m)$$ 不能被 4 整除。

1. 先考虑 m 为偶数，根据第十题的讨论：$$\overline{M}$$ 一个必要条件是 $$\displaystyle \frac{m}{2}$$ 的素因子数量仅为一（若大于 1 的话，必然出现两个 2 的因子），分类讨论这个素因子为 2 的情况：

   • 得到一个更强的 $$\overline{M}$$ 的必要条件：$$\displaystyle \frac{m}{2}$$ 是素数。

   再考虑 $$\overline{M}$$ 一个必要条件：

   不考虑 $$\displaystyle \frac{m}{2} = 2$$ 的情况，为使 $$\displaystyle \frac{m}{2} - 1 \not\equiv 0 \pmod{4}$$，必有 $$\displaystyle \frac{m}{2} = 4k+3$$。

   所以：$$m \in {2k | k = 2 或 k 为形如 4n+3 的素数}$$

2. 再考虑 m 为奇数，同样根据第十题的讨论也能得到，m 的素因子数量仅为一，结合 m 为奇数的条件：

   • 可以得到一个 $$\overline{M}$$ 的必要条件：$$m$$ 是素数

   再考虑一个必要条件可以得到：$$m = 4k+3$$。

   所以：$$m \in {k | k为形如 4n+3 的素数}$$

综上所述，m 的取值空间为：$${2} \cup{k, 2k | k为形如 4n+3 的素数}$$

12

1
2
3
4
5
6
7

from sage.all import *
x = SR.symbol('x')
solve_mod(27*x == 12, 15), solve_mod(24*x == 6, 81), solve_mod(91*x == 26, 169), solve_mod(71*x == 32, 3441)
# ([(6,), (1,), (11,)],
#  [(7,), (34,), (61,)],
#  [(4,), (17,), (30,), (43,), (56,), (69,), (82,), (95,), (108,), (121,), (134,), (147,), (160,)],
#  [(1309,)])

笔算通过以下的定理计算：

设 $$m > 1, gcd(a, m) =d > 1$$，则同余方程 $$ax \equiv b \pmod{m}$$ 有解的充要条件是 $$d | b$$，并且其解的个数为 d，且若 $$x \equiv x_0 \pmod{m}$$ 是一个特解，则它的 d 个解为：$$\displaystyle x \equiv x_0 + \frac{m}{d}t \pmod{m}, t = 0,1,…,d-1$$

13

容易得到：$$7^{-1} \equiv 15 \pmod{26}$$，即：$$7*15 \equiv 1 \pmod{26}$$

$$y \equiv 7x + 3\pmod{26} \Rightarrow y-3 \equiv 7x \pmod{26} \Rightarrow x \equiv15y -45 \pmod{26}$$

化简得到：$$x \equiv 15y + 7 \pmod{26}$$

14

定理：设 $$m_1, m_2,.., m_k$$ 是 k 个两两互素的正整数，若令 $$m = m_1 m_2 …m_k, m = m_iM_i$$，则对任意的整数 $$b_1, b_2, …, b_k$$，同余方程组：

$$\begin{cases}x \equiv b_1 \pmod{m_1} \ x \equiv b_2 \pmod{m_2} \ … \x \equiv b_k \pmod{m_k} \end{cases}$$

有唯一解：$$\displaystyle x \equiv \sum_{i=1}^{k} M_iM_i’ b_i \pmod{m}$$，其中 $$M_i M_i’ \equiv 1 \pmod{m_i}$$

（1）$$x \equiv 2519 + 12 * 23 * 6 \equiv 81 \pmod{300}$$

（2）$$x \equiv 33015 + 154412 + 1051318 \equiv 1272\pmod{2310}$$

（3）

$$\begin{cases} x \equiv 2 \pmod{9} \ 3x \equiv 4 \pmod{5} \ 4x \equiv 3 \pmod{7} \end{cases} \Rightarrow \begin{cases} x \equiv 2 \pmod{9} \ x \equiv 24 \pmod{5} \ x \equiv 23 \pmod{7} \end{cases} \Rightarrow \begin{cases} x \equiv 2 \pmod{9} \ x \equiv 3 \pmod{5} \ x \equiv 6 \pmod{7} \end{cases}$$

所以 $$x \equiv 3582 + 6323 + 4556 \equiv 83 \pmod{315}$$

15

设士兵的总人数为 x，即有方程组：$$\begin{cases}x \equiv 1 \pmod{3} \ x \equiv 2 \pmod{5} \ x\equiv 2 \pmod{7} \end{cases}$$

根据上面描述的定理：$$x \equiv 3521 + 2112 + 1512 \equiv 37\pmod{105}$$

考虑到 x 的取值范围，因此共有 37 个士兵。

16

对于 440，我们有 $$440 = 112^35$$，因此对 $$91x \equiv 419 \pmod{440}$$ 有：

$$\begin{cases} 91x \equiv 419 \pmod{11} \91x \equiv 419 \pmod{8} \ 91x \equiv 419 \pmod{5} \end{cases} \Rightarrow \begin{cases} 3x \equiv 1 \pmod{11} \ 3x \equiv 3 \pmod{8} \ x \equiv 4 \pmod{5} \end{cases} \Rightarrow \begin{cases} x \equiv 4 \pmod{11} \ x \equiv 1 \pmod{8} \ x \equiv 4 \pmod{5} \end{cases}$$

同样的根据之前的定理：$$x \equiv 4084 + 5571 + 8824 \equiv 169 \pmod{440}$$

17

即求同余方程组 $$\begin{cases} x \equiv 0 \pmod{13} \ x \equiv 2 \pmod{3} \ x \equiv 2 \pmod{5}\ x \equiv 2 \pmod{7} \ x \equiv 2 \pmod{11} \end{cases}$$ 的解，

解得 $$x \equiv 2*(50051 + 30032 + 21455 + 13651) \equiv 1157 \pmod{15015}$$

18

设其中的最后一个整数为 x，即解同余方程组：

$$\begin{cases}x - 3\equiv 0 \pmod{2^2} \ x -2 \equiv 0 \pmod{3^2} \ x-1 \equiv 0 \pmod{5^2} \ x \equiv 0 \pmod{7^2}\end{cases} \Rightarrow \begin{cases}x \equiv 3 \pmod{4} \ x \equiv 2 \pmod{9} \ x \equiv 1 \pmod{25} \ x \equiv 0 \pmod{49}\end{cases} $$

解得 $$x \equiv 105^213 + 70^2 * 7 *2 + 42^2 * 9 *1 \equiv 29351\pmod{210^2}$$

所以这四个数分别为：29348, 29349, 29350, 29351

19

也就是说有这样的两个等式成立：$$K \begin{pmatrix} 3 \ 14\end{pmatrix} = \begin{pmatrix} 1 \ 14\end{pmatrix}, K \begin{pmatrix} 2 \ 19\end{pmatrix} = \begin{pmatrix} 11 \ 21\end{pmatrix}$$

对 K 的四个未知数，可以列出以下的方程式：$$\begin{cases} 3a_{11} + 14a_{12} = 1 \ 3a_{21} + 14a_{22} = 14 \ 2a_{11} + 19 a_{12} = 11 \ 2a_{21} + 19 a_{22} = 21\end{cases}\pmod{26}$$

可以由这个方程组解出：$$\begin{cases} a_{11} \equiv 7 \ a_{12} \equiv 19 \ a_{21} = 8 \ a_{22} = 3 \end{cases}$$，所以这个矩阵为 $$K= \begin{pmatrix} 7 & 19 \ 8 & 3\end{pmatrix}$$

20

1
2
3
4

from sage.all import *
x = SR.symbol('x')
print(solve_mod(3*x**14 + 4*x**13 + 2*x**11 + x**9 +x**6 +x**3 + 12*x**2 + x == 0, 5))
# [(0,), (1,), (2,)]

即 $$x \equiv 0, 1, 2 \pmod{5}​$$

另外，可以通过一下方法笔算：

注意到欧拉函数 $$\phi(5) = 4$$，因此根据欧拉定理我们有 $$x^{\phi(5)} \equiv x^4 \equiv 1 \pmod{5}$$

因此在模 5 的情况下有：

$$3x^{14} + 4x^{13} + 2x^{11} +x^9 + x^6 +x^3 +12x^2 +x \equiv 0 \pmod{5} \Leftrightarrow$$

$$3x^{2} + 4x^1 + 2x^{3} + x^1 + x^2 +x^3 +2 x^2 +x \equiv 0 \pmod{5} \Leftrightarrow$$

$$3x^3 + 6x^2 +6x \equiv 0 \pmod{5} \Leftrightarrow x^3 + 2x^2 + 2x \equiv 0 \pmod{5}$$

穷举就容易求解了。

证明题

1

设一个正整数 n 表示为：$$\displaystyle n = \sum_{i=0}^{m}\alpha_i*10^i$$

那么即证明 $$\displaystyle n \equiv 0 \pmod{3} \Leftrightarrow \sum_{i=0}^{m} \alpha_i \equiv 0 \pmod{3}$$

我们知道对任意 i，有：$$10^i \equiv 1 \pmod{3}$$（考虑 $$10^i - 1$$ 与 3 的整除关系）

于是我们有以下等价关系的推导：

$$\displaystyle n = \sum_{i=0}^{m} (\alpha_i *(10^i - 1)) + \sum_{i=0}^{m} \alpha_i \equiv 0\pmod{3} \Leftrightarrow \sum_{i=0}^{m}\alpha_i \equiv 0 \pmod{3}$$

所以题式得证。

2

设 $$f(x) = 0 $$ 有一个整数解 s，即 $$f(s) = 0$$，设 $$t \in \mathbb{Z}_m, s \equiv t \pmod{m}$$

又有：$$f(1), f(2), …, f(m) \not\equiv 0 \pmod{m} \Leftrightarrow f(0), f(1), …f(m-1) \not\equiv 0 \pmod{m}$$

所以我们有以下的推导：

$$\displaystyle f(s) = 0 \overset{弱化}{\Rightarrow} f(s) \equiv 0 \pmod{m} \overset{f(x) 是整系数多项式}{\Rightarrow} f(t) \equiv 0 \pmod{m}$$

注意到 $$t \in \mathbb{Z}_m$$，这与上面的推导是矛盾的，所以 $$f(x) = 0$$ 不存在整数解。

3

我们注意到 $$(m-1)^2 - 1^2 = m(m-2) \equiv 0 \pmod{m}$$

这意味着：$$(m-1)^2 \equiv 1^2 \pmod{m}$$

这违反了完全剩余系两两不同余的构造条件。

4

我们先假定一个不需要证明的定理：

• 模 m 的完全剩余类完备地将 $$\mathbb{Z}$$ 分割为 m 个集合。即 $$\forall n \in \mathbb{Z}, \exist C_r, n\in C_r, r \in \mathbb{Z}_m$$

因为，m 个整数都不属于模 m 的 0 剩余类。

那么总共有 m-1 个完全剩余类，完备地覆盖 m 个整数的取值空间。

根据鸽笼定理，题式成立。

5

考虑设 $$ 1 \le s \le t \le 18$$，

先证明这样的结论：$$s \equiv t \pmod{18} \Leftrightarrow 2^s \equiv 2^t \pmod{27}$$

有以下推导：$$2^s \equiv 2^t \pmod{27} \Leftrightarrow 2^s(2^{t-s} - 1) \equiv 0 \pmod{27} \Leftrightarrow 2^{t-s} \equiv 1 \pmod{27}$$

$$\Leftrightarrow t-s \equiv 0 \pmod{\phi(27)} \Leftrightarrow t \equiv s \pmod{18}$$

所以根据反证法有：$$2, 2^2, 2^3,…,2^{18}$$ 两两不同余，而有可以知道模 27 的完全剩余系大小为 $$\phi(27) = 18$$，因此必有 $$2, 2^2, 2^3,…,2^{18}$$ 构成一个完全剩余系。

6

因为 7 是素数，根据费马小定理 $$a^7 \equiv a \pmod{7}​$$

又因为 $$gcd(a, 3) = 1 \Rightarrow gcd(a, 9) = 1​$$，根据欧拉定理 $$a^{\phi(9)} \equiv 1 \pmod{9}​$$

因此我们有：$$a^7 \equiv a \pmod{7}, a^7 \equiv a \pmod{9} \Rightarrow a^7 \equiv a \pmod{63}$$

7

见解答题第九题。

8

对于欧拉函数的分解 $$\phi(n) = 14 = 2*7$$

我们又知道任意 $$\displaystyle m = p_1^{a_1} p_2^{a_2} … p_s^{a_s}$$

其欧拉函数可以表示成为：$$\displaystyle \phi(m) = m \prod_{i=1}^s (1 - \frac{1}{p_i}) = \frac{m}{p_i p_2 … p_s} \prod_{i=1}^{s}(p_i - 1)​$$ 的形式。

因为 $$p_i​$$ 均为素数，而 $$7+1​$$ 不是素数，$$\displaystyle 7 | \frac{m}{p_1p_2…p_s} \Rightarrow 7|m \Rightarrow 7 \in {p_{i+1} | i \in \mathbb{Z}_s}​$$

有 $$7-1=6$$，从而：$$\displaystyle 3 | \prod_{i=1}^{s}(p_i - 1)$$，且 $$\displaystyle \frac{m}{p_i p_2 … p_s}$$ 总是一个整数，

但 3 并不整除 14，这是矛盾的，因此不存在这样的数字 n 使得 $$\phi(n) = 14$$

9

（1）

对于奇数 $$a = 2k+1, k \ge 1$$，根据欧拉定理，我们有：$$\displaystyle 2^{\phi(a)} \equiv 1 \pmod{a}$$

因为 $$\phi(a) \le a-1$$ 总是成立的，所以 $$\phi(a) = d$$ 即为所求。

（2）

因为我们有：$$\displaystyle 2^{kd_0} - 1 = (2^{d_0} - 1)(\sum_{i=1}^{k} 2^{d_0(k-i)})$$

$$\displaystyle d_0 | h \Leftrightarrow h = kd_0 \Leftrightarrow (2^{d_0} - 1)| (2^h -1)$$

至此，充分性是分显然的： $$(2^{d_0} - 1)|(2^h - 1) \Rightarrow a|(2^h - 1)$$

关于必要性：

如果 $$d_0$$ 与 $$h$$ 有非 1 最大公因数数，那么这与 $$d_0$$ 最小相悖。

如果 $$d_0$$ 与 h 是互素的，根据 2.1 第九题的证明，$$(2^{d_0} - 1) | (2^h -1)$$ 不可能成立。

因此我们用反证法证明了必要性。

10

$$2x^3 - x^2 +3x +11 \equiv 0 \pmod{5} \Leftrightarrow 2x^3 - x^2 +3x -4 \equiv 0 \pmod{5}$$

$$\Leftrightarrow (x-1)(2x^2 + x + 4) \equiv 0 \pmod{5} \Rightarrow x = 1\pmod{5} 或 2x^2 + x +4 \equiv 0 \pmod{5}​$$

$$2x^2 + x +4 \equiv 0 \pmod{5} \Leftrightarrow 2x^2 +x -1 \equiv 0 \pmod{5} \Rightarrow (x+1)(2x - 1) \pmod{5}$$

由此可知三个解分别为 $$x \equiv 1, 3, 4 \pmod{5} ​$$