文章总览：春风得意

原根与离散对数，是非常玄学的概念~~（虽然说只是高联初等数论，但是本蒟蒻已经不会了）~~，由于关于原根和阶的一些性质，我在搜索的过程中遇到了一个叫做群论的东西，这玩意对于我来说略有超纲有缘再见罢。这篇文章的内容限定于下。

前置知识：时运驰骋

阶的定义性质及其证明
- 阶的定义
- 阶的性质及其证明

阶的定义

首先要知道原根，就需要一个非常重要的前置知识，没有它甚至连原根都算不出来，他就是阶。首先给出阶在数学上的定义。我们定义满足 $a^r\equiv 1\pmod p$ 其中 $\gcd(a,p)=1\ (p\gt 1)$ 的最小正整数 $r$ 是 $a$ 对模 $p$ 的阶，记作 $\delta_p(a)$ 。

定义非常好理解，但是始终是抽象的，我们可以大概的举几个例子。比如说下面的例子中我们都取 $p=7$：

当 $a = 2$ 时，我们可以枚举：

$2^1\equiv 2\pmod 7$，$2^2\equiv 4\pmod 7$，$2^3\equiv 1\pmod 7$，

则 $\delta_7(2)=3$，这是 $2$ 对模 $7$ 的阶。
当 $a = 3$ 时，我们可以枚举：

$3^1\equiv 3\pmod 7$，$3^2\equiv 2\pmod 7$，$3^3\equiv 6\pmod 7$，

$3^4\equiv 4\pmod 7$，$3^5\equiv 5\pmod 7$，$3^6\equiv 1\pmod 7$，

则 $\delta_7(3)=6$，这是 $3$ 对模 $7$ 的阶。
当 $a=4$ 时，我们可以枚举：

$4^1\equiv 4\pmod 7$，$4^2\equiv 2\pmod 7$，$4^3\equiv 1\pmod 7$，

则 $\delta_7(4)=3$，这是 $4$ 对模 $7$ 的阶。

当然就有人问了，会不会存在没有阶的数字呢？显然没有。我们知道欧拉定理，当 $\gcd(a,m)=1,m>1$ 的时候，我们有式子 $a^{\varphi(m)}\equiv1\pmod m$ 这时候我们就发现一定会有一个满足条件的阶作为结果。

阶的性质

然后就是一些常用的性质。

定理一　若 $a$ 对模 $m$ 的阶是 $\delta$，则 $a^0,a^1,\dots,a^{\delta-1}\ $对模 $m$ 两两不同余。

证明：

假设存在 $0\le r \lt l\le \delta-1$ 使得 $a^l\equiv a^r\pmod m$，因为 $\gcd(a,m)=1$ 所以说 $\gcd(a^r,m)=1$，则显而易见的我们有 $a^{l-r}\equiv 1\pmod m$，但是根据阶的定义，$\delta$ 是满足 $a^\delta\equiv 1\pmod m$ 的最小正整数。可是 $l-r$ 只能取到最大值 $\delta-1$ 也就是说 $0<l-r<\delta$，这与阶的定义相矛盾，也就是说这样的 $l,r$ 并不存在，原定理正确。

最小正整数是在证明命题真伪时非常重要的一个点，会有特别多的命题用到，这个需要学会熟练运用。

定理二　若 $a$ 对模 $m$ 的阶是 $\delta$，则 $a^\gamma \equiv a^{\gamma’}\pmod m$ 的充要条件是 $\gamma \equiv \gamma’\pmod \delta$

证明：

先证明必要性：由于条件关于同余，不难想到用带余除法分别表示为 $\gamma=k_1\delta+r_1$ 和 $\gamma’=k_2\delta+r_2$ 然后代入到原式子变成 $a^{k_1\delta+r_1}\equiv a^{k_2\delta+r_2}\pmod m$ 然后轻松的拆解为 $a^{k_1\delta}\cdot a^{r_1}\equiv a^{k_2\delta}\cdot a^{r_2}\pmod m$ 然后根据阶的定义 $a^\delta \equiv 1\pmod m$ 可以把刚刚的式子变为 $a^{r_1}\equiv a^{r_2}\pmod m$ 因为 $r_1,r_2$ 是 $\gamma,\gamma’$ 除以 $\delta$ 的余数，所以说 $0\le r_1,r_2\lt \delta$ 而根据上面的定理一，可得 $r_1=r_2$ 也即是 $\gamma \equiv \gamma’\pmod \delta$ 。

后证明充分性：其实这个证法一样的，和上面一样拆开来以后，同样化简成 $a^{r_1}\equiv a^{r_2}\pmod m$ 这时候由于我们的条件 $\gamma\equiv\gamma’\pmod\delta$ 所以说 $r_1=r_2$ 那其实就已经证完了。

运用已经证完的定理，还有带余除法表示都是数论中的常用技巧。

定理二的特殊情况　$a^\gamma\equiv 1\pmod m \Leftrightarrow \delta\mid\gamma$

根据定理二，$a^\gamma \equiv 1 \equiv a^\delta\pmod m$ $\Leftrightarrow$ $\gamma\equiv \delta \pmod \delta$ 也就是 $\delta\mid\gamma$ 。

其实这里强调的就是取模运算的周期性，转一圈就回到原点的。然后我们对于定理二就可以有一个显然的推论，根据欧拉定理 $a^{\varphi(m)}\equiv 1\pmod m$ 可以得到：$\delta\mid\varphi(m)$，重要的推论。

