📖 答案：

(1) 是命题，真值为 真(T)（2+3确实等于5）

(2) 不是命题（祈使句，不能判断真假）

(3) 不是命题（疑问句，不能判断真假）

(4) 是命题，真值为 假(F)（目前没有证据表明存在外星人，但这是可以判断真假的陈述句）

💡 命题的判断标准：能判断真假的陈述句。

📖 答案：

(1) 今天下雨 且 刮风

(2) 今天下雨 或 不刮风

(3) 如果今天下雨，那么今天刮风

(4) 今天下雨 当且仅当 今天刮风

💡 牢记联结词的含义：¬(非)、∧(且)、∨(或)、→(蕴含)、↔(等价)。

📖 答案：

设 A = (p → q) ∧ (q → r) → (p → r)，真值表如下：

p | q | r | p→q | q→r | (p→q)∧(q→r) | p→r | A

T | T | T | T | T | T | T | T

T | T | F | T | F | F | F | T

T | F | T | F | T | F | T | T

T | F | F | F | T | F | F | T

F | T | T | T | T | T | T | T

F | T | F | T | F | F | T | T

F | F | T | T | T | T | T | T

F | F | F | T | T | T | T | T

所有赋值下A均为真，所以是永真式。

💡 该公式对应逻辑上的"三段论"推理规则。

📖 答案：

(1) p ∧ (p ∨ q) ⇔ p（吸收律）

(2) p ∨ (p ∧ q) ⇔ p（吸收律）

(3) ¬(p ∨ q) ∨ (¬p ∧ q)

 ⇔ (¬p ∧ ¬q) ∨ (¬p ∧ q)（德摩根律）

 ⇔ ¬p ∧ (¬q ∨ q)（分配律）

 ⇔ ¬p ∧ T ⇔ ¬p（排中律 + 同一律）

💡 吸收律和德摩根律是化简命题公式的常用工具。

📖 答案：

先补充缺失变元：

(p ∧ q) ∨ (¬p ∧ r)

⇔ (p ∧ q ∧ (r ∨ ¬r)) ∨ (¬p ∧ (q ∨ ¬q) ∧ r)

⇔ (p ∧ q ∧ r) ∨ (p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r)

主析取范式：m₇ ∨ m₆ ∨ m₃ ∨ m₁
主合取范式：M₀ ∧ M₂ ∧ M₄ ∧ M₅

💡 主析取范式看真值为1的极小项，主合取范式看真值为0的极大项。

📖 答案：

(1) 假言推理（A→B, A ⇒ B）

(2) 拒取式（A→B, ¬B ⇒ ¬A）

(3) 析取三段论（A∨B, ¬A ⇒ B）

💡 这是自然推理系统P中最常用的三条推理规则。

📖 答案：

证明：

① p → q   前提引入

② q → r   前提引入

③ p → r   ①②假言三段论（HS）

④ ¬r   前提引入

⑤ ¬p   ③④拒取式

所以 ¬p 成立。 □

📖 答案：

设 Bird(x): x是鸟，Fly(x): x会飞，Real(x): x是实数，Math(x): x喜欢数学。

(1) ∀x(Bird(x) → Fly(x))

(2) ∃x(Real(x) ∧ x² = 2)

(3) ¬∀x(Math(x)) 或 ∃x(¬Math(x))

💡 注意全称量词用"→"，存在量词用"∧"连接。

📖 答案：

在 ∀x(P(x) → Q(x, y)) 中：

 x 受 ∀x 约束 → 约束变元

 y 未被量词约束 → 自由变元

在 ∃yR(y, z) 中：

 y 受 ∃y 约束 → 约束变元

 z 未被量词约束 → 自由变元

所以整个公式中：约束变元为 x 和 y，自由变元为 y 和 z。

💡 注意y在不同子公式中可能一个是约束、一个是自由，但整体上属于不同出现。

📖 答案：

(1) ¬∀xP(x) ⇔ ∃x¬P(x)

(2) ¬∃x∀yQ(x, y) ⇔ ∀x∃y¬Q(x, y)

💡 量词否定口诀："全称变存在，存在变全称，谓词加否定"。

📖 答案：

原式：∀x(P(x) → ∃yQ(x, y))

消去蕴含：∀x(¬P(x) ∨ ∃yQ(x, y))

