扩展欧拉定理
\[a^b\equiv \begin{cases} a^{b \bmod \varphi(m)} & (a,m)=1\\ a^b & (a,m)\neq 1,b<\varphi(m)\\ a^{b\bmod\varphi(m)+\varphi(m)} & (a,m)\neq 1,\,b\geqslant \varphi(m) \end{cases} \pmod{m} \]-
应当注意不能认为总是有 \(a^b\equiv a^{b\bmod\varphi(m)+\varphi(m)} \pmod{m}\)，这在第二种情况下可能不对，因为不能保证 \(a^{\varphi(m)}\equiv 1 \pmod{m}\)。
-
证明如下：
-
对于 \(a^0,a^1,\dots ,a^{+\infty}\pmod{m}\)，存在 \(r,s\)，使得 \(a^0\sim a^{r-1}\) 互不相同，从 \(a^r\) 开始每 \(s\) 个数循环一次。
-
因为 \(\pmod{m}\) 的数集是有限集，故互不相同的 \(a^k\) 是有限的，\(r\) 存在。
-
由鸽笼原理，一定存在 \(k>k'\)，使得 \(a^k\equiv a^{k'}\)，于是显然循环。
-
-
\(a\in prime\) 时，该式成立。
-
若 \(a\perp m\)，为欧拉定理的简单情况。
-
否则，存在 \(t\)，使得 \(m=a^tm'\)，且 \(a\perp m'\)，从而 \(a^{\varphi(m')}\equiv 1\pmod{m'}\)。
-
由欧拉函数的积性，有 \(m'\mid m\to \varphi(m')\mid \varphi(m)\)，于是 \(a^{\varphi(m)}\equiv 1\pmod{m'}\)。
-
转为不定方程，\(a^{\varphi(m)}=km'+1\)，再在两边同乘 \(a^t\)，得到 \(a^{t+\varphi(m)}=km+a^t\)。
-
转回同余式，得到 \(a^t\equiv a^{t+\varphi(m)}\)。利用欧拉函数的积性，有
- 注意到 \(a\geqslant 2,t\geqslant 1\)，故
-
其中 \(a^{t-1}(a-1)=t\) 只在 \(a=2,t=1\) 时取得。
-
所以对于 \(a>2\) 或 \(t>1\)，有 \(a^t\equiv a^{t+\varphi(m)}\equiv a^{t\bmod m+\varphi(m)}\)。
-
对于 \(a=2 \And t=1\)，手动验证发现总有 \(t=1\leqslant \varphi(m)\)，\(<\) 时走第二种情况，\(=\) 时显然有 \(2^1=2^{1\bmod 1+1}\)。
-
故该式在 \(a\in prime\) 时成立。
-
-
\(a\in p^k,p\in prime\) 时，该式成立。
- 累了。
-
应用：光速幂。
-
扩展欧拉定理告诉我们，在 \(\pmod m\) 意义下，一切幂的次数都在 \([0,2\varphi(m))\) 中。
-
\(2\varphi(m)\) 还是有点大，考虑使用幂的性质，取 \(sq=\lceil\sqrt{\varphi(m)}\rceil\)，于是
- 则可以 \(O(\sqrt{m})-O(1)\) 地求固定底数的幂。一般化地，应当是 \(O(m^{\frac{1}{k}})-O(\log_{m^{\frac{1}{k}}} m)=O(k)\) 的，不过实践中最常用 \(k=2\)。
-
中国剩余定理
- 给定如下同余方程组,其中 \(m_i\) 与 \(m_j\) 互质。
-
求最小正整数解。
-
思路：构造一组 \(x_1,x_2,\dots,x_n\)，使得 \(x_i\equiv 1\pmod {m_i},x_i\equiv 0\pmod {m_j}(j\neq i)\)。
-
从而我们有 \(x=\sum\limits_{i=1}^{n} b_ix_i\)，解系为 \(x_0=x+kM\)，最小正整数解 \(x_1=x\bmod M(M=\prod\limits_{i=1}^{n}m_i)\)。
-
证明从构造里就能看出。
-
下面说一下怎么构造。取 \(now_i=\dfrac{M}{m_i}\)，显然有 \(now_i\equiv 0\pmod {m_j}\)，则 \(x_i=now_i\times now_i^{-1}\pmod {m_i}\)。
扩展中国剩余定理
- 给定如下同余方程组，不保证 \(m_i\) 与 \(m_j\) 互质。
-
原思路所需的性质根本不存在。考虑另起炉灶。
-
尝试将方程合并。
-
令 \(x_0\) 满足前两个方程，则有 \(1\times x_0+m_1\times y_1=b_1\)。形式不好看，整理一下，\(x_0=m_1\times y_1+b_1=m_2* y_2+b_2\)。
-
从而有 \(m_1\times y_1-m_2\times y_2=b_2-b_1\)。
-
exGCD。容易给出 \(y\) 从而得到 \(x\)。
-
定理：对如上的二同余方程组，如果有特解 \(x_0\) ,则解系为 \(x\equiv x_0\pmod {\operatorname{lcm}(m_1,m_2)}\) 。这也是合并出的新方程。
-
证明：
-
正确性略，lcm 是可以约掉的。
-
唯一性：假设有 \(x,y\) 都满足要求，则 \(x-y\equiv 0\pmod{m_1}\) 或 \(\pmod{m_2}\)，所以 \(x-y\equiv0\pmod {\operatorname{lcm}(m_1,m_2)}\)，但 \(x,y<\operatorname{lcm}(m_1,m_2)\)，所以 \(x-y=0,x=y\)，不成立。
-
-
注意，虽然这个也是转化成剩余系，也可以调整成最小正整数解，但这一步和上面的 exGCD 可以说半毛钱关系都没有，因为 \(x\) 并不是 exGCD 的内容！！！请先用 \(\dfrac{c}{g}\) 把 \(y\) 调整好，再用它来做 \(x\)！！！
-
另外，这里还有一点小 trick。考虑 exCRT 的同余方程中式左 \(x\) 系数不为 \(1\) 的情况。
-
考虑重构该方程。记系数为 \(k\)，则原同余方程等价于 \(k\times x+m\times y=b\)。
-
老规矩，先用裴蜀定理判一下解的存在性。然后得出 \(x\) 的解系，从而对应母方程等价于该解系。
例题
P5091 【模板】扩展欧拉定理
- 板子，使用秦九韶算法即可。注意扩欧开头的那句话。