定理三　若 $x$ 对模 $m$ 的阶是 $ab$，$a,b>0$，则 $x^a$ 对模 $m$ 的阶是 $b$ 。

证明：

首先证明存在性：由于$\ \gcd(x,m)=1$，所以 $\gcd(x^a,m)=1$ 这时候 $x^a$ 对模 $m$ 的阶是存在的。

然后从两方面分别证明

一方面：设 $\delta_m(x^a)=\delta$，则 $x^{a\delta}\equiv 1\pmod m$ 根据定理二得 $ab\mid a\delta$ 即 $b\mid \delta$ 。

另一方面：由阶的定义得 $x^{ab}\equiv 1\pmod m$ 变化得 $(x^a)^b\equiv 1\pmod m$ 同样设了 $\delta_m(x^a)=\delta$ 由定理二不难得到 $\delta\mid b$ 。

综上，$\delta=b$ 。

这样一个两方面来确定一个结果的证明方式，被称为夹逼的思想，非常常用。

定理四　若 $x$ 对模 $m$ 的阶是 $a$，$y$ 对模 $m$ 的阶是 $b$，且 $\gcd(a,b)=1$，则 $xy$ 对模 $m$ 的阶是 $ab$ 。

证明：

首先证明存在性：由于 $(x,m)=1,(y,m)=1$ 所以说 $(xy,m)=1$ 则 $\delta_m(xy)=\delta$ 存在。

一方面来讲：根据阶的定义得 $(xy)^\delta\equiv 1\pmod m$ ，同余等式两边同时算上 $b$ 次方则有 $(xy)^{b\delta}\equiv 1\pmod m$ 根据乘方运算的规律可得 $x^{b\delta}\cdot y^{b\delta}\equiv 1\pmod m$，而又根据阶的定义 $y^b\equiv1\pmod m$ 也就是说这一项会被消掉变成 $x^{b\delta}\equiv1\pmod m$ 根据定理二得 $a\mid b\delta$ 又因为 $(a,b)=1$ 所以 $a\mid\delta$ 。同理的话 $(xy)^{a\delta}\equiv 1\pmod m$ 也是可以证出来相同的结论 $b\mid\delta$ 的，又因为 $(a,b)=1$ 所以 $ab\mid\delta$ 。

另一方面说：我们带入 $ab$ 变成 $(xy)^{ab}\equiv x^{ab}\cdot y^{ab}\equiv 1\pmod m$ 这时候发现根据定理二也可以得到 $\delta\mid ab$ 。

这样的话综上就是，$\delta=ab$ 。

这样我们就再次运用了夹逼的思想来搞定了定理四。我们注意到在“一方面”的内容中，我们反复利用了 $(a,b)=1$ 的条件，也就是说这是一个不可或缺的条件，那么定理四的逆命题是否成立呢？或者说：

逆 · 定理四　已知 $x$ 对模 $m$ 的阶是 $a$，$y$ 对模 $m$ 的阶是 $b$，且 $xy$ 对模 $m$ 的阶是 $ab$，则 $(a,b)=1$ 。

证明：
$\begin{aligned} & \because\ x^a\equiv 1,y^b\equiv1\pmod m,\\ & \therefore\ x^{[a,b]}\equiv y^{[a,b]}\equiv 1\pmod m,\\ & \therefore\ (xy)^{[a,b]}\equiv 1\pmod m,\\ & \therefore\ ab\mid [a,b],\\ & \therefore\ ab\le [a,b]=\frac{ab}{(a,b)},ab\le \frac{ab}{(a,b)},(a,b)\le 1\\ & \because\ a,b\in \mathbb N^\ast\\ & \therefore\ (a,b)\ge1\\ & \therefore\ (a,b)=1 \end{aligned}$

同样，这还是类似于夹逼的思想搞定了这个逆定理。

定理五　设 $a$ 对模 $m$ 的阶为 $\delta$，$\lambda\ge 1$，则 $a^\lambda$ 对模 $m$ 的阶是 $\cfrac{\delta}{(\lambda,\delta)}$

证明：

我们顺着题目的意思来，式子的主要部分其实是 $(\lambda,\delta)$ 所以不妨设 $g=(\lambda,\delta)$ 则根据最大公因数的定义可以得到 $\delta=p\times g,\ \lambda=q\times g$ 且 $(p,q)=1$ 。

根据阶的定义，$(a^d)^r\equiv a^{dr}\equiv a^{qgr}\equiv 1\pmod m$ 。

根据上面的定理二，也就是 $\delta\mid qgr$ 。带入上面设定的值也即是 $pg\mid qgr$，约去相同因数 $g$ 可以得到 $p\mid qr$ 。根据整除的定义，$p$ 和 $q$ 没有任何公因子，也就是说唯一的选择就是 $p=r=\delta=\tfrac{\delta}{g}=\tfrac{\delta}{(\lambda,\delta)}$

这个定理五有两个经典的推论：

推论一：$\delta_m(a)=\delta,\lambda\ge1,(\lambda,\delta)=1\Rightarrow\delta_m(a^\lambda)=\delta$
推论二：$\delta_m(a)=\delta,\lambda\in\{1,2,\dots,\delta\}$ 则有 $\varphi(\delta)$ 个 $a^\lambda$ 对模 $m$ 的阶是 $\delta$ 。

第一个推论很显然，定理五的一个直接运用，推论二的话……其实就是接下来要说的定理六。

定理六　$p$ 是一个素数，若 $\exists\ a\in Z$，使 $a$ 对模 $p$ 的阶是 $l$，则恰有 $\varphi(l)$ 个对模 $p$ 两两不同余的整数，他们对模 $p$ 的阶都是 $l$ 。