将量词提到前面（两者无约束冲突）：

前束范式：∀x∃y(¬P(x) ∨ Q(x, y))

💡 前束范式的所有量词都在公式最前面，且辖域延伸到公式末尾。

📖 答案：

证明：

① ∀x(P(x) → Q(x))   前提引入

② ∀x(Q(x) → R(x))   前提引入

③ P(y) → Q(y)   ①全称量词消去（∀-）

④ Q(y) → R(y)   ②全称量词消去（∀-）

⑤ P(y) → R(y)   ③④假言三段论（HS）

⑥ ∀x(P(x) → R(x))   ⑤全称量词引入（∀+）

所以结论成立。 □

💡 一阶逻辑推理的关键：先用∀-消去量词，进行命题推理，再用∀+引入量词。

📖 答案：

(1) A ∪ B = {1,2,3,4,5,6,7}

(2) A ∩ B = {4,5}

(3) A − B = {1,2,3}

(4) A ⊕ B = (A−B) ∪ (B−A) = {1,2,3,6,7}

(5) ~A = {6,7,8,9,10}

💡 对称差也可以理解为属于A或B但不同时属于两者的元素。

📖 答案：

用容斥原理：|A∪B| = |A| + |B| − |A∩B|

(1) |A∪B| = 25 + 30 − 10 = 45（人）

(2) 两种都不喜欢 = 50 − 45 = 5（人）

(3) 只喜欢篮球 = 25 − 10 = 15（人）

💡 容斥原理是解决有穷集计数问题的核心工具。

📖 答案：

证明：

A − (B ∪ C)

= A ∩ ~(B ∪ C)  （差的定义）

= A ∩ (~B ∩ ~C)  （德摩根律）

= (A ∩ ~B) ∩ (A ∩ ~C)  （幂等律、交换律、结合律）

= (A − B) ∩ (A − C)  （差的定义）

所以等式成立。 □

💡 集合证明的核心技巧：将差运算转化为交和补运算，再利用集合恒等式进行演算。

📖 答案：

A × B = {(1,a), (1,b), (2,a), (2,b), (3,a), (3,b)}

B × A = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

A × B

=

B × A

💡 笛卡儿积不满足交换律，结果与顺序有关。

📖 答案：

(1) 是自反的：所有1,2,3都有(1,1),(2,2),(3,3) ∈ R

(2) 不是反自反的：反自反要求无任何(x,x) ∈ R，但(1,1),(2,2),(3,3)都在R中

(3) 是对称的：有(1,2)就有(2,1)，其余元素的自反对也满足对称

(4) 不是反对称的：存在(1,2)和(2,1)且1≠2，违反了反对称的条件

(5) 是传递的：检查所有可能的三元组均满足传递性

💡 判断关系性质的关键是找到反例：一个反例即可否定。

📖 答案：

r(R) = R ∪ {(1,1), (2,2), (3,3)}

 = {(1,1), (1,2), (2,2), (2,3), (3,1), (3,3)}

s(R) = R ∪ {(2,1), (3,2), (1,3)}

 = {(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)}

t(R) = R ∪ R² ∪ R³

R² = R∘R = {(1,3), (2,1), (3,2)}

R³ = R²∘R = {(1,1), (2,2), (3,3)}

t(R) = {(1,2), (1,3), (1,1), (2,3), (2,1), (2,2), (3,1), (3,2), (3,3)}

💡 传递闭包 t(R) = ∪Rⁿ (n≥1)，在有限集上总存在某个N使得t(R)=R∪R²∪⋯∪Rᴺ。

📖 答案：

(1) 单射（若2x₁=2x₂，则x₁=x₂）；不是满射（值域为偶数集，奇数没有原像）；不是双射

(2) 单射（x³是严格递增函数）；满射（∀y∈ℝ，∃x=∛y使x³=y）；是双射

(3) 不是单射（f(1)=f(-1)=1但1≠-1）；不是满射（值域为ℕ，但ℕ中的0...等下，ℕ通常不含负整数...f:ℤ→ℕ，值域为{0,1,2,...}，但ℕ包含0时就是满射...）；实际上是满射（∀n∈ℕ，取x=n或x=-n，f(x)=n）

💡 单射：不同输入→不同输出；满射：每个输出都有输入对应。

📖 答案：

f是双射（单射+满射），所以存在逆函数：

