算法导论31.1习题

dbywsc / 2024-10-10 / 原文

31.1-1

证明：若$a > b > 0$，$c = a + b$，则$c \bmod a = b$。

设$c \bmod a = x$,则$c = ka + x (k \in \mathbb{Z}) = a + b$.

当$k = 1$时: $c = a + x = a + b$,所以$x = b$.

当$k > 1$时:因为$a > b > 0$,$c = a + b$,所以$\lfloor c / a \rfloor \geq 2$.所以$c = ka + x = a + b \geq 2a + x$,因此$b \geq a + x > a$,与$a > b > 0$不符.

综上,$c \bmod a = b$.

31.1-2

证明有无穷多个素数(提示:证明素数$p_1, p_2, ... , p_k$都不能整除$(p_1p_2...p_k) + 1$.)

假设存在有限个质数$p_i(i = 1, 2, ... , k)$,且$p_i(i = 1, 2, ..., k) \mid p$,所以$p$不是质数.

对于每一个质数$p_i$有: $p \bmod p_i = 1$,所以$p_i(i = 1, 2, ..., k) \nmid p$,所以$p$是质数,推出矛盾.

所以有无穷多个质数.

31.1-3

证明:如果$a \mid b$且$b \mid c$，则$a \mid c$

因为$b \mid c$, 所以$c = kb(k_1 \in \mathbb{Z})$.又因为$a \mid b$, 所以$b = k_2a(k_2 \in \mathbb{Z})$.所以$c = k_1(k_2a) = k_1k_2a$且$k_1k_2 \in \mathbb{Z}$.

所以$a \mid k_1k_2a$即$a \mid c$.

31.1-4

证明:如果p是素数且$0 < k < p$,则$\gcd(k, p) = 1$

设$\gcd(k, p) = a$,因为$p$是质数,所以$a = 1$或$a = p$,又因为$k < p$,所以$a = 1$,即$\gcd(k, p) = 1$.

31.1-5

对于任意整数$n, a$和$b$,如果$n \mid ab$且$\gcd(a, n) = 1$,则$n \mid b$

因为$n \mid ab$,所以$ab = kn(k \in \mathbb{Z})$

所以$$\gcd(a, n) = \gcd(a, kn / k) = 1 \Rightarrow k\gcd(a, kn / k) = \gcd(ka, kn) = k$$

\[\Rightarrow \gcd(ka, ab) = k \Rightarrow a\gcd(k, b) = k \]

所以$ab = kn \Rightarrow ab = a\gcd(k, b)n$

\[\Rightarrow b = \gcd(k, b) n \Rightarrow b / n = \gcd(k, b) \in \mathbb{Z}$$. 所以$n \mid b$\]