证明：

因为 $\delta_m(a)=l$ 根据定理一可得集合 $S=\{a,a^2,\dots,a^l\}$ 中的 $l$ 个元素模 $p$ 两两不同余，那么接下来要证明的就变成了 $S$ 的元素是方程 $x^l\equiv 1\pmod p$ 的全部解。

$\forall\ x\in S$，设 $x=a^\lambda,1\le\lambda\le l$ 则 $x^l\equiv a^{\lambda l}\equiv 1\pmod p$ 所以说 $S$ 所有的元素都是该同余方程的解。根据拉格朗日定理，这个高次同余方程至多有 $l$ 个解，也就是说这个有 $l$ 个元素的集合 $S$ 恰好是这个同余方程所有的解。

设 $S$ 中任意一元素为 $a^\lambda,1\le\lambda\le l$ 由定理五得到 $\delta_p(a^\lambda)=l\ \Rightarrow\ (\lambda,l)=1$ 也就是说对模 $p$ 的阶是 $l$ 的前提要求是这个元素对应的 $\lambda$ 与 $l$ 互素。显而易见的这样的数的数量就是 $\varphi(l)$ 个。

这就是阶的大多数定理了，然后我们可以开始看关于原根的内容了。

概念基础：君子惠渥

原根的定义性质及其证明
- 原根的定义
- 原根的性质

原根的定义

如果一个数 $a$ 满足 $(a,m)=1$ 若 $\delta_m(a)=\varphi(m)$ 则称 $a$ 是对模 $m$ 的的一个原根。然后呢关于原根的定义我们就有一个很简单的推论：若 $a$ 是模 $m$ 的一个原根，则 $a+km\ (k\in \mathbb Z)$ 也是模 $m$ 的原根。

证明：设 $r=\delta_m(a)=\varphi(m)$ 则有 $a^r\equiv 1\pmod m$ 代入 $a+km$ 有 $(a+km)^r\equiv a^r+(\dots)$ 这里 $(\dots)$ 是二项式定理展开后除去 $a^r$ 的部分，由于这些部分显而易见都有因子 $m$ 模后都是 $0$，所以说 $(\dots)\equiv 0\pmod m$ 那么刚刚的式子就只剩下 $a^r\equiv 1\pmod m$ 和原来没区别，也就是说推论正确。

原根是否存在是我们求原根时一个重要的概念，所以我们可以尝试先枚举几个数

你在想什么，$1$ 有阶吗就开始叫。
显然的 $\delta_2(1)=\varphi(2)=1$ 但是说所有的奇数对模二的阶其实都是 $1$ 所以我们下面只探讨最小原根。
$\delta_3(1)=1$ 不对，然后试 $\delta_3(2)=2=\varphi(3)$ 所以说 $2$ 是对模 $3$ 的一个原根。
同样的 $\delta_4(1)=1$ 不对，然后对于 $2$ 来讲不互质不用想，$\delta_4(3)=2=\varphi(4)$
还是 $\delta_5(1)=1$ 不对，$\delta_5(2)=4=\varphi(5)$
$\delta_6(1)=1$ 不对，$(2,6)=2$ 跳过，$(3,6)=3$ 跳过，$(4,6)=2$ 跳过，$\delta_6(5)=2=\varphi(6)$
$\delta_7(1)=1$ 不对，$\delta_7(2)=3$ 不对，$\delta_7(3)=6=\varphi(7)$
就不枚举那些不互素的数了 $\delta_8(1)=1$ 不对，$\delta_8(3)=2$ 不对，$\delta_8(5)=2$ 不对，$\delta_8(7) =2$ 不对，可以证明除了 $1$ 或者大于 $8$ 的奇数对模 $8$ 的阶都是 $1$，其他的都是 $2$ 。也就是说 $8$ 没有原根。
$\delta_9(1)=1$ 不对，$\delta_9(2)=6=\varphi(9)$

基于这些枚举我们可以有一些适当的猜想来判定是否有原根，这个先留个坑，一会再来。

原根的性质

定理一　一个正整数 $m$ 有原根的条件是 $m=2,4,p^e,2p^e$，其中 $p$ 是奇素数，$e$ 是正整数。

证明移步下文原根的出现情况谢谢。

由于定理一的证明非常复杂，所以单开一个标题，先不放在这里。

定理二　设 $g$ 是模 $m$ 的原根，则 $g^d$ 是 $m$ 的原根的充分必要条件是 $(d,\varphi(m) )=1$ 。

证明：

根据上面阶的定理五，$\delta_m(g^d)=\tfrac{\delta_m(g)}{(\delta_m(g),d)}=\tfrac{\varphi(m)}{(\varphi(m),d)}=\varphi(m)$ 的充分必要条件是 $(\varphi(m),d)=1$ 。

这就是利用已经证明出来的定理来证明新的定理，原根和阶的关系密切，阶的定理可能会反复运用在原根定理的证明中。

关于定理二我们有一个推论：每一个有原根的正整数 $m$ 有 $\varphi(\varphi(m))$ 个原根，每一个素数都有 $\varphi(p-1)$ 个原根。这个推论非常显然，因为充分必要条件是与 $\varphi(m)$ 互素，所以自然就是有 $\varphi(\varphi(m))$ 个原根，然后由于对于素数 $p$ 有定义 $\varphi(p)=p-1$ 所以说带入刚刚的式子就可以了。

