数论之阶与原根讲解

大大源码 • 2023年4月30日 pm10:36 • 其他

前言：

本来想写BSGS算法，但是~~笔者今天想打游戏~~ 感觉先写原根会更好一点，所以我们今天重点讨论一下什么是原根、哪些整数有原根、原根的性质和求解。

提要：

为了减少后面的阅读障碍，先简单介绍一下欧拉函数

(

)

\varphi(x)

$φ (x)$ ，主要部分后面放积性函数那介绍。(ps:书上符号写的是

(

)

\phi(x)

$ϕ (x)$ ，但网上写的是

(

)

\varphi(x)

$φ (x)$ ，不过这不重要)
欧拉函数

(

)

\varphi(x)

$φ (x)$ 的函数值是，小于

$x$ 且与

$x$ 互质的正整数的个数。
比如

(

)

\varphi(6)=2

$φ (6) = 2$ ，因为小于

$6$ 的正整数中，仅有

$1$ 与

$5$ 与其互质。
容易发现，当

$p$ 为素数时，有

(

)

−

\varphi(x)=p-1

$φ (x) = p - 1$ 。
还有欧拉定理：若

(

)

gcd(a,n)=1

$g c d (a, n) = 1$ ，则

(

)

≡

(

)

a^{\varphi(n)}\equiv1(mod\;p)

$a^{φ (n)} \equiv 1 (m o d p)$ 。

差不多先这些，开始正文。

整数的阶：

什么是阶？
设

$a$ 和

$n$ 是互素的整数，

≠

a\neq 0,n>0

$a \neq = 0, n > 0$ ，使得

≡

(

)

a^{x}\equiv1(mod\;n)

$a^{x} \equiv 1 (m o d n)$ 成立的最小正整数

$x$ ，称为

$a$ 模

$n$ 的阶，符号表示为

ord_{n}a

$o r d_{n} a$ 。

比如要求

$2$ 模

$7$ 的阶，我们一一列举，

≡

(

)

，

≡

(

)

，

≡

(

)

2^{1}\equiv2(mod\;7)，2^{2}\equiv4(mod\;7)，2^{3}\equiv1(mod\;7)

$2^{1} \equiv 2 (m o d 7) ， 2^{2} \equiv 4 (m o d 7) ， 2^{3} \equiv 1 (m o d 7)$ 。
那么我们称

$2$ 模

$7$ 的阶就是

$3$ ，记为

ord_{7}2=3

$o r d_{7} 2 = 3$ 。

现在我们观察方程

≡

(

)

a^{x}\equiv1(mod\;n)

$a^{x} \equiv 1 (m o d n)$ 。
那么显然根据欧拉定理，我们可以知道

(

)

\varphi(n)

$φ (n)$ 是方程的一个解，但它未必是最小的，所以不一定是阶，而当

(

)

\varphi(n)

$φ (n)$ 是

$a$ 模

$n$ 的阶时，我们称

$a$ 为

$n$ 的一个原根，这个放后面介绍。

现在继续来讲阶。

定理一：若

(

)

gcd(a,n)=1

$g c d (a, n) = 1$ ，则

x_{0}

$x_{0}$ 是方程

≡

(

)

a^{x}\equiv1(mod\;n)

$a^{x} \equiv 1 (m o d n)$ 的一个解的充要条件是

∣

ord_{n}a|x

$o r d_{n} a ∣ x$ 。(其中

∣

$∣$ 是整除符号，表示

ord_{n}a

$o r d_{n} a$ 整除

$x$ )
这个必要性很好证明，既然

≡

(

)

a^{ord_{n}a}\equiv1(mod\;n)

$a^{o r d_{n} a} \equiv 1 (m o d n)$ ，那

≡

(

)

a^{k\times ord_{n}a}\equiv1(mod\;n)

$a^{k \times o r d_{n} a} \equiv 1 (m o d n)$ 当然也成立。
然后充分性，假设存在

$x 1$ 不整除

x_{0}

$x_{0}$ 且满足方程，令

x_{1}=k\times ord_{n}a+d

$x_{1} = k \times o r d_{n} a + d$ (其中

$d$ 不整除

ord_{n}a

$o r d_{n} a$ )满足方程，那么

$d$ 一定比

ord_{n}a