f⁻¹: B → A, f⁻¹(a)=1, f⁻¹(b)=2, f⁻¹(c)=3

f∘f⁻¹: B → B, 对于∀y∈B，有 f∘f⁻¹(y) = f(f⁻¹(y)) = y，即恒等函数 I_B

f⁻¹∘f: A → A, 对于∀x∈A，有 f⁻¹∘f(x) = f⁻¹(f(x)) = x，即恒等函数 I_A

💡 双射函数才有逆函数，且 f∘f⁻¹ = I_B，f⁻¹∘f = I_A。

📖 答案：

(1) 满足交换律：a ★ b = a + b + 1 = b + a + 1 = b ★ a

(2) 满足结合律：

 (a ★ b) ★ c = (a + b + 1) ★ c = (a + b + 1) + c + 1 = a + b + c + 2

 a ★ (b ★ c) = a ★ (b + c + 1) = a + (b + c + 1) + 1 = a + b + c + 2

 所以 (a ★ b) ★ c = a ★ (b ★ c)

💡 该运算的单位元是 -1：a ★ (-1) = a + (-1) + 1 = a

📖 答案：

(1) 设单位元为e，则对∀a∈ℤ：a ★ e = a + e + 1 = a

 → e = -1。验证：(-1) ★ a = -1 + a + 1 = a ✓

 单位元为 -1

(2) 设a的逆元为a⁻¹，则 a ★ a⁻¹ = e = -1

 a + a⁻¹ + 1 = -1 → a⁻¹ = -a - 2

 验证：a ★ (-a-2) = a + (-a-2) + 1 = -1 ✓

 每个元素a的逆元为 -a - 2

💡 在代数系统中，不要求运算一定是普通加法或乘法，逆元的定义依赖于具体的运算和单位元。

📖 答案：

(1) 是群：封闭 ✓，结合律 ✓，单位元0 ✓，逆元为相反数 ✓

(2) 不是群：封闭 ✓，结合律 ✓，单位元0 ✓，但除0外其他元素无加法逆元（如1的逆元应为-1，但-1∉ℕ）✗

(3) 是群：封闭 ✓（1×1=1, 1×(-1)=-1, (-i)×i=1等），结合律 ✓，单位元1 ✓，1⁻¹=1, (-1)⁻¹=-1, i⁻¹=-i, (-i)⁻¹=i ✓

💡 群需要验证四条性质：封闭性、结合律、单位元、逆元。

📖 答案：

证明：

(⇒) 设 aᵐ = e。由带余除法，m = qn + r，其中0 ≤ r < n。

aᵐ = a^(qn+r) = (aⁿ)ᵠ · aʳ = eᵠ · aʳ = aʳ = e

因为 r < n 且 n 是使 aⁿ = e 的最小正整数，所以 r = 0，即 n | m。

(⇐) 若 n | m，则 m = kn，aᵐ = a^(kn) = (aⁿ)ᵏ = eᵏ = e。

所以结论成立。□

💡 群的元素阶是群论中最重要的概念之一，与拉格朗日定理密切相关。

📖 答案：
拉格朗日定理的证明思路：

用H的陪集划分G。G被划分为若干个互不相交的左陪集（或右陪集），每个陪集的大小都等于|H|。

设 [G:H] 是H在G中的指数（即不同陪集的个数），则 |G| = [G:H] · |H|，所以|H|整除|G|。

应用：

4阶群：可能子群阶数为 1, 2, 4（1和4是平凡子群，可能有2阶子群）

5阶群：可能子群阶数为 1, 5（只有平凡子群）

因为5是素数，由拉格朗日定理，5阶群只有1阶和5阶子群。

💡 拉格朗日定理是群论中最基本的定理之一，它给出了子群阶与群阶之间的关系。

📖 答案：

(1) 是格：任意两个自然数都有上确界max(a,b)和下确界min(a,b)

(2) 是格：任意两个数的上确界为lcm（最小公倍数），下确界为gcd（最大公约数）

(3) 哈斯图：

    12

   /  \

   4   6

   |   / \

   2  3

  /  \

  1

💡 格要求偏序集中任意两个元素都有唯一的上确界（并）和下确界（交）。

📖 答案：

通过真值表验证所有4种赋值：

x | y | z | y∨z | x∧(y∨z) | x∧y | x∧z | (x∧y)∨(x∧z)

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