定理三　若 $g$ 是 $m$ 的一个原根，则 $g,g^2,\dots,g^{\varphi(m)}$ 对 $m$ 取模的余数就是小于 $m$ 且与 $m$ 互质的 $\varphi(m)$ 个数的一个排列。

证明：

这种定理一眼就是两点，一是与 $m$ 互质，二是排列，所以我们可以分两部分证明。

先证明排列，也就是 $g,g^2,\dots,g^{\varphi(m)}$ 模 $m$ 的结果两两不同。熟悉的使用反证法，假设存在 $i,j\ (1\le i<j\le\varphi(m))$ 使得 $g^i\equiv g^j\pmod m$ 则 $g^{j-i}\equiv 1\pmod m$ 这时候非常显然的是 $j-i\lt\varphi(m)$ 也就是说与 $g$ 是原根的定义矛盾。

然后证明互质。同样的使用反证法，设 $g^s=km+b=(ku+v)\gcd(b, m)$ 若 $(b,m)>1$ 也就是说 $(g^s,m)>1$ 那么我们肯定有 $(g,m)>1$ 这又与 $g$ 是原根的定义矛盾。

综上，这条定理是正确的。

拆解定理依次证明，非常常用的手法。

定理四　$m >1,\varphi(m)$ 的所有不同的质因数为 $p_1,p_2,\dots,p_k$，$(g,m)=1$，则 $g$ 是 $m$ 的原根的充要条件是 $g^{\tfrac{\varphi(m)}{p_i}}\not\equiv 1\pmod m,i\in\{1,2,\dots,k\}$ 。

证明：

同样的，分为充分性和必要性证明。先证明必要性，还是反证法：如果存在 $i\in[1,k]$ 使得 $g^{\tfrac{\varphi(m)}{p_i}}\not\equiv 1\pmod m$ 成立，根据阶的定理二可得 $\delta\mid\tfrac{\varphi(m)}{p_i}$ 也就是 $\delta\le\tfrac{\varphi(m)}{p_i}<\varphi(m)$ 与 $g$ 是原根的定义矛盾。

然后证明充分性，还是反证。假设 $g$ 不是对模 $m$ 的原根，也就是说有 $g^\delta\equiv 1\pmod m$ 其中 $\delta\neq\varphi(m)$ 。根据阶的定理二，可以有 $\delta\mid\varphi(m)$ 而且说过 $\delta\neq\varphi(m)$ 也就一定存在某一个 $\varphi(m)$ 的因子 $p_i$ 满足 $\delta\mid\tfrac{\varphi(m)}{p_i}$ 那么就有 $g^\tfrac{\varphi(m)}{p_i}\equiv(g^\delta)^u\equiv 1\pmod m$ 但是这与 $g^\tfrac{\varphi(m)}{p_i}\not\equiv1\pmod m$ 的条件相违背，也就是说假设不成立，$g$ 是对模 $m$ 的原根。

综上，该定理正确。

这个证明非常的拗口，重点就是在于别忘了充分性是从条件推出结论，必要性是从结论推出条件，而反证法是把我们要推出的东西反义一下然后证明矛盾。搞清楚这些的关系就可以理顺定理四的证明。

概念进阶：青丘遗泽

原根出现情况

还记得刚刚的原根性质定理一吗，这里就是专门证明他的地方。由于我们注意到它分为四个部分 $2,4,p^e,2p^e$ 所以我们将其拆解一下，我们发现 $2,4$ 都是二的幂，在一开始的枚举时也注意到，除了 $2,4$ 其他的 $2$ 的幂都没有原根了，这里就分解除了第一部分，引理一。接着来看，$p^e$ 中 $e\ge 1$ 那么如果 $e=1$ 就代表一个纯的奇素数这就是我们要证明的定理五，然后呢是 $p^e,e>1$ 的部分就是定理六。然后注意到 $2p^e$ 其实就是 $p^e$ 多了个 $2$ 而它和 $p^e$ 的关系显而易见应该是 $(2,p^e)=1$ 也就是说我们还需要一个引理二来连接他们，而这个 $2p^e$ 就是定理七本体。

这样的排序规则很奇怪，为什么这样排呢？他们其实是按照原根存在的必要条件和充分条件来分的。引理一和引理二都是原根存在的必要条件，而引理三四五都是原根存在的充分条件。我们先来证明引理一和引理二。

引理一　当 $\alpha\ge 3$ 且 $\alpha\in\mathbb Z$ 时，模 $2^\alpha$ 的原根不存在。

证明：

首先说还是一样，原根的条件一定是和模数互素，也就是说我们需要有一个 $a$ 满足 $(a,2^\alpha)=1$，所以我们要证明的问题就转化为：$\forall\ a=2k+1,k\in\mathbb Z$ 都有 $\delta_{2^{\alpha}}(a)<\varphi(2^\alpha)$

我们注意到对于奇数 $a$ 而言，都有 $a^{2^{\alpha-2}}\equiv1\pmod{\varphi(2^\alpha)}$ 这个数字的来源需要用到群论，知道就可以，我们接下来证明这个数字是对的即可。

