证明：若a、b两数互质，a必定与ak+b 互质

假设取任意两个不同的整数:

$\begin{align*}z_{a} &= p_{1}\prime p_{2}\prime ... p_{n}\prime \\z_{b} &= q_{1}\prime q_{2}\prime ... q_{n} \prime\end{align*}$

那么

$z_{c} = z_{a} * k + z_{b} = p_{1}\prime * p_{2}\prime* ...* p_{n}\prime * k + q_{1}\prime* q_{2}\prime* ... *q_{n}\prime$

假设 $z_{c} 与 z_{a}$ 存在一个质数公因数 $p_{x}\prime$ ，那么必定有

$p_{x}\prime \in \{ p_{1}\prime,p_{2}\prime...p_{n}\prime \}$ 且 $p_{x}\prime \mid z_{a},\quad p_{x}\prime \mid z_{c}$

即:

$\begin{align*}\frac{z_{c}} { p_{x}\prime } &= \frac {p_{1}\prime*...*p_{n}\prime * k + q_{1}\prime*...*q_{n}\prime} {p_{x}\prime } \\&= \frac {p_{1}\prime*...*p_{n}\prime * k}{p_{x}\prime } + \frac{q_{1}\prime*...*q_{n}\prime} {p_{x} \prime}\end{align*}$

要满足上式结果为整数， $\frac{q_{1}\prime*...*q_{n}\prime} {p_{x}\prime}$ 必须是整数，即 $p_{x}$ 必须满足以下条件:

$p_{x}\prime = q_{i}\prime * ...* q_{j}\prime, \quad \{q_{i}\prime,..,q_{j}\prime \} \subseteq \{q_{1}\prime,...,q_{n}\prime \}$

但 $p_{x}\prime$ 是质数不能表示为两个及以上的质数之积。又 $p_{x} \notin \{ q_{1}\prime, q_{2}\prime, ...,q_{n}\prime\}$ ，由此可得 :

假设不成立。

同理 $z_{c} 与 z_{b}$ 也不存在公因数。

最后编辑于：2019.07.01 19:39:03

证明：若a、b两数互质，a必定与ak+b 互质

推荐阅读更多精彩内容