$o r d_{n} a$ 小，且满足

≡

(

)

a^{d}\equiv1(mod\;n)

$a^{d} \equiv 1 (m o d n)$ ，那它才是原根嘛。
这样就证好了。

定理二：若

(

)

gcd(a,n)=1

$g c d (a, n) = 1$ ，则

ord_{n}a

$o r d_{n} a$ 能整除

(

)

\varphi(n)

$φ (n)$ 。
前面看下来应该也能想到，且由定理一发现显然嘛。
这时候我们容易想到一个

(

)

o(\sqrt{n} log)

$o (n l o g)$ 求阶的办法，因为

$n$ 的阶一定是

(

)

\varphi(n)

$φ (n)$ 的因子，所以可以暴力枚举其因子，再看看是不是满足条件。

定理三：若

(

)

gcd(a,n)=1

$g c d (a, n) = 1$ ，则

≡

(

)

a^i\equiv a^j(mod\;n)

$a^{i} \equiv a^{j} (m o d n)$ 的充要条件是

≡

(

)

i\equiv j(mod\;ord_{n}a)

$i \equiv j (m o d o r d_{n} a)$ 。
定理比较重要，自己意会一下。

定理四：若

ord_{n}a=t

$o r d_{n} a = t$ ，且

$u$ 为正整数，则有

(

)

(

)

ord_{n}(a^{u})=\frac{t}{gcd(t,u)}

$o r d_{n} (a^{u}) = \frac{t}{g c d ( t , u )}$ 。
打个比方体会一下，

≡

(

)

2^3\equiv1(mod\;7)

$2^{3} \equiv 1 (m o d 7)$ ,那么就有

≡

(

)

8^1\equiv1(mod\;7)

$8^{1} \equiv 1 (m o d 7)$ 。其实就是这个

$3$ 的因子，这样想就容易理解多了吧。

原根：

当

$a$ 模

$n$ 的阶为

(

)

\varphi(n)

$φ (n)$ ，也就是说当且仅当

$x$ 是

(

)

\varphi(n)

$φ (n)$ 的倍数，使得

≡

(

)

a^{x}\equiv1(mod\;n)

$a^{x} \equiv 1 (m o d n)$ 成立，此时称

$a$ 为

$n$ 的原根。

那么知道了

$n$ 的原根

$a$ 后，有什么好处呢，可以举一个例子。
~~我们举998244353的原根3，~~ 我们举一个素数

$7$ 的一个原根

$3$ ，然后列举

$3$ 的幂次模

$7$ 。

≡

(

)

，

≡

(

)

，

≡

(

)

，

≡

(

)

，

≡

(

)

，

≡

(

)

3^{1}\equiv3(mod\;7)，3^{2}\equiv2(mod\;7)，3^{3}\equiv6(mod\;7)，3^{4}\equiv4(mod\;7)，3^{5}\equiv5(mod\;7)，3^{6}\equiv1(mod\;7)

$3^{1} \equiv 3 (m o d 7) ， 3^{2} \equiv 2 (m o d 7) ， 3^{3} \equiv 6 (m o d 7) ， 3^{4} \equiv 4 (m o d 7) ， 3^{5} \equiv 5 (m o d 7) ， 3^{6} \equiv 1 (m o d 7)$ 。
然后发现这些余数构成了一个模

$7$ 的完全剩余系

1,2,3,4,5,6

$1, 2, 3, 4, 5, 6$ ，也就是对于任意

$a$ ，都可以找到

x_{0}

$x_{0}$ 使得

≡

(

)

3^{x_{0}}\equiv a(mod\;7)

$3^{x_{0}} \equiv a (m o d 7)$ 。
这是素数的情况，现在我们来康康非素数的情况，举

$18$ 的一个原根

$5$ 。然后列举

$5$ 的幂次模

$18$ 。

≡

(

)

，

5^{1}\equiv5(mod\;18)，

$5^{1} \equiv 5 (m o d 18) ，$

≡

(

)

，

5^{2}\equiv7(mod\;18)，

$5^{2} \equiv 7 (m o d 18) ，$

≡

(

)

，

5^{3}\equiv17(mod\;18)，

$5^{3} \equiv 17 (m o d 18) ，$

≡

(

)

，

5^{4}\equiv13(mod\;18)，

