高中数学扩展/素数/解答

高中数学扩展

---

补充章节 — 素数与模运算 — 逻辑

数学证明 — 集合论与无限过程 — 计数与生成函数 — 离散概率

矩阵 — 进一步模运算 — 数学规划 — 马尔可夫链

HSME
内容
素数
模运算
问题与项目
习题集
项目
解答
练习解答
习题集解答
杂项
定义表
完整版
PDF 版本

HSE 素数|素数与模运算

目前，主要集中在编写每个章节的主要内容。因此，此练习解答部分可能已过时，并且看起来杂乱无章。

如果您有任何问题，请在“讨论部分”留言，或联系作者或任何主要贡献者。

因式分解练习

对以下数字进行因式分解。（注意：我知道您不需要这样做，这只是为了那些好奇的人）

1. 13 是素数
2. $26=13\cdot 2$
3. 59 是素数
4. $82=41\cdot 2$
5. 101 是素数
6. $121=11\cdot 11$
7. $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

递归因式分解练习

使用递归进行因式分解。

1. $45=3\cdot 3\cdot 5$
2. $4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5$
3. $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

素数筛法练习

1. 使用上述结果，在知道 5 是下一个素数的情况下，快速算出以下表格中需要划去的数字

${\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}$

下一个素数是 5。因为 5 是一个未标记的素数，并且 5 * 5 = 25，所以划去 25。同样，7 是一个未标记的素数，并且 5 * 7 = 35，所以划去 35。但是，5 * 11 = 55，太大，所以标记 5 为素数，并继续到 7。唯一可以划去的足够小的数字是 7 * 7，等于 49。您不能再高了。

2. 找到 200 以下的所有素数。

这里不会详细说明该方法，因为它太长了。但是，200 以下的所有素数是

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

模运算练习

1. $(-1)\cdot (-5)\mod {11}=5$或者，-1 = 10，-5 = 6：10 × 6 = 60 = 5&times 11 + 5 = 5
2. $3\cdot 7\mod {11}=21=10$
3. $2^{1}=2,2^{2}=4,2^{3}=8,2^{4}=16=5$
   $2^{5}=32=10,2^{6}=64=9,2^{7}=128=7$
   $2^{8}=256=3,2^{9}=512=6,2^{10}=1024=1$
   更简单的列表：2, 4, 8, 5, 10, 9, 7, 3, 6, 1
   请注意，实际上并没有必要
   计算 $2^{10}$ 来求得 $2^{10}$ 模 11 的余数。
   如果你知道 $2^{9}$ 模 11 的余数为 6。
   你可以求得 $2^{10}$ 模 11 的余数为 (2*($2^{9}$ 模 11)) 模 11 = 2*6 模 11 = 12 模 11 = 1。
   我们可以注意到，2⁹ = 6 且 2¹⁰ = 1，我们可以轻松计算 6²： 6² = 2¹⁸ = 2^8 = 3。或者使用上面的方法
   $6^{1}=6,6^{2}=36=3,6^{3}=6*3=18=7,$
   $6^{4}=6*7=42=9,6^{5}=6*9=54=10,6^{6}=6*10=60=5,$
   $6^{7}=6*5=30=8,6^{8}=6*8=48=4,6^{9}=6*4=24=2,6^{10}=6*2=12=1.$
   更简单的列表：6, 3, 7, 9, 10, 5, 8, 4, 2, 1。
4. 0² = 0, 1² = 1, 2² = 4, 3² = 9,
   4² = 16 = 5, 5² = 25 = 5, 6² = 36 = 3, 7² = 49 = 3,
   8² = 64 = 9, 9² = 81 = 4, 10² = 100 = 1
   更简单的列表：0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1
   因此${\sqrt {4}}=2{\mbox{ and }}{\sqrt {4}}=9$
5. x² = -2 = 9
   只需查看上面的列表，你就会发现${\sqrt {-2}}=8{\mbox{ and }}{\sqrt {-2}}=3$

除法和逆元练习

1.

$x=2^{-1}=4$

$x=3^{-1}=5$

$x=4^{-1}=2$

$x=5^{-1}=3$

$x=6^{-1}=6$

$x=7^{-1}=0^{-1}$ 所以没有逆元

2. $x={\frac {28}{7}}=4\ \ {\mbox{(mod 29)}}$

$7^{-1}=25\ \ {\mbox{(mod 29)}}$

$x=28\cdot 25=4\ \ {\mbox{(mod 29)}}$

3.

$x=5^{99}\times (40+{\frac {1}{3}})\ \ {\mbox{(mod 11)}}$

$x=5^{99}\times (40+4)\ \ {\mbox{(mod 11)}}$

$x=5^{99}\times 0\ \ {\mbox{(mod 11)}}$

$x=0\ \ {\mbox{(mod 11)}}$