0 | 0 | 1 | 1 | 0 | 0 | 0 | 0

0 | 1 | 0 | 1 | 0 | 0 | 0 | 0

0 | 1 | 1 | 1 | 0 | 0 | 0 | 0

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0

1 | 0 | 1 | 1 | 1 | 0 | 1 | 1

1 | 1 | 0 | 1 | 1 | 1 | 0 | 1

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1

两列完全一致，所以分配律成立。✓

💡 布尔代数是计算机逻辑电路设计的数学基础。

📖 答案：

证明：

(⇒) 若 a ≤ b，则 a ∧ b = a（格的吸收性质）。

a ∧ ¬b = (a ∧ b) ∧ ¬b （因为 a ∧ b = a）

= a ∧ (b ∧ ¬b) （结合律）

= a ∧ 0 = 0

(⇐) 若 a ∧ ¬b = 0，则：

a = a ∧ 1 = a ∧ (b ∨ ¬b) = (a ∧ b) ∨ (a ∧ ¬b) = (a ∧ b) ∨ 0 = a ∧ b

所以 a ∧ b = a，由格的等价定义可知 a ≤ b。

所以结论成立。□

💡 布尔代数中的许多性质可以通过将关系问题转化为代数等式来证明。

📖 答案：

(1) P(6,3) = 6 × 5 × 4 = 120

(2) C(8,3) = 8! / (3! × 5!) = (8 × 7 × 6) / (3 × 2 × 1) = 336 / 6 = 56

(3) C(10,7) = C(10,3) = (10 × 9 × 8) / (3 × 2 × 1) = 720 / 6 = 120

💡 组合数公式 C(n,k) = n! / (k!(n−k)!)，利用C(n,k)=C(n,n−k)可以简化计算。

📖 答案：

(1) 有顺序的选法（排列）：P(10,3) = 10 × 9 × 8 = 720（种）

(2) 无顺序的选法（组合）：C(10,3) = 10! / (3! × 7!) = (10×9×8) / (3×2×1) = 120（种）

💡 区分排列与组合的关键在于是否"考虑顺序"。

📖 答案：

证明：

由二项式定理：(x + y)ⁿ = ΣC(n,k)xⁿ⁻ᵏyᵏ (k从0到n)

令 x = 1, y = 1：

(1 + 1)ⁿ = ΣC(n,k) · 1ⁿ⁻ᵏ · 1ᵏ

2ⁿ = ΣC(n,k) （k从0到n）

即 C(n,0) + C(n,1) + C(n,2) + … + C(n,n) = 2ⁿ

证毕。

💡 这个等式的组合意义：n个元素的所有子集个数等于2ⁿ。

📖 答案：

F₂ = F₁ + F₀ = 1 + 0 = 1

F₃ = F₂ + F₁ = 1 + 1 = 2

F₄ = F₃ + F₂ = 2 + 1 = 3

F₅ = F₄ + F₃ = 3 + 2 = 5

💡 Fibonacci数列是递推方程最经典的例子，广泛出现在自然界的各种模式中。

📖 答案：

特征方程：x² − 3x + 2 = 0

因式分解：(x − 1)(x − 2) = 0

特征根：r₁ = 1, r₂ = 2

通解形式：aₙ = A · 1ⁿ + B · 2ⁿ = A + B · 2ⁿ

代入初始条件：

n = 0：A + B = 2

n = 1：A + 2B = 3

解方程组得：A = 1, B = 1

所以 aₙ = 1 + 2ⁿ

验证：a₂ = 1 + 4 = 5 = 3a₁ − 2a₀ = 9 − 4 = 5 ✓

💡 齐次线性递推方程的标准解法：特征方程→特征根→通解→待定系数。

📖 答案：

非齐次递推方程：Tₙ = 2Tₙ₋₁ + 1

齐次解：Tₙ⁽ʰ⁾ = A · 2ⁿ

特解形式：设 Tₙ⁽ᵖ⁾ = c（常数），代入得 c = 2c + 1 → c = −1

通解：Tₙ = A · 2ⁿ − 1

代入初始条件 T₁ = 1：A · 2¹ − 1 = 1 → 2A = 2 → A = 1

所以 Tₙ = 2ⁿ − 1

验证：T₁=1, T₂=3, T₃=7, T₄=15, ...