$5^{4} \equiv 13 (m o d 18) ，$

≡

(

)

，

5^{5}\equiv11(mod\;18)，

$5^{5} \equiv 11 (m o d 18) ，$

≡

(

)

。

5^{6}\equiv1(mod\;18)。

$5^{6} \equiv 1 (m o d 18) 。$

≡

(

)

，

5^{7}\equiv5(mod\;18)，

$5^{7} \equiv 5 (m o d 18) ，$

≡

(

)

，

5^{8}\equiv7(mod\;18)，

$5^{8} \equiv 7 (m o d 18) ，$

≡

(

)

，

5^{9}\equiv17(mod\;18)，

$5^{9} \equiv 17 (m o d 18) ，$

≡

(

)

，

5^{10}\equiv13(mod\;18)，

$5^{10} \equiv 13 (m o d 18) ，$

≡

(

)

，

5^{11}\equiv11(mod\;18)，

$5^{11} \equiv 11 (m o d 18) ，$

≡

(

)

。

5^{12}\equiv1(mod\;18)。

$5^{12} \equiv 1 (m o d 18) 。$

≡

(

)

，

5^{13}\equiv5(mod\;18)，

$5^{13} \equiv 5 (m o d 18) ，$

≡

(

)

，

5^{14}\equiv7(mod\;18)，

$5^{14} \equiv 7 (m o d 18) ，$

≡

(

)

，

5^{15}\equiv17(mod\;18)，

$5^{15} \equiv 17 (m o d 18) ，$

≡

(

)

，

5^{16}\equiv13(mod\;18)，

$5^{16} \equiv 13 (m o d 18) ，$

≡

(

)

，

5^{17}\equiv11(mod\;18)，

$5^{17} \equiv 11 (m o d 18) ，$

≡

(

)

。

5^{18}\equiv1(mod\;18)。

$5^{18} \equiv 1 (m o d 18) 。$
很容易发现以

$6$ 个为一组，那这个

$6$ 是什么呢？
其实是

(

)

\varphi(18)=6

$φ (18) = 6$ 。然后出现的数字

1,5,7,11,13,17

$1, 5, 7, 11, 13, 17$ ，正是与

$18$ 互质的那

$6$ 个数啊。
那么前面素数的情况也说得通了。
所以我们就可以得到，
定理一：若

(

)

gcd(a,n)=1

$g c d (a, n) = 1$ ，则

…

(

)

a^{1},a^{2},……,a^{\varphi(n)}

$a^{1}, a^{2}, \dots \dots, a^{φ (n)}$ 构成模

$n$ 的既约剩余系。
大概懂了就不证明了。
而当

$p$ 为素数时，我们就可以将求解方程

≡

(

)

x^{5}\equiv a(mod\;p)

$x^{5} \equiv a (m o d p)$ 的问题代换为求解

≡

(

)

g^{5x}\equiv a(mod\;p)

$g^{5 x} \equiv a (m o d p)$ ，其中

$g$ 是

$p$ 的原根，因为

$g$ 的幂次是模

$n$ 的完全剩余系，所以可以用

g^{x}

$g^{x}$ 来代换

$x$ ，这样我们只要求出新方程的

x_{0}

$x_{0}$ ，那么原方程的解就可以求出来了。

下一个，
定理二：如果一个数

$n$ 有原根，那么他有多少个不同余的原根，
答案是

(

)

\varphi(\varphi(n))

$φ (φ (n))$ 个。
伪证明：由前面阶那里的定理四，我们可以知道

(

)

(

)

ord_{n}(a^{u})=\frac{t}{gcd(t,u)}

$o r d_{n} (a^{u}) = \frac{t}{g c d ( t , u )}$ ，那么当

$a$ 为

$n$ 的原根时，就有

(

)

ord_{n}a=\varphi(n)

$o r d_{n} a = φ (n)$ 。
于是我们得到，

(

)

(

)

(

)

ord_{n}(a^{u})=\frac{\varphi(n)}{gcd(\varphi(n),u)}

$o r d_{n} (a^{u}) = \frac{φ ( n )}{g c d ( φ ( n ) , u )}$ 。
所以要使

(

)

ord_{n}(a^{u})

$o r d_{n} (a^{u})$ 等于

(

)

\varphi(n)

$φ (n)$ ，就要满足

