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

作者: 人类发展观察者 | 来源:发表于2019-06-29 12:58 被阅读0次

证明：若a、b两数互质，a必定与ak+b 互质
欧拉函数
无理数的那点事
2019-09-28
CRT中国剩余定理
数学基础
真理往往是最简单朴素的
数学基础，笔记
快速幂求逆元
乘法逆元

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

$\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}$ 也不存在公因数。

证明：若a、b两数互质，a必定与ak+b 互质
假设取任意两个不同的整数: 那么假设存在一个质数公因数，那么必定有且即: 要满足上式结果为整数，必须是整数...
欧拉函数
欧拉函数定义：若则称a，b互质。gcd(a,b,c)称为a，b，c互质，而称为两两互质。例如2,3,4互质但是不...
无理数的那点事
证明：不是有理数假设是有理数，则可以表示成,且与互质则为偶数设则为偶数，与不互质，矛盾。故不是有理数。
2019-09-28
关于RSA算法原理欧拉函数φ(n)φ(n) = 小于等于n的正整数中，有多少与n互质的数（互质，即两个数除了1，...
CRT中国剩余定理
特别版（除数两两互质）普通版（任意情况）两两合并变成互质情况。
数学基础
有理数互质最小公约数
真理往往是最简单朴素的
关于互质关系，以下几条是不证自明的结论： 1. 任意两个质数构成互质关系，比如13和61。 2. 一个数是质数...
数学基础，笔记
最大公约数，最小公倍数，关系互质分数，分子与分母的关系，互质质数指数计数法
快速幂求逆元
逆元的定义若整数b，m互质，并且b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法...
乘法逆元
若整数b，m互质，并且,则存在一个整数x，使得。称x为b的模m乘法逆元，记为。因为,所以。计算乘法逆元有两个方法费...