阶
对于 \(\gcd(a,p)=1\)，最小的 \(t\) 使得 \(a^t\equiv 1(\bmod p)\) 称为 \(a\) 的阶。写作 \(\operatorname{ord}_p(a)\)。
若 \(a^k\equiv 1(\bmod p)\)，当且仅当 \(\operatorname{ord}_p(a)|k\)。
求阶的复杂度是 \(O(\sqrt{n})\)。
给定 \(\gcd(a,p)=\gcd(b,p)=1\)，问是否存在 \(t\) 使得 \(a^t\equiv b(\bmod p)\)。
\(\operatorname{ord}_p(b)|\operatorname{ord}_p(a)\) 是充要条件。
不会证。
原根
若 \(\gcd(a,p)=1\) 且 \(\operatorname{ord}_p(a)=\phi(p)\)，则称 \(a\) 为模 \(p\) 意义下的原根。
所有质数都存在原根。
从求阶的过程来证明。
后面没听。
莫比乌斯反演
定义域为正整数的函数被称为数论函数。
莫比乌斯反演是狄利克雷前缀和的逆变换。
标签：gcd,原根,bmod,day3.2,数学,整合,ord,operatorname,equiv From： https://www.cnblogs.com/BYR-KKK/p/18172583