首先我们知道 $\varphi(2^\alpha)=2^{\alpha-1}$ 这个显然，因为 $2^\alpha$ 只有因子 $2$ 。我们可以先把 $a=2k+1$ 代入式子然后将其拆解证明：
$\begin{aligned} a^{2^{\alpha-2}}&\equiv (1+2k)^{2^{\alpha-2}}\\ &\equiv 1^{2^{\alpha-2}}+\binom{2^{\alpha-2}}{1}(2k)+\sum_{i=2}^{2^{\alpha-2}}\binom{2^{\alpha-2}}{i}(2k)^i\\ &\equiv 1+2^{\alpha-2}\times 2k +\operatorname{(*)}\\ &\equiv 1+2^{\alpha-1}k+\operatorname{(*)}\pmod{2^{\alpha-1}} \end{aligned}$
然后我们可以看一看，显然 $2^{\alpha-1}k$ 会被模掉变成 $0$，然后我们要证明 $\operatorname{(*)}$ 部分（式子中的那个超长 $\sum$ ）能被模掉。

注意到对于 $i\ge2$，$\binom{2^{\alpha-2}}{i}$ 的分子中有连续的 $i$ 个因子，其中至少一个因子为 $2^{\alpha-2}$（实际上随着 $i$ 的增大，$2$ 的因子数会更多），而 $(2k)^i$ 至少贡献 $2^i$ 的因子。综上，这一项至少含有 $2^{\alpha-2+i}$ 的因子。当 $i\ge2$ 时，有
$\alpha-2+i\ge \alpha,$
故对于 $i\ge2$ 的所有项，都可以写成 $2^{\alpha-1}$ 的倍数，即 $a^{2^{\alpha-2}}\equiv 1\pmod{2^{\alpha-1}}$。那么对于所有的奇数都是如此，也就是说设他们的阶为 $\delta$ 的话，他们满足 $\delta\mid 2^{\alpha-2}$ 也就是 $\delta\le 2^{\alpha-2}\lt 2^{\alpha-1}=\varphi(2^\alpha)$。

故对于所有的 $2^\alpha,\alpha\ge3$ 且 $\alpha\in\mathbb Z$ 都没有原根，引理正确。

引理二　若正整数 $n=ab$，其中 $a>2,b>2,(a,b)=1$，则不存在模 $n$ 的原根。

证明：

反证法。假设存在模 $n$ 的原根 $x$，则 $\delta_n(x)=\varphi(n),(x,n)=1$ 因为 $a>2,b>2$ 所以 $\varphi(a),\varphi(b)$ 都是偶数。因为 $n=ab,(a,b)=1$ 所以说根据欧拉函数积性函数的性质可以有 $\varphi(n)=\varphi(ab)=\varphi(a)\varphi(b)$ 也就是说 $\varphi(n)$ 也是偶数。然后我们有一个小小的特性，$\varphi(a)\mid\tfrac{\varphi(n)}{2},\varphi(b)\mid\tfrac{\varphi(n)}{2}$ 这是为什么？

由于 $\varphi(a),\varphi(b)$ 都是偶数，我们可以设他们是 $2k_1,2k_2$ 而 $\varphi(n)$ 作为他们的乘积可以看作 $4k_1k_2$ 然后 $\tfrac{\varphi(n)}{2}$ 就是 $2k_1k_2$ 显然都可以被 $\varphi(a),\varphi(b)$ 整除。

然后我们根据欧拉定理，$a\mid x^{\varphi(a)}-1$，$b\mid x^{\varphi(b)}-1$ 。这个的来源是 $x^{\varphi(a)}\equiv 1\pmod a$ 然后移项得到 $x^{\varphi(a)}-1\equiv 0\pmod a\ $然后对于 $b$ 同理。

然后我们还需要一个小引理才可以证明，那就是 $a^n-b^n\mid a^m-b^m$ 其中 $(a,b)=1$ 的充要条件是 $n\mid m$，特别好证明，直接把 $m$ 表示为 $kn$ 然后代一代就可以了，不证明了。

然后注意到一开始说的 $\varphi(a)\mid\tfrac{\varphi(n)}{2},\varphi(b)\mid\tfrac{\varphi(n)}{2}$ 然后就可以得到 $x^{\varphi(a)}-1\mid x^{\tfrac{\varphi(n)}{2}}-1$ 当然 $b$ 还是同理，根据整除的传递性就可以有 $a\mid x^{\tfrac{\varphi(n)}{2}}-1,b\mid x^{\tfrac{\varphi(n)}{2}}-1$ 又因为我们有 $(a,b)=1$ 就可以有 $ab\mid x^{\tfrac{\varphi(n)}{2}}-1$ 又因为 $n=ab$ 所以说就有 $x^{\tfrac{\varphi(n)}{2}}\equiv 1\pmod n$。

显而易见这与一开始 $x$ 是模 $n$ 的原根的假设矛盾了，也就是说该引理正确。

事实上有了这两个引理我们就可以证明出原根的定理一了，也就是说这两个引理是原根存在的充要条件。接下来要证明几个关于原根存在的充分不必要条件。

定理五　奇素数 $p$ 的原根存在。

证明：

证明这个定理我们首先需要以小引理。

引理：设 $a,b$ 是与 $p$ 互素的两个整数，则存在整数 $c$ 使得 $\delta_p(c)=[\delta_p(a),\delta_p(b)]$。

