题解 P6091 【【模板】原根】

#### 前言 upd(**2021.02.13**)：更改了所有已知错误与笔误；对一些评论有异议的地方增添了补充说明；更改了部分用词并修正了一些内容；修正了部分错误的 LaTeX。 另外，codecode 早已退役~~转战数竞~~，这次更新可能是对本博客的最后一次更新，但仍欢迎您反馈发现的问题/不懂的表述等~~说不定还会回来呢~~。 upd(**2020.04.06**)：更新了部分用词；修正了部分 LaTeX 错误；添加了部分内容。 ---------- 楼下的大佬已经给出了正解，这里只是整理一下并帮他们补充完整证明。 作为数竞生，对于这种问题就想要给出一个完整的证明。（其实作为 OIer，只需要知道结论就可以了，不一定需要知道证明。（雾）） 证明比较复杂，可能需要阅读并理解较长时间；如果不想看证明，可以跳到最后看结论。 ### 证明过程 前置：费马定理，欧拉定理，拉格朗日定理。 这里只给出拉格朗日定理的证明。 >> **前置 拉格朗日定理**：设 $p$ 为素数，对于模 $p$ 意义下的整系数多项式 >> >> $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0\;(p\nmid a_n)$$ >> >> 的同余方程 $f(x)\equiv 0\pmod p$ 在模 $p$ 意义下至多有 $n$ 个不同解。 > > **证明**：对 $n$ 使用归纳法。当 $n=0$ 时，由于 $p\nmid a_0$，故 $f(x)\equiv 0\pmod p$ 无解，定理对 $n=0$ 的多项式 $f(x)$ 都成立。 > > 若命题对于 $\deg f<n$ 的 $f$ 都成立，由反证法，假设存在一个满足题目条件的 $f$ 在模 $p$ 意义下有着至少 $n+1$ 个不同的解 $x_0,x_1,\cdots,x_{n}$。 > > 可设 $f(x)-f(x_0)=(x-x_0)g(x)$，则 $g(x)$ 在模 $p$ 意义下是一个至多 $n-1$ 次的多项式。现在由 $x_0,x_1,\cdots,x_n$ 都是 $f(x)\equiv 0\pmod p$ 的解，知对 $1\leq i\leq n$，都有 > > $$(x_i-x_0)g(x_i)\equiv f(x_i)-f(x_0)\equiv 0\pmod p$$ > > 而 $x_i \not\equiv x_0 \pmod p$，故 $g(x_i)\equiv 0\pmod p$，从而 $g(x)\equiv 0\pmod p$ 有至少 $n$ 个根，与归纳假设矛盾。 > > 所以，命题对 $n$ 次多项式也成立，定理获证。 > _补充：关于拉格朗日定理的证明中，由于 $f(x_i)=0$，故 $f(x)-f(x_i)$ 就是 $f(x)$，不影响阅读。_ ------------ 下面来看看阶与原根。 > **阶**：由欧拉定理可知，对 $a\in \mathbf{Z},m\in\mathbf{N}^{*}$，若 $\gcd(a,m)=1$，则 > $$a^{\varphi(m)}\equiv 1\pmod m$$ > >因此满足同余式 $a^n \equiv 1 \pmod m$ 的最小正整数 $n$ 存在，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$。 > > **原根**：设 $m \in \mathbf{N}^{*}$，$a\in \mathbf{Z}$。若 $\gcd(a,m)=1$，且 $\delta_m(a)=\varphi(m)$，则称 $a$ 为模 $m$ 的原根。 关于阶有一个较为显然的性质： > 若 $a^n \equiv 1 \pmod m$，则 $\delta_m(a)|n$。 **证明**： 对 $n$ 除以 $\delta_m(a)$ 作带余除法，设 $$n=\delta_m(a)q+r,0\leq r<\delta_m(a)$$ 若 $r>0$，则 $$a^r\equiv a^r(a^{\delta_m(a)})^q\equiv a^n \equiv 1 \pmod m$$ 这与 $\delta_m(a)$ 的最小性矛盾。故 $r=0$，即 $\delta_m(a)|n$。 _应评论：这里区分出 $r>0$ 是为证明 $r=0$。_ ------------ 阶还有两个重要的性质。 > **性质 $1$**：设 $m\in\mathbf{N}^{*}$，$a,b\in\mathbf{Z}$，$\gcd(a,m)=\gcd(b,m)=1$，则 > > $$\delta_m(ab)=\delta_m(a)\delta_m(b)$$ > > 的充分必要条件是 $\gcd(\delta_m(a),\delta_m(b))=1$。 > **证明**： 必要性。由 $a^{\delta_m(a)}\equiv 1 \pmod m$ 及 $b^{\delta_m(b)} \equiv 1 \pmod m$，可知 $$(ab)^{\operatorname{lcm}(\delta_m(a),\delta_m(b))}\equiv 1 \pmod m$$ 由前面所述阶的性质，有 $$\delta_m(ab)|\operatorname{lcm}(\delta_m(a),\delta_m(b))$$ 又由于 $\delta_m(ab)=\delta_m(a)\delta_m(b)$，故 $$\delta_m(a)\delta_m(b)|\operatorname{lcm}(\delta_m(a),\delta_m(b))$$ 即 $\gcd(\delta_m(a),\delta_m(b))=1$。 充分性。由 $(ab)^{\delta_m(ab)}\equiv 1 \pmod m$ 可知 $$1 \equiv (ab)^{\delta_m(ab)\delta_m(b)}\equiv a^{\delta_m(ab)} \pmod m$$ 故 $\delta_m(a)|\delta_m(ab)\delta_m(b)$。结合 $\gcd(\delta_m(a),\delta_m(b))=1$ 即得 $$\delta_m(a)|\delta_m(ab)$$ 对称地，同理可得 $$\delta_m(b)|\delta_m(ab)$$ 所以 $$\delta_m(a)\delta_m(b)|\delta_m(ab)$$ 另一方面，有 $$(ab)^{\delta_m(a)\delta_m(b)}\equiv(a^{\delta_m(a)})^{\delta_m(b)}\times(b^{\delta_m(b)})^{\delta_m(a)}\equiv 1 \pmod m$$ 故 $$\delta_m(ab)|\delta_m(a)\delta_m(b)$$ 综合以上两点即得 $$\delta_m(ab)=\delta_m(a)\delta_m(b)$$ **性质 $1$ 证毕。** > **性质 $2$**：设 $k \in \mathbf{N}$，$m\in \mathbf{N}^{*}$，$a\in\mathbf{Z}$，$\gcd(a,m)=1$，则 > > $$\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$ > **证明**：注意到 $$a^{k\delta_m(a^k)}=(a^k)^{\delta_m(a^k)}\equiv 1 \pmod m$$ $$\Rightarrow \delta_m(a)|k\delta_m(a^k)$$ $$\Rightarrow \dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}|\delta_m(a^k)$$ 另一方面，由 $a^{\delta_m(a)}\equiv 1 \pmod m$，可知 $$(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}}=(a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}}\equiv 1 \pmod m$$ 故 $$\delta_m(a^k)|\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$ 综合以上两点，得 $$\delta_m(a^k)=\dfrac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$ **性质 $2$ 证毕。** ------------ 回到正题，我们下面来证明，关于怎样的 $m$，其原根存在。 首先，$m=1,2,4$ 时，原根存在。 > **定理 $1$**：对于奇素数 $p$，$p$ 有原根。 > **证明**：先证一个引理： >> **引理**：设 $a$ 与 $b$ 是与 $p$ 互素的两个整数，则存在 $c\in\mathbf{Z}$ 使得 $\delta_p(c)=\operatorname{lcm}(\delta_p(a),\delta_p(b))$。 >> > > _该引理原来的证明存在错误，现已更改证明，感谢 @ [lgLinZhengYu](https://www.luogu.com.cn/user/74931) 及 @ [Peanut_Tang](https://www.luogu.com.cn/user/72765) 指出。_ > > 记 $r=\delta_p(a),t=\delta_p(b)$，设它们的“标准分解”（这里对指数只要求 $\max(\alpha_j,\beta_j)>0$）分别为 > > $$r=\prod_{j=1}^s p_j^{\alpha_j},\quad t=\prod_{j=1}^s p_j^{\beta_j}$$ > > 令 $l$ 为所有使得 $\alpha_j\leq\beta_j$ 的 $p_j^{\alpha_j}$ 的乘积，令 $m$ 为所有使得 $\alpha_j>\beta_j$ 的 $p_j^{\alpha_j}$ 的乘积. 记 $r=lx,t=my$. 则这样定义的 $x,y$ 满足 $\gcd(x,y)=1$ 且 $\operatorname{lcm}(r,t)=xy$。 > > 由性质 $2$，$\delta_p(a^l)=x,\delta_p(b^m)=y$，则由性质 $1$，$\delta_p(a^lb^m)=xy=\operatorname{lcm}(\delta_p(a),\delta_p(b))$，即取 $c=a^lb^m$ 即可。 > 回到原命题，对 $1 \sim (p-1)$ 依次两两使用引理，可知存在 $g\in \mathbf{Z}$ 使得 $$\delta_p(g)=\operatorname{lcm}\left(\delta_p(1),\delta_p(2),\cdots,\delta_p(p-1)\right)$$ 这表明 $\delta_p(j)|\delta_p(g)\;,j=1,2,\cdots,p-1$，所以 $j=1,2,\cdots,p-1$ 都是同余方程 $$x^{\delta_p(g)}\equiv 1\pmod p$$ 的根。由拉格朗日定理，可知方程的次数 $\delta_p(g) \geq p-1$。 又由费马小定理，易知 $\delta_p(g) \leq p-1$，故 $\delta_p(g)=p-1=\varphi(p)$。 综上可知 $g$ 为模 $p$ 的原根。 **定理 $1$ 证毕**。 ------------ > **定理 $2$**：对于奇素数 $p$，$\alpha \in \mathbf{N}^{*}$，$p^\alpha$ 有原根。 > **证明**：一个基本的想法是将模 $p$ 的原根平移。 先证明一个引理： >> **引理**：存在模 $p$ 的原根 $g$，使得 $g^{p-1}\not\equiv 1 \pmod {p^2}$ >> > > **引理的证明**：事实上，任取模 $p$ 的原根 $g$，若 $g$ 不满足条件，我们认定 $g+p$ 满足条件。 > > 易知 $g+p$ 也是模 $p$ 的原根。 > > 我们有 > > $$\begin{aligned}(g+p)^{p-1}&\equiv C_{p-1}^0g^{p-1}+C_{p-1}^1pg^{p-2}\\&\equiv g^{p-1}+p(p-1)g^{p-2}\\&\equiv 1-pg^{p-2}\\&\not\equiv 1 \pmod {p^2}\end{aligned}$$ > 回到原题，我们证明若 $g$ 是一个满足引理条件的原根，则对任意 $\alpha\in\mathbf{N}^{*}$，$g$ 是模 $p^{\alpha}$ 的原根。 首先，证明下面的结论：对任意 $\beta\in\mathbf{N}^{*}$，都可设 $$g^{\varphi(p^\beta)}=1+p^{\beta}\times k_{\beta}$$ 这里 $p\nmid k_{\beta}$。事实上，$\beta=1$ 时，由 $g$ 的选取可知结论成立。现设上式对 $\beta$ 时成立，则 $$\begin{aligned}g^{\varphi(p^{\beta+1})}&=(g^{\varphi(p^{\beta})})^{p}\\&=(1+p^{\beta}\times k_{\beta})^p\\&\equiv 1+p^{\beta+1}\times k_{\beta} \pmod {p^{\beta+2}}\end{aligned}$$ 结合 $p\nmid k_{\beta}$ 可知命题对 $\beta+1$ 成立。 所以命题对任意 $\beta\in\mathbf{N}^{*}$ 都成立。 其次，记 $\delta=\delta_{p^\alpha}(g)$，则由欧拉定理，可知 $\delta|p^{\alpha-1}(p-1)$。 而由 $g$ 为模 $p$ 的原根，及 $g^{\delta}\equiv 1\pmod {p^\alpha}$ 可知 $(p-1)|\delta$。 所以可设 $\delta=p^{\beta-1}(p-1)$，这里 $1\leq \beta\leq \alpha$。 现在利用之前的结论，可知 $$g^{\varphi(p^{\beta})}\not\equiv 1\pmod {p^{\beta+1}}\Rightarrow g^{\delta}\not\equiv 1\pmod {p^{\beta+1}}$$ 结合 $g^{\delta}\equiv 1\pmod {p^\alpha}$ 可知 $\beta \geq \alpha$。 综上可知，$\beta=\alpha$，即 $$\delta_{p^{\alpha}}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha)$$ 从而，$g$ 是模 $p$ 的原根。 **定理 $2$ 证毕**。 ---------- > **定理 $3$**：对于奇素数 $p$，$\alpha\in\mathbf{N}^{*}$，$2p^{\alpha}$ 的原根存在。 > **证明**：设 $g$ 是模 $p^{\alpha}$ 的原根，则 $g+p^{\alpha}$ 也是模 $p^{\alpha}$ 的原根。 在 $g$ 和 $g+p^{\alpha}$ 中有一个是奇数，设这个奇数是 $G$，则 $\gcd(G,2p^{\alpha})=1$。 由欧拉定理，$\delta_{2p^{\alpha}}(G)|\varphi(2p^{\alpha})$。 而 $G^{\delta_{2p^{\alpha}}(G)}\equiv 1\pmod {2p^{\alpha}}$，故 $$G^{\delta_{2p^{\alpha}}(G)}\equiv 1 \pmod {p^{\alpha}}$$ 利用 $G$ 为模 $p^{\alpha}$ 的原根可知 $\varphi(p^{\alpha})|\delta_{2p^{\alpha}}(G)$。 结合 $\varphi(p^{\alpha})=\varphi(2p^{\alpha})$ 可知 $G$ 为模 $2p^{\alpha}$ 的原根。 **定理 $3$ 证毕**。 ---------- > **定理 $4$**：对于 $m\notin\{1,2,4\}$，且不存在奇素数 $p$ 及 $\alpha \in \mathbf{N}^{*}$ 使得 $m\in\{p^{\alpha},2p^{\alpha}\}$，则对任意 $a\in\mathbf{Z}$，$\gcd(a,m)=1$，都有 $\delta_m(a)<\varphi(m)$，即模 $m$ 的原根**不存在**。 > **证明**：对于 $m=2^{\alpha}$，$\alpha\in\mathbf{N}^{*},\alpha\geq 3$，则对任意奇数 $a=2k+1$ 均有 $$\begin{aligned}a^{2^{\alpha-2}}&=(2k+1)^{2^{\alpha-2}}\\&\equiv 1+C_{2^{\alpha-2}}^1(2k)+C_{2^{\alpha-2}}^{2}(2k)^{2}\\&\equiv1+2^{\alpha-1}k+2^{\alpha-1}(2^{\alpha-2}-1)k^2\\&\equiv 1+2^{\alpha-1}(k+(2^{\alpha-2}-1)k)\\&\equiv 1 \pmod {2^{\alpha}}\end{aligned}$$ 其中最后一步用到 $k$ 与 $(2^{\alpha-2}-1)k$ 同奇偶，故其和为偶数。 若 $m$ 不是 $2$ 的幂，且 $m$ 为符合题目条件的数，则可设 $m=rt$，这里 $2<r<t$ 且 $\gcd(r,t)=1$。 此时，若 $\gcd(a,m)=1$，由欧拉定理可知 $$a^{\varphi(r)}\equiv 1 \pmod r\;,\quad a^{\varphi(t)}\equiv1\pmod t$$ 注意到 $n>2$ 时，$\varphi(n)$ 为偶数，所以 $$a^{\frac{1}{2}\varphi(r)\varphi(t)}\equiv 1\pmod {rt}$$ 进而 $$\delta_m(a)\leq\dfrac{1}{2}\varphi(r)\varphi(t)=\dfrac{1}{2}\varphi(rt)=\dfrac{1}{2}\varphi(m)<\varphi(m)$$ **定理 $4$ 得证**。 ---------- ### 结论 上面的定理 $1$ 到 $4$ 完整的给出了原根的充要条件。截至目前，我们证明了仅有 $1,2,4$ 或奇素数 $p^{\alpha}$ 及 $2p^{\alpha}$ 有原根，其它的数都没有原根。 那么我们可以先预处理素数及其幂次，及其幂次的 $2$ 倍，$\Theta(1)$ 的判断一个数有没有原根。 如果一个数有原根，可以先求出最小正原根。 > 王元于 1959 年证明了若 $m$ 有原根，其最小原根是不多于 $m^{0.25}$ 级别的。 > > 事实上，由大量试验数据可以发现，对于足够大的 $m$，其最小正原根的大小不是多项式级别的。 > > ——百度百科 可以感性理解一下，模 $m$ 的原根有 $\varphi(\varphi(m))$ 个，密度很大，所以最小原根很小。 根据这个结论，我们可以从小到大枚举。由原根的定义，若 $g$ 为模 $m$ 的原根，则对于 $\varphi(m)$ 的任意素因数 $p$，必有 $$g^{\varphi(m)/p}\not\equiv 1 \pmod m$$ 同时，满足如上条件的 $g$，必将是原根。 我们可以预处理出 $\varphi(m)$ 的所有素因数，快速幂来判断。 假如找到了一个原根 $g$，不难证明对于所有 $\gcd(x,\varphi(m))=1$ 的 $x$，$g^x$ 均为原根，所以模 $m$ 的原根有 $\varphi(\varphi(m))$ 个。 所以我们可以在找到 $g$ 后再枚举找出所有 $m$ 的原根，排序后按要求输出。 ~~复杂度不会算~~ **注意需要开 longlong**。