《什么是数学 》习题 第一章 补充

从 $p_1=2, p_2=3$开始，进行这种构造，找出5个以上的素数。

• $p_3 = 2 * 3 + 1 = 7$
• $p_4 = 2 * 3 * 7 + 1 = 43$
• $p_5 = 2 * 3 * 7 * 43 + 1 = 1807$
• $p_6 = 2 * 3 * 7 * 43 * 1807 + 1 = 3263443$
• $p_7 = 2 * 3 * 7 * 43 * 1807 * 3263443 + 1 = 10650056950807$

找出整数$z$被$13$整除的规则

对于模$13$同余，我们有： $10\equiv-3,10^2\equiv9,10^3\equiv12,10^4\equiv3,10^5\equiv4,10^6\equiv1,10^7\equiv-3$ 再接下去的余数则是上面的重复，因此 $z$ 被13整除必须而且只须表达式 $z= a_0 - 3a_1 + 9a_2 + 12a_3 + 3a_4 + 4a_5 + a_6 - 3a_7 + \cdots$ 被$13$整除。

说明下面的消去律对素数的模的同余式成立：

如果 $ab\equiv ac$ ，且 $a \not\equiv0$ ，则 $b \equiv c$ .

$ab - ac \equiv 0$

$a(b - c) \equiv 0$

因为 $a \not\equiv0$

所以 $b - c \equiv 0$

所以 $b \equiv c$

分配律证明：

$$\begin{aligned} ab &= ac + rd \\ ab - ac &= rd \\ a(b-c) &= rd \\ a(b-c) &\equiv 0 \\ \end{aligned}$$

习题

0和6之间哪一个数和乘积$11*18*2322*13*19$模7同余？

$11 ≡ 4(mod 7)$ $18 ≡ 4(mod 7)$ $2322 ≡ 5(mod 7)$ $13 ≡ 6(mod 7)$ $13 ≡ 5(mod 7)$ $111823221319 ≡ 4 * 4 * 5 * 6 * 5 (mod 7)$ $4 * 4 * 5 * 6 * 5 ≡ 2400(mod 7) ≡ 6(mod 7)$

0和12之间哪一个数和乘积$371117192329*113$模13同余？

$3 ≡ 3(mod 13)$ $7 ≡ 7(mod 13)$ $11 ≡ 11(mod 13)$ $17 ≡ 4(mod 13)$ $19 ≡ 6mod 13)$ $23 ≡ 10(mod 13)$ $29 ≡ 3(mod 13)$ $113 ≡ 9(mod 13)$ $371117192329*113 ≡ 3 * 7 * 11 * 4 * 6 * 10 * 3 * 9 (mod 13)$ $3 * 7 * 11 * 4 * 6 * 10 * 3 * 9 ≡ 1496880(mod 13)≡ 8(mod 13)$

0和4之间哪一个数与$1 + 2 + 2^2 + \cdots + 2^{19}$的和模5同余？

设2的指数为 $k(k>=0)$ 。 $2^0 ≡ 1(mod 5)$ $2^1 ≡ 2(mod 5)$ $2^2 ≡ 4(mod 5)$ $2^3 ≡ 3(mod 5)$ $2^4 ≡ 1(mod 5)$ 接下来随着k的增长余数是重复，所以k模4观察。 若 $k ≡ 0(mod 4)$ ，则 $2^k = 2 ^{4n}=16^n,(n>=0)$ 。因为 $16 ≡ 1(mod 5)$ ，所以 $16^n ≡ 1(mod 5)$ ，所以 $2^k ≡ 1(mod 5)$ 。 若 $k ≡ 1(mod 4)$，则 $2^k = 2 ^{4n+1}=216^n,(n>=0)$ 。因为 $16 ≡ 1(mod 5)$ ，所以 $216^n ≡ 2(mod 5)$ ，所以 $2^k ≡ 2(mod 5)$ 。 若 $k ≡ 2(mod 4)$ ，则 $2^k = 2 ^{4n+2}=416^n,(n>=0)$ 。因为 $16 ≡ 1(mod 5)$ ，所以 $416^n ≡ 4(mod 5)$ ，所以 $2^k ≡ 4(mod 5)$ 。 若 $k ≡ 3(mod 4)$ ，则 $2^k = 2 ^{4n+3}=816^n,(n>=0)$ 。因为 $16 ≡ 1(mod 5)$ ，所以 $816^n ≡ 3(mod 5)$ ，所以 $2^k ≡ 3(mod 5)$ 。 $1 + 2 + 2^2 + \cdots + 2^{19} = 1 + 2 + 4 + 3 + \cdots + 3(mod 5) = 5 * (1 + 2 + 4 + 3)(mod 5) = 0(mod 5)$

费马定理

用类似的计算表明：$2^8≡1(mod17); 3^8≡-1(mod17); 3^{14}≡-1(mod29);2^{14}≡-1(mod29);4^{14}≡1(mod29);5^{14}≡1(mod29);$