证明：我们如果把 $\delta_m(a),\delta_m(b)$ 质因数分解，则有（由于质因数分解需要，暂时将 $p$ 替换为 $m$ ）：
$\delta_m(a)=\prod_{i=1}^k p_i^{\alpha_i},\delta_m(b)=\prod_{i=1}^k p_i^{\beta_i}$
然后我们有一种非常巧妙地分解方式将 $\delta_m(a)=XY,\delta_m(b)=ZW$，下面给出取值：
$\begin{aligned} Y=\prod_{i=1}^k p_i^{[\alpha_i>\beta_i]\alpha_i},X=\frac{\delta_m(a)}{Y}\\ W=\prod_{i=1}^k p_i^{[\alpha_i\le\beta_i]\beta_i},Z=\frac{\delta_m(b)}{W} \end{aligned}$
由上面阶的定理五，显然有 $\delta_m(a^X)=\tfrac{\delta_m(a)}{(\delta_m(a),X)}$ 显然 $X\mid \delta_m(a)$ 所以代入式子就有 $\delta_m(a^X)=Y$，同理我们有 $\delta_m(b^Z)=W$。

显然的 $(Y,W)=1$ 有根据最大公倍数的定义我们有 $YW=[\delta_m(a),\delta_m(b)]$ 由阶的定理四我们有
$\begin{aligned} \delta_m(a^Xb^Z)&=\delta_m(a^X)\delta_m(b^Z)\\ &= YW\\ &= [\delta_m(a),\delta_m(b)] \end{aligned}$
也就是说对于引理中提到的整数 $c$ 我们取 $a^Xb^Z$ 即可。

有了上面的引理，我们可以开始证明这个定理。我们可以知道我们一定存在一个 $g\in\mathbb Z$ 满足下式：
$\delta_p(g)=[\delta_p(1),\delta_p(2),\dots,\delta_p(p-1)]$
显然的对于根据这个式子我们可以得到 $\delta_p(j)\mid\delta_p(g)$ 其中 $j\in\{1,2,\dots,p-1\}$ 则显然这些 $j$ 都是同余方程 $x^{\delta_p(g)}\equiv1\pmod p$ 的根。根据拉格朗日定理 $\delta_p(g)\ge p-1$ 又因为费马小定理我们有 $\delta_p(g)\le p-1$ 所以说最后我们有 $\delta_p(g)=p-1=\varphi(p)$

也就是说一定存在一个 $g$ 是模 $p$ 的原根，原定理正确。

定理六　设 $p$ 是奇素数，$\alpha$ 是大于 $1$ 的整数，则模 $p^\alpha$ 的原根存在。

证明：

同样的我们还是需要一个引理。

引理：存在模 $p$ 的原根 $g$，使得 $g^{p-1}\not\equiv1\pmod{p^2}$

证明：显而易见的，如果原根 $g$ 不满足条件，我们可以尝试另一个原根 $g+p$ 显然这是一个存在的原根。
$\begin{aligned} (g+p)^{p-1}&\equiv g^{p-1}+\binom{p-1}{1}pg^{p-2}\\ &\equiv g^{p-1}+(p-1)pg^{p-2}\\ &\equiv g^{p-1}+p^2g^{p-2}-pg^{p-2}\\ &\equiv 1-pg^{p-2}\pmod{p^2}\\ &\not\equiv 1\pmod{p^2} \end{aligned}$

回到原题，我们证明若 $g$ 是一个满足上述引理的原根，对于任意的 $\alpha\in\mathbb N^\ast$，$g$ 是模 $p^\alpha$ 的原根。

首先我们有一个小结论：对于任意的 $\beta\in\mathbb N^\ast$，都有 $g^{\varphi(p^\beta)}=1+p^\beta k_\beta$ 其中 $p\nmid k_\beta$ 。显然的对于 $\beta=1$ 时，由 $g$ 的选取可知结论成立。然后我们可以小小的利用数学归纳法，也就是说如果对于 $\beta$ 如果结论成立，能否证明 $\beta+1$ 同样满足结论。
$\begin{aligned} g^{\varphi(p^{\beta+1})}&=\left(g^{\varphi(p^\beta)}\right)^p\\ &=(1+p^\beta k_\beta)^p\\ &\equiv 1+p^{\beta+1}k_\beta\pmod{p^{\beta+2}} \end{aligned}$
又 $p\nmid k_\beta$ 可知命题对于 $\beta+1$ 成立。也就是说这个命题对于任意的 $\beta\in\mathbb N^\ast$ 都成立。

接下来记 $\delta=\delta_{p^\alpha}(g)$，由欧拉定理可知 $\delta\mid\varphi(p^\alpha)$，又根据欧拉函数的计算公式我们可以有 $\varphi(p^\alpha)=p^\alpha\varphi(p)=p^\alpha(p-1)$ 代回原式有 $\delta\mid p^\alpha(p-1)$。

又因为 $g$ 是模 $p$ 的原根，我们就有 $g^\delta\equiv1\pmod{p^\alpha}$，所以我们可以设 $\delta=p^{\beta-1}(p-1)$ 这里 $1\le\beta\le\alpha$ 利用上面说的小结论可以有：
$g^{\varphi(p^\beta)}\not\equiv1\pmod{p^{\beta+1}}\Longrightarrow g^\delta\equiv1\pmod{p^{\beta+1}}$
然后根据 $g$ 的定义我们还有 $g^\delta\equiv1\pmod{p^\alpha}$ 可知 $\beta\ge\alpha$ 。

综上，$\beta=\alpha$ 也就是说 $\delta_{p^\alpha}(g)=p^{\alpha-1}(p-1)=\varphi(p^\alpha)$ 也就是说 $g$ 是模 $p^\alpha$ 的原根。

显然的在后面几个定理中欧拉函数的计算公式显得尤为重要，这里重复描述一遍，对于任意的整数 $n$ 其 $\varphi(n)$ 的值为（下式中 $p_i$ 为其质因数分解后所有的质因子）

$\varphi(n)=n\prod_{p_i\mid n}\left(1-\frac{1}{p_i}\right)$

