题解 P6091 【【模板】原根】
codecode
2020-04-06 15:03:21
#### 前言
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**。