Lemma 1: 若\((c, a) = 1, c | ab\), 则\(c | b\)
Proof: 直接应用裴蜀定理可得
\[\exists m, n \in \mathbb{Z}, am + cn = 1
\]
等式两边同乘b, 有
\[ abm + bcn = b \newline
\Rightarrow cqm + bcn = b\]
得证
Lemma 2: 若\((c, a) = 1, (c, b) = 1\), 则\((c, ab) = 1\)
Proof: 也是直接用裴蜀定理有
\[am_1 + cn_1 = 1, bm_2 + cn_2 = 1
\]
两式同乘, 有
\[abm_1m_2 + acm_1n_2 + bcn_1m_2 + c^2n_1n_2 = 1 \Rightarrow
abm_1m_2 + c(am_1n_2 + bn_1m_2 + cn_1n_2) = 1
\]
得证(众所周知, 裴蜀定理是有逆定理的)
Lemma 3: 若\(b | a, c | a, (b, c) = 1\), 则\(bc | a\).
Proof: 我们知道
\[\exists q_1, q_2 \in \mathbb{Z}, bq_1 = a, cq_2 = a
\]
和
\[\exists m, n \in \mathbb{Z}, bm + cn = 1
\]
所以
\[a = bq_1 = bq_1(bm + cn) = bcq_2m + bcq_1n
\]
得证
最后我们用一道简单的整除例题来收尾叭!
Q1: 已知\(4b + 2c + d = 32\). 求证: \(8 \ | \ \overline{abcd}\)
Proof: 显然\(\overline{abcd} = 1000a + \overline{bcd}\), 所以只须证\(8 \ | \ \overline{bcd} = 100b + 10c + d\), 观察到题中给的式子形式很好, 我们直接有\(8 \ | \ 4b + 2c + d\)和 $ 8 \ | \ 96b + 8c$, 容易知道
\[a \ | \ b, a \ | \ (b - c) \Rightarrow a \ | \ c
\]
得证