💡 64个圆盘需要 2⁶⁴ − 1 ≈ 1.84 × 10¹⁹ 步，假设每秒移动一次，需要约5849亿年！

📖 答案：

C₀ = 1

C₁ = C₀C₀ = 1 × 1 = 1

C₂ = C₀C₁ + C₁C₀ = 1×1 + 1×1 = 2

C₃ = C₀C₂ + C₁C₁ + C₂C₀ = 1×2 + 1×1 + 2×1 = 5

C₄ = C₀C₃ + C₁C₂ + C₂C₁ + C₃C₀ = 1×5 + 1×2 + 2×1 + 5×1 = 14

通项公式：Cₙ = (1/(n+1)) · C(2n,n)

💡 Catalan数出现在许多组合问题中：n对括号的合法匹配数、n个结点的不同二叉树数等。

📖 答案：

(1) 总度数 = 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 = 36

(2) 由握手定理 Σd(v) = 2|E|，得：

 2|E| = 36 → |E| = 18（条边）

💡 握手定理是图论最基本的定理，它告诉我们所有顶点的度数之和等于边数的两倍。

📖 答案：

(1) 错误。一个n个顶点的简单图中，每个顶点的度数取值范围是0到n−1。但度数为0的顶点（孤立点）和度数为n−1的顶点不能同时出现（度数为n−1说明与所有其他顶点相连，而度数为0说明不与任何顶点相连，矛盾）。对于5个顶点，可能的度数为{0,1,2,3,4}，但0和4不能共存，所以最多有4种不同的度数，无法使5个顶点度数各不相同。

(2) 正确。5个顶点的圈（5-cycle）中每个顶点的度数都是2。

💡 度数序列的可图化问题需要满足握手定理以及一些必要约束条件。

📖 答案：

(1) 存在欧拉回路（所有顶点偶数度 → 可以一笔画回到起点）

(2) 存在欧拉通路但不存欧拉回路（两个奇度顶点为起点和终点，欧拉一笔画）

(3) 既无欧拉回路也无欧拉通路（多于2个奇度顶点无法一笔画）

💡 欧拉图判定定理：连通图有欧拉回路⇔所有顶点度数均为偶数；有欧拉通路⇔恰有0或2个奇度顶点。

📖 答案：
Dirac定理：若n≥3且简单图G中每个顶点的度数 ≥ n/2，则G是哈密顿图（存在哈密顿回路）。
应用：n=6，n/2=3，每个顶点度数≥3，满足Dirac定理条件。

所以一定是哈密顿图。

💡 注意：Dirac定理是充分条件而非必要条件。即使不满足Dirac定理，图仍可能是哈密顿图。

📖 答案：

树的性质：|E| = |V| − 1 = 10 − 1 = 9（条边）

设度数为3的顶点有x个，则总顶点数：3 + 2 + x = 10 → x = 5

验证度数之和：3×1 + 2×2 + 5×3 = 3 + 4 + 15 = 22

握手定理：总度数 = 2|E| = 2 × 9 = 18？

等等，这里有矛盾：22 ≠ 18！

重新计算：3个度1 + 2个度2 + 5个度3 = 3 + 4 + 15 = 22，但2|E|=18。

矛盾说明数据有误。设度数为3的顶点有 x 个：

总顶点数：3 + 2 + x = 5 + x = 10 → x = 5

总度数：3×1 + 2×2 + 5×3 = 3 + 4 + 15 = 22

总边数 = 22/2 = 11，但 n=10 时边数应为 9。

数据不一致。正确解法：

设度3的顶点有 x 个，则：3 + 2 + x = 10 → x = 5

总度数 = 3 + 4 + 5×3 = 22，边数 = 11。

但树要求边数 = 9，所以这样的树不存在。

💡 检查树的存在性不仅要满足树的性质 |E|=|V|−1，还要满足握手定理 Σd(v)=2|E|。

📖 答案：

Prim算法步骤（从A开始）：

Step 1: A → 当前集合{A}，最小边 AC=2，加入C → {A,C}，权值和=2

Step 2: 从{A,C}出发，可选边：AB=4, BC=1, CD=3, CE=6，最小边 BC=1，加入B → {A,B,C}，权值和=3

