高中數學擴充套件/素數/解答

高中數學擴充套件

---

補充章節 — 素數與模運算 — 邏輯

數學證明 — 集合論與無限過程 — 計數與生成函式 — 離散機率

矩陣 — 進一步模運算 — 數學規劃 — 馬爾可夫鏈

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 沒有逆元