(

)

gcd(\varphi(n),u)

$g c d (φ (n), u)$ ，在

$1$ 到

(

)

−

\varphi(n)-1

$φ (n) - 1$ 范围里自然就有

(

)

\varphi(\varphi(n))

$φ (φ (n))$ 个满足条件的。

吃饭去了，回来再写。

现在研究哪些数是有原根的，也就是原根的存在性。
因为刚吃了饭，我懒了。
先证明素数都是有原根的。
再证明奇素数的幂都是有原根的。
然后讨论关于

$2$ 的幂次，发现

$2$ 和

$4$ 是有原根的，其他

$2$ 的幂次都没有原根。
然后再发现

$2$ 乘上奇素数的幂也是有原根的。
最后再证明剩下的都没有原根。
于是，得出结论：
定理三：

$2$ 和

$4$ ，和奇素数的正整数幂次

p^{k}

$p^{k}$ ，以及

$2$ 乘上奇素数的正整数幂次

2p^{k}

$2 p^{k}$ 都是有原根的。

最后，再研究一下怎么求

$p$ 的原根。传送门
先给出一种暴力的解法。（没有第二种了）
先判断有无原根。

$2$ 的原根是

$1$ ，

$3$ 的原根是2，

$4$ 的原根是

$3$ 直接特判掉。
然后我们暴力枚举

[

−

]

[2,p-1]

$[2, p - 1]$ ，再判断它是不是

$p$ 的原根，枚举的时候当然还要保证与模数互质。
至于要判断

$i$ 是不是

$p$ 的原根，只要看是否存在

x_{0}

$x_{0}$ 比

(

)

\varphi(p)

$φ (p)$ 小，且满足

≡

(

)

i^{x_{0}}\equiv 1(mod\;p)

$i^{x_{0}} \equiv 1 (m o d p)$ 。
但是我们不至于再去一个一个枚举

x_{0}

$x_{0}$ ，因为我们知道它的阶是满足方程的，而阶的倍数也是满足方程的。所以我们只要将

(

)

\varphi(p)

$φ (p)$ 质因子分解成

…

p_{1}^{k_{1}}p_{2}^{k_{2}}…p_{n}^{k_{n}}

$p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$ 。
然后枚举每个质因子，判断是否存在

(

)

≡

(

)

i^{\frac{\varphi(p)}{p_{j}}}\equiv1(mod\;p)

$i^{\frac{φ ( p )}{p _{j}}} \equiv 1 (m o d p)$ 。若存在，说明阶比

(

)

\varphi(p)

$φ (p)$ 小，则不是原根；反之，则是原根。

大力出奇迹，不愧是大力。
最后贴代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

ll gcd(ll a,ll b)
{
    return b?gcd(b,a%b):a;
}

ll fpow(ll a,ll n,ll p)
{
    ll sum=1,base=a%p;
    while(n!=0)
    {
        if(n%2)sum=sum*base%p;
        base=base*base%p;
        n/=2;
    }
    return sum;
}

vector<ll> getPrimFac(ll n)
{
    vector<ll>fac;
    fac.clear();
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            fac.push_back(i);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)fac.push_back(n);
    return fac;
}

bool hasRoot(ll n)
{
    if(n==2||n==4)return true;
    if(n<=1||n%4==0)return false;
    ll num=0;
    while(n%2==0)n/=2;
    for(ll i=3;i*i<=n;i++)
    {
        if(n%i==0)
        {
            num++;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)num++;
    if(num==1)return true;
    return false;
}

ll getPhi(ll n)
{
    ll ans=n;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

ll getRoot(ll n)
{
    if(!hasRoot(n))return -1;//不存在原根返回-1
    if(n==2)return 1;
    if(n==3)return 2;
    if(n==4)return 3;
    ll w=getPhi(n);
    vector<ll>fac=getPrimFac(w);
    for(ll i=2;i<w;i++)
    {
        if(gcd(i,n)!=1)continue;
        ll is=1;
        for(ll j=0;j<fac.size();j++)
        {
            if(fpow(i,w/fac[j],n)==1)is=0;
        }
        if(is)return i;
    }
    return -1;
}

int main()
{
    ll p;
    scanf("%lld",&p);
    printf("%lld\n",getRoot(p));
    return 0;
}