Step 3: 从{A,B,C}出发，可选边：AB=4(已连), AC=2(已连), BC=1(已连), BD=5, CD=3, CE=6，最小边 CD=3，加入D → {A,B,C,D}，权值和=6

Step 4: 从{A,B,C,D}出发，可选边：DE=4, CE=6，最小边 DE=4，加入E → {A,B,C,D,E}，权值和=10

最小生成树边集：AC(2), BC(1), CD(3), DE(4)，总权值 = 10

💡 Prim算法每一步从未处理的顶点中选择与已选集合距离最近的顶点加入。

📖 答案：

由欧拉公式：n − m + r = 2

代入 n=6, m=10：

6 − 10 + r = 2

r = 2 + 4 = 6（个面）

💡 欧拉公式 n − m + r = 2 是平面图理论中最重要的公式之一。

📖 答案：

证明（反证法）：

假设K₅是平面图。K₅有 n=5, m=10。

对于简单平面图，每个面至少由3条边围成，每条边至多属于两个面，因此有：

3r ≤ 2m → r ≤ 2m/3 = 20/3 ≈ 6.67

代入欧拉公式：n − m + r = 2 → 5 − 10 + r = 2 → r = 7

但 r = 7 > 6.67，矛盾！

所以K₅不是平面图。

💡 K₅和K₃,₃是图示性的"非平面图"，所有非平面图都包含它们的细分（Kuratowski定理）。

📖 答案：

由四色定理：任何平面图最多需要4种颜色即可保证相邻区域不同色。

最少：如果8个区域互不相邻（例如都是孤立的），则1种颜色就足够了。

最多：如果8个区域两两相邻（构成完全图K₈），但K₈不是平面图。作为平面图，最多的情况是某些区域互相邻接...例如4个区域两两相邻需要4种颜色。但任何平面图都可用4种颜色着色。

所以：最少 1种，最多 4种。

💡 四色定理是图论中最著名的定理之一，也是第一个借助计算机证明的数学定理。

📖 答案：

用增广路径法（匈牙利算法）求最大匹配：

初始匹配 M = ∅

① 选x₁，匹配y₁ → M = {(x₁, y₁)}

② 选x₂，y₁已被占，找增广路径：x₂→y₁→x₁→y₂

 增广路径存在，更新匹配：M = {(x₂, y₁), (x₁, y₂)}

③ 选x₃，y₂已被占，找增广路径：x₃→y₂→x₁→y₁→x₂→y₃

 增广路径存在，更新匹配：M = {(x₃, y₂), (x₁, y₁), (x₂, y₃)}

最大匹配：{(x₁, y₁), (x₂, y₃), (x₃, y₂)}，大小为3（完美匹配）

💡 二部图的最大匹配可以通过不断寻找增广路径来扩大匹配，直到不存在增广路径为止。

📖 答案：

252 ÷ 105 = 2 余 42

105 ÷ 42 = 2 余 21

42 ÷ 21 = 2 余 0

gcd(252, 105) = 21

💡 欧几里得算法：反复用较大数除以较小数，直到余数为0，最后的除数就是最大公约数。

📖 答案：

(1) 17 − 5 = 12，12能被12整除 → 成立 ✓

(2) 23 − 3 = 20，20能被5整除 → 成立 ✓

(3) 100 − 0 = 100，100能被25整除 → 成立 ✓

(4) 35 − 1 = 34，34不能被7整除 → 不成立 ✗

💡 a ≡ b (mod m) 的含义是 m | (a−b)。

📖 答案：

方法一（试除法）：依次尝试 x = 0, 1, 2, ...

x=0: 5×0=0≡0≠3

x=1: 5×1=5≡5≠3

x=2: 5×2=10≡3 ✓

所以 x ≡ 2 (mod 7)

方法二（求逆元）：5在模7下的逆元是3（因为5×3=15≡1 mod 7）

两边同乘3：x ≡ 3×3 = 9 ≡ 2 (mod 7)

解为 x ≡ 2 (mod 7)，即 x = 7k + 2 (k ∈ ℤ)

💡 解一次同余方程 ax ≡ b (mod m) 的关键是求a在模m下的逆元（前提是gcd(a,m)=1）。

📖 答案：

7是素数，由费马小定理：3^(7−1) ≡ 3⁶ ≡ 1 (mod 7)

2024 ÷ 6 = 337 余 2

