-
逆元
-
定义
存在 $ a\times x \equiv 1 \pmod{m} $ ，我们称 \(x\) 为 \(a\) 的逆元。
-
完全剩余系
假设 \(1 \to P-1\) 都存在逆元，我们则称他为一个完全剩余系。当然，是在模 \(P\) 的意义下。
-
费马小定理
\(a^{p-1} \equiv 1 \pmod{p}\)。
显然，此时 \(a^{p-1}\) 的逆元为 \(a^{p-2}\) 。
-
\(\color{red} \text 递推求逆元\)
若存在 $a \times i +b \equiv 0 \pmod{p} $ 。
这存在 \(i^{-1} \equiv (p-a) \times b^{-1} \pmod{p}\)。其中 \(i^{-1}\) 为 \(i\) 的逆元。
-
欧拉函数
我们用 $ \varphi(n) $ 表示 \(1 \to n\) 里面所有与 \(n\) 互质的数。且有一个脑瘫的柿子。 $$a^{\varphi(n)} \equiv 1 $$
-
性质
\(1.\varphi(nm)=\varphi(n) \times \varphi(m)\)。 要求 \(n,m\) 互质。
\(2. \varphi(nm)=\varphi(n) \times m\) 。要求 \(m\) 的质因数是 \(n\) 的子集。
-
线性求出
自己看wiki...
标签：数论,varphi,times,学习,pmod,逆元,笔记,互质,equiv From： https://www.cnblogs.com/zhong114514/p/17052227.html