定理七　设 $p$ 是奇素数，$\alpha$ 是正整数，则模 $2p^\alpha$ 的原根存在。

证明：

设 $g$ 是模 $p^\alpha$ 的原根，则显然 $g+p^\alpha$ 也是模 $p^\alpha$ 的原根。由于 $p^\alpha$ 一定是一个奇数，所以说在 $g$ 和 $g+p^\alpha$ 之间一定有一个数字是奇数，如果这个奇数是 $G$，则它满足 $(G,2p^\alpha)=1$ 。

由欧拉定理 $\delta_{2p^\alpha}(G)\mid\varphi(2p^\alpha)$ 又 $G^{\delta_{2p^\alpha}(G)}\equiv1\pmod{2p^\alpha}$ 故 $G^{\delta_{2p^\alpha}(G)}\equiv 1\pmod{p^\alpha}$

利用 $G$ 为模 $p^\alpha$ 的原根可知 $\varphi(p^\alpha)\mid\delta_{2p^\alpha}(G)$ 结合 $\varphi(p^\alpha)=\varphi(2p^\alpha)$ 可知 $G$ 为模 $2p^\alpha$ 的原根。

原根相关计算

接下来就是如何计算原根了，根据前人的证明，我们可以确定的是模 $p$ 的最小原根的大小大致在 $\Omega(\log p)$ 左右，这保证了暴力枚举最原根的可行性。

首先计算原根，我们要知道这个数字是否拥有原根，而根据上面的定义我们就知道只有 $m=2,4,p^\alpha,2p^\alpha$ 才有用，所以直接模拟即可（线性筛筛出素数与欧拉函数不再重复）

ll prime[N], phi[N];

inline bool CheckPrimitiveRoot(ll m) {
    if(m == 1) return false; // 1 无法被后续的判断中判断出无原根
    if(m == 2 || m == 4) return true;
    if(!(m & 1)) m >>= 1;
    if(!(m & 1)) return false;
    for(int i = 1; prime[i] * prime[i] <= m; i++) {
		if(m % prime[i] != 0) continue;
        while(m % prime[i] == 0) m /= prime[i];
        return m == 1;
    }
    return true;
}

然后是万众瞩目的最小原根计算，上面已经说过了最小原根的范围，所以说暴力枚举原根的范围可以在非常小，事实上我们枚举到 $100$ 就已经是非常大了。

vector<ll >st;

inline void Init(int m) {
    st.clear();
    for(int i = 2; i * i <= phi[m]; i++) {
        if(phi[m] % i == 0) {
            st.push_back(i);
            if(i * i != phi[m]) {
                st.push_back(phi[m] / i);
            }
        }
    }
}

inline bool Check(int g, int m) {
	if(Pow(g, phi[m], m) != 1) return false;
    for(auto &p : st) {
        if(Pow(g, phi[m]/p, m) == 1) {
            return false;
        }
    }
    return true;
}

inline int MinPRoot(int m) {
    if(m == 2) return 1;
    Init(m);
	for(int g = 2; g <= 100; g++) {
        if(Check(g, m)) return g;
    }
}

这就是计算原根的相关代码了，接下来就是另一部分 —— 离散对数的相关内容了。

算法基础：鸣火机变

指标的定义与性质

指标，也就是离散对数的定义：设 $g$ 是对模 $m$ 的原根，若 $g^r\equiv a\pmod m$，则称 $r$ 是以 $g$ 为底的 $a$ 对模 $m$ 的一个指标，记作 $k=\operatorname{ind}_g a$ 在不引起混淆的情况下可以记作 $\operatorname{ind} a$ 。显而易见我们有 $\operatorname{ind}_g 1=0,\operatorname{ind}_g g=1$ 。

关于指标的性质，其实和正常的对数差不多（设 $g$ 是模 $m$ 的原根，$(a,m)=(b,m)=1$ ）

$\operatorname{ind}_g(ab)\equiv\operatorname{ind}_ga+\operatorname{ind}_gb\pmod{\varphi(m)}$ 进而 $\forall n\in\mathbb N$，$\operatorname{ind}_g(a^n)\equiv n\operatorname{ind}_ga$ 。

证明：$g^{\operatorname{ind}_g(ab)}\equiv ab\equiv g^{\operatorname{ind}_g a}g^{\operatorname{ind}_gb}\equiv g^{\operatorname{ind}_ga+\operatorname{ind}_gb}\pmod m$
若 $g_1$ 也是模 $m$ 的原根，则 $\operatorname{ind}_ga\equiv\operatorname{ind}_{g_1}a\cdot\operatorname{ind}_gg_1\pmod{\varphi(m)}$ 。

证明：令 $x=\operatorname{ind}_{g_1}a$，则 $a\equiv {g_1}^x\pmod m$ 。又令 $y=\operatorname{ind}_g g_1$，则 $g_1\equiv g^y\pmod m$ 故 $a=g^{xy}\pmod m$，即 $\operatorname{ind}_ga\equiv xy\equiv\operatorname{ind}_{g_1}a\cdot\operatorname{ind}_gg_1\pmod{\varphi(m)}$ 。
$a\equiv b\pmod{m}\Longleftrightarrow\operatorname{ind}_ga=\operatorname{ind}_gb$

证明：
$\begin{aligned} \operatorname{ind}_ga=\operatorname{ind}_gb &\Longleftrightarrow\operatorname{ind}_ga\equiv\operatorname{ind}_gb\pmod{\varphi(m)}\\ &\Longleftrightarrow g^{\operatorname{ind}_ga}\equiv g^{\operatorname{ind}_gb}\pmod m\\ &\Longleftrightarrow a\equiv b\pmod m \end{aligned}$