所以 3²⁰²⁴ = 3^(6×337 + 2) = (3⁶)^337 × 3² ≡ 1^337 × 9 ≡ 2 (mod 7)

3²⁰²⁴ mod 7 = 2

💡 费马小定理 a^(p−1) ≡ 1 (mod p) 是简化大指数模运算的利器。

📖 答案：

12 = 2² × 3

φ(12) = 12 × (1 − 1/2) × (1 − 1/3) = 12 × 1/2 × 2/3 = 4

由欧拉定理：5^φ(12) ≡ 5⁴ ≡ 1 (mod 12)（因为gcd(5,12)=1）

验证：5² = 25 ≡ 1 (mod 12)，所以 5⁴ = (5²)² ≡ 1² = 1 (mod 12) ✓

欧拉定理成立。

💡 欧拉定理 a^φ(m) ≡ 1 (mod m) 是费马小定理的推广，其中φ(m)是欧拉函数。

📖 答案：

(1) n = p × q = 11 × 13 = 143

 φ(n) = (p−1)(q−1) = 10 × 12 = 120

(2) 求d使得 7d ≡ 1 (mod 120)，即 7d = 120k + 1

 用扩展欧几里得算法：7 × 17 + 120 × (−1) = 119 − 120 = −1

 7 × (−17) + 120 × 1 = −119 + 120 = 1

 所以 d ≡ −17 ≡ 103 (mod 120)

 验证：7 × 103 = 721 = 6 × 120 + 1 ✓

 私钥 d = 103

(3) 密文 c = 5⁷ mod 143

 5² = 25, 5⁴ = 25² = 625 mod 143 = 625 − 4×143 = 625 − 572 = 53

 5⁷ = 5⁴ × 5² × 5¹ = 53 × 25 × 5 = 53 × 125 = 6625

 6625 mod 143 = 6625 − 46×143 = 6625 − 6578 = 47

(4) 解密：m = 47¹⁰³ mod 143

 由欧拉定理，47^φ(143) = 47¹²⁰ ≡ 1 (mod 143)

 47¹⁰³ = 47^(120−17) = 47¹²⁰ × 47^(−17) ≡ 1 × (47⁻¹)¹⁷ (mod 143)

 实际上我们只需要验证 47⁷ mod 143 = 5 即可（因为RSA的加解密互为逆运算）。

 直接验证较复杂，但由RSA的正确性定理保证 m ≡ cᵈ ≡ (mᵉ)ᵈ ≡ m (mod n)。

 所以解密后得到 m = 5 ✓

💡 RSA的安全性基于大整数分解的困难性：已知n分解出p和q是计算上不可行的。

📖 答案：

证明：

情况1：若 p | a，则 a ≡ 0 (mod p)，aᵖ ≡ 0 (mod p)，所以 aᵖ ≡ a (mod p) ✓

情况2：若 p ∤ a，则 gcd(a, p) = 1，由费马小定理：a^(p−1) ≡ 1 (mod p)

 两边同乘a：aᵖ ≡ a (mod p) ✓

所以对于任意整数a，aᵖ ≡ a (mod p) 成立。 □

💡 这是一个常用的费马小定理的等价形式，不要求gcd(a,p)=1的额外条件。

📖 答案：

15 = 3 × 5，由中国剩余定理，x² ≡ 1 (mod 15) 等价于方程组：

x² ≡ 1 (mod 3) 且 x² ≡ 1 (mod 5)

模3：x² ≡ 1 (mod 3) → x ≡ ±1 (mod 3)，即 x ≡ 1 或 2 (mod 3)

模5：x² ≡ 1 (mod 5) → x ≡ ±1 (mod 5)，即 x ≡ 1 或 4 (mod 5)

四种组合：

(x≡1 mod 3, x≡1 mod 5) → x ≡ 1 (mod 15)

(x≡1 mod 3, x≡4 mod 5) → x ≡ 4 (mod 15)

(x≡2 mod 3, x≡1 mod 5) → x ≡ 11 (mod 15)

(x≡2 mod 3, x≡4 mod 5) → x ≡ 14 (mod 15)

验证：1²=1, 4²=16≡1, 11²=121≡1, 14²=196≡1 (mod 15) ✓

解为 x ≡ 1, 4, 11, 14 (mod 15)

💡 注意模合数时，二次同余方程的解通常多于2个！