数论
2021-01-26 发表算法 / 数论4 分钟读完 (大约572个字)
数论:逆元
什么是逆元?
若 $ax \equiv 1 \pmod b$,则称 $x$ 是 $a$ 关于模 $b$ 的逆元,常记做 $a^{-1}$.
上式等价于 $ax + by = 1$,因此,一种求逆元的方法就是利用扩欧解方程 $ax + by = 1$.
显然,逆元不一定存在:其存在的充要条件为 $(a, b) = 1$.
推论:$p$ 是质数,$p$ 不整除 $a$,则 $a$ 模 $p$ 的逆元存在.
数论:不定方程整数解
欧几里得算法
又称辗转相除法,迭代求两数 gcd.
由 $(a, b) = (a, ka + b)$ 的