$$\begin{aligned} 2^1 ≡ 2(mod17) \\ 2^2 ≡ 4(mod17) \\ 2^5 ≡ 15(mod17) \\ 2^6 ≡ 13(mod17) \\ 2^8 ≡ 52(mod17) ≡1(mod17) \end{aligned}$$ $$\begin{aligned} 3^1 ≡ 3(mod17) \\ 3^2 ≡ 9(mod17) \\ 3^3 ≡ 10(mod17) \\ 3^4 ≡ 13(mod17) \\ 3^5 ≡ 5(mod17) \\ 3^8 ≡ 50(mod17) ≡-1(mod17) \end{aligned}$$ $$\begin{aligned} 3^2 ≡ 9(mod29) \\ 3^3 ≡ -2(mod29) \\ 3^4 ≡ -6(mod29) \\ 3^8 ≡ 7(mod29) \\ 3^{10} ≡ 5(mod29) \\ 3^{14} ≡ -6*5(mod29) ≡1(mod29) \end{aligned}$$ $$\begin{aligned} 2^2 ≡ 4(mod29) \\ 2^4 ≡ 16(mod29) \\ 2^5 ≡ -3(mod29) \\ 2^{10} ≡ 9(mod29) \\ 2^{12} ≡ 7(mod29) \\ 2^{14} ≡-1(mod29) \end{aligned}$$ $$\begin{aligned} 2^{14} ≡ -1(mod29) \\ 4^{14} = 2^{15} = 2^{14} * 2^{14} = 1(mod29) \end{aligned}$$ $$\begin{aligned} 5^2 ≡ -4(mod29) \\ 5^4 ≡ 16(mod29) \\ 5^5 ≡ -7(mod29) \\ 5^{10} ≡ -9(mod29) \\ 5^{12} ≡ 7(mod29) \\ 5^{14} ≡1(mod29) \end{aligned}$$

对$p=5,7,11,17,23$，用不同的$a$值来核对费马定理。

$$3^4 = 3^2*3^2 ≡ 4 * 4 (mod 5) ≡ 1(mod5)$$ $$\begin{aligned} 4^2 ≡ 2 (mod 7) \\ 4^4 ≡ 4 (mod 7) \\ 4^6 ≡ 1(mod7) \end{aligned}$$ $$\begin{aligned} 3^2 ≡ -2 (mod 11) \\ 3^4 ≡ 4 (mod 11) \\ 3^8 ≡ 5(mod11) \\ 3^{10} ≡ 1(mod11) \\ \end{aligned}$$ $$\begin{aligned} 5^2 ≡ 8 (mod 17) \\ 5^4 ≡ -4 (mod 17) \\ 5^8 ≡ -1(mod17) \\ 5^{16} ≡ 1(mod17) \end{aligned}$$ $$\begin{aligned} 7^2 ≡ -3 (mod 23) \\ 7^4 ≡ 9 (mod 23) \\ 7^6 ≡ -4(mod23) \\ 7^{12} ≡ 16(mod23) \\ 7^{14} ≡ -2(mod23) \\ 7^{16} ≡ -6(mod23) \\ 7^{22} ≡ 1(mod23) \end{aligned}$$

证明一个一般的定理：使$a^e≡1 \pmod p$的最小正整数$e$必须是$p-1$的一个因子（提示：用$e$除$p-1$得到$p-1=ke+r$，这里$0 \leqq r<e$，并且用$a^{p-1}≡a^e≡1 \pmod a$这一事实）

$$\begin{aligned} \because a^e≡1 \pmod p \\ \therefore a^{ke} ≡ 1 \pmod p \\ \because a^{p-1} ≡ 1 \pmod p \\ \therefore a^{ke+r} ≡ 1 \pmod p \\ \therefore a^{ke}*a^r ≡ 1 \pmod p \\ \therefore a^r ≡ 1 \pmod p \end{aligned}$$

根据条件，使 $a^e≡1 \pmod p$的最小正整数为$e$ ，且$0 \leqq r<e$ ，因此 $r$不可能为正整数。故能满足$a^r ≡ 1 \pmod p$的 $r$ 的唯一取值为0。因此 $p-1 = ke$，也即 $e$ 为 $p-1$ 的一个因子。

二次剩余

$6^2 = 36 ≡ 13 \pmod {23}$，$23$是不是二次剩余$\pmod {13}$?

$$\begin{aligned} \because [\cfrac {23-1} 2]*[\cfrac {13-1} 2] 是偶数且13是二次剩余 \\ \therefore 23是二次剩余 \\ 6^2 = 36 ≡ 23 \pmod {13} \end{aligned}$$

我们已看到$x^2≡(p-x)\pmod p$，说明这是数$1^2,2^2,3^2,\cdots,(p-1)^2$中间仅有的同余关系。