这就是指标的定义和常用性质，接下来我们可以开始计算指标了。

基础的指标的计算

显而易见的指标问题可以看作求同余方程 $a^x\equiv b\pmod p$ 其中 $(a,p)=1$ 的最小非负整数根问题。根据欧拉定理我们有 $a^{\varphi(p)}\equiv 1\pmod p$，也就是说我们要枚举的 $x$ 的范围在 $\varphi(p)$ 以内，复杂度最大可达 $O(p)$ 级别，效率低下。

也就是说我们现在需要找到一个更优秀的方式来解决这个问题。于是说我们考虑分块，设每一块的大小为 $m$，令 $x=m\times i-j$ 其中 $j\in[0,m-1]$，则有 $a^{m\times i-j}\equiv b\pmod p$ 化简后得到 $(a^m)^i\equiv a^jb\pmod p$ 这时候我们只需要事先计算出 $a^j b$ 并存入哈希表，然后枚举 $i$ 就可以匹配出结果了。显然的复杂度应该是预处理 $a^jb$ 的 $O(m)$ 然后 $i$ 的取值范围就是 $\tfrac p m$（保证 $m * i$ 不越界即不超过 $p$ 的值）那么综合即为 $O(m+\tfrac p m)$ 显然的当 $m=\sqrt p$ 是可以取到最优值 $O(\sqrt p)$ 其中常数 $2$ 被忽略不计。

这种事先存下一定的结果，然后匹配的思想非常的熟悉，其实这个看似分块，实际上是 $\tt Meeting\ in\ the\ middle$ 思想的一种应用，这种算法被叫做 GSBS（Baby-Step Giant-Step 小步大步法）

代码到这里已经非常好写了：

inline int BSGS(int a, int b, int P, int d=1, int k=0) {
    int m = ceil(sqrt(P));
    if(b == 1) return 0;
    map<int , int >mp;
    for(int i = 0; i < m; i++) {
        mp[b] = i;
        b = 1LL * b * a % P;
    }
    a = Pow(a, m, P);
    for(int i = 1; i <= m; i++) {
        d = 1LL * d * a % P;
        if(mp.count(d)) {
            return i * m - mp[d] + k;
        }
    }
    return -1;
}

这个函数的调用就是和一开始的式子中一样的 $a^x\equiv b\pmod p$ 求 $x$ 中的变量一模一样，后面的 d,k

算法进阶：绥绥狐魅

非互素情况下的指标计算（拓展 BSGS）

所谓进阶其实就是对于更加特殊的这个同余方程的根的快速计算，所谓特殊，其实就是非互素，我们上面的式子是强制定义过 $(a,p)=1$ 的，这样的话推导更加房间有利于计算，现在的问题是如果我们不再拥有这个条件如何处理现在的问题。

首先我们要理解为什么刚刚是可以用 GSBS 解的，我们在上面的变形中，$a^{m\times i-j}$ 看作了 $(a^m)^ia^{-j}$ 也就是说这里利用了逆元的概念，由于 $(a,p)=1$ 所以说 $a$ 在模 $p$ 意义下的逆元显然存在，这就是为什么刚刚可以用 GSBS 来做。可是说现在 $(a,p)=1$ 的这个条件不在存在，没有逆元可以用了，所以就要另辟蹊径。

显然的我们如果没有互素的条件，可以手动让式子变得互素，也就是说我们如果有 $d_1=(a,p)$ 这时候可以考虑整体除掉这个 $d_1$ 来变成互素的状态，也就是说如果 $d_1\nmid b$ 这个方程就是无解的了。我们可以像下面一样一直除下去直到最后的结果和 $p$ 互素为止：

$\begin{aligned} &d_1=\left(a,m\right),\quad\frac{a}{d_1}\times a^{x-1}\equiv\frac{b}{d_1}\pmod{\frac{p}{d_1}}\\ &d_2=\left(\frac{a}{d_1},m\right),\quad\frac{a^2}{d_1d_2}\times a^{x-2}\equiv\frac{b}{d_1d_2}\pmod{\frac{p}{d_1d_2}}\\ &\cdots\\ &a\perp\frac{m}{d_1d_2\dots d_k},\quad \frac{a^k}{d_1d_2\dots d_k}\times a^{x-k}\equiv\frac{b}{d_1d_2\dots d_k}\pmod{\frac{p}{d_1d_2\dots d_k}} \end{aligned}$

如果我们设 $D=\prod_{i=1}^k d_i$ 由于我们有 $a\perp\tfrac{m}{D}$，所以说有 $\tfrac{a^k}{D}\perp\tfrac{m}{D}$，这时候就存在 $\tfrac{a^k}{D}$ 的逆元，把它除到同余方程右边就可以变成一开始方程的形式，但是最后我们求解出来的是 $x-k$ 所以答案需要再加上 $k$ 。

inline int exBSGS(int a, int b, int p) {
    if(b == 1) return 0;
    int g, d = 1, k = 0;
    while((g = __gcd(a, p)) != 1) {
        if(b % g != 0) return -1;
        k++; b /= g, p /= g;
        d = 1LL * d * (a / g) % p;
        if(b == d) return k;
    }
    // 这里的 GSBS 就是上面的函数，这里就体现出了后面两个系数的意思了
    return BSGS(a, b, p, d, k);
}