4.

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
	1																		mod 2
	1	2																	mod 3
	1		3																mod 4
	1	3	2	4															mod 5
	1				5														mod 6
	1	4	5	2	3	6													mod 7
	1		3		5		7												mod 8
	1	5		7	2		4	8											mod 9
	1		7				3		9										mod 10
	1	6	4	3	9	2	8	7	5	10									mod 11
	1				5		7				11								mod 12
	1	7	9	10	8	11	2	5	3	4	6	12							mod 13
	1		5		3				11		9		13						mod 14
	1	8		4			13	2			11		7	14					mod 15
	1		11		13		7		9		3		5		15				mod 16
	1	9	6	13	7	3	5	15	2	12	14	10	4	11	8	16			mod 17
	1				11		13				5		7				17		mod 18
	1	10	13	5	4	16	11	12	17	2	7	8	3	15	14	6	9	18	mod 19

互质和最大公约数练习

1.

1.

较小	较大
5050	5051
1	5050
0	1

5050 和 5051 互质

2.

较小	较大
59	78
19	59
2	19
1	2
0	1

59 和 79 互质

3.

较小	较大
111	369
36	111
3	36
0	3

111 和 369 不互质

4.

较小	较大
2021	4032
2011	2021
10	2011
1	10
0	1

2021 和 4032 互质

2. 我们首先计算所有组合的最大公约数

较小	较大
15	510
0	15

较小	较大
15	375
0	15

较小	较大
375	510
135	375
105	135
30	105
15	30
0	15

任何组合的最大公约数都是 15，所以三个数的最大公约数是 15。

丢番图方程练习

1.

${\begin{matrix}216x&=&1+816b\\216c&=&1+168b\\48c&=&1+168d\\48e&=&1+24d\\24e&=&1+24f\\\end{matrix}}$

没有解，因为永远不可能变成整数。

2.

${\begin{matrix}42x&=&7+217b\\42c&=&7+7b\\7c&=&0+7d\\\end{matrix}}$

我们选择 d=1，然后 x=26。

3.

(a)

较小	较大	PQ
33	101	3
2	33	16
1	2	2
0	1

		3	16	2
0	1	3	49	101	1	0	1	16	33

(b) 待补充

4.

(a)

较小	较大	PQ
17	317	18
11	17	1
6	11	1
5	6	1
1	5	5
0	1

		18	1	1	1	5
0	1	18	19	37	56	317	1	0	1	1	2	3	17

(b) 待补充

中国剩余定理练习题

1.

${\begin{matrix}3x&\equiv &5{\pmod {14}}\\x&\equiv &11{\pmod {14}}\\x&=&11+14a\\2x&=&2(11+14a)&\equiv &-3{\pmod {17}}\\&&22+28a&\equiv &-3{\pmod {17}}\\&&11a&\equiv &-8{\pmod {17}}\\&&a&=&7+17b\\x&=&11+14(7+17b)&\equiv &6{\pmod {15}}\\&=&109+238b&\equiv &6{\pmod {15}}\\&=&4+13b&\equiv &6{\pmod {15}}\\&=&13b&\equiv &2{\pmod {15}}\\&&b&\equiv &14{\pmod {15}}\\&&b&=&14+15c\\x&=&109+238(14+15c)\\x&=&3441+3570c\end{matrix}}$

问题 1

证明“可被3整除的判定法则”适用于任何三位数。（提示：将一个三位数表示为 100a + 10b + c，其中 a、b 和 c 为 ≥ 0 且 < 10 的数）

解答 1 任何三位整数 x 可以表示如下

x = 100a + 10b + c

其中 a、b 和 c 是介于 0 和 9（包含 0 和 9）之间的正整数。现在

$x\equiv 100a+10b+c\equiv a+b+c{\pmod {3}}$

$x\equiv 0{\pmod {3}}$

当且仅当 a + b + c = 3k，其中 k 为某个整数。而 a、b 和 c 是 x 的各个数字。

问题 2

“一个数可被 9 整除当且仅当其各位数字之和可被 9 整除。” 对还是错？ 判断 89、558、51858 和 41857 是否可被 9 整除。验证你的答案。

解答 2 该陈述是正确的，可通过类似问题 1 的方法进行证明。

问题 4

在上面的数字表格上应用了素数筛法。请注意，2 和 5 正下方所有的数字都被划掉了。构建一个从 1 到 60 的矩形数字网格，使得在对其应用素数筛法之后，3 和 5 正下方所有的数字都被划掉。该网格的宽度是多少？

解答 4 该网格的宽度应该是 15 或 15 的倍数。

问题 6

证明 n - 1 关于模 n 的逆元是其本身。

解答 6

(n - 1)² = n² - 2n + 1 = 1 (mod n)

或者

(n - 1)² = (-1)² = 1 (mod n)

问题 7

证明 10 关于模 15 没有逆元。

解答 7 假设 10 关于模 15 有逆元 x，

10x = 1 (mod 15)

2×5x = 1 (mod 15)

5x = 8 (mod 15)

5x = 8 + 15k

其中 k 为某个整数

x = 1.6 + 3k

但现在 x 不是一个整数，因此 10 没有逆元