「原根」与「阶」

2019-09-26 本文已影响0人雨落八千里

阶

定义：
设 $p>1,gcd(a,p)==1$ ，那么使得 $a^r≡1\ (mod\ \ \ p)$ 成立的最小正整数 $r$ 就称为 $a$ 模 $p$ 的阶.记作 $ord_p(a)$

并且 $ord_p(a)$ 总是可以整除 $φ(p)$ 即 $φ(p)$ 是 $ord_p(a)$

$\because a^{φ(p)}≡1\ (mod\ \ \ p)且a^{ord_p(a)}≡1\ (mod\ \ \ p)$

$设φ(p)=k*ord_p(a)+w \ \ \ \ \ \ \ \ \ \ w\in[0,ord_p(a)\ )$

$\therefore 1≡a^{φ(p)}≡(a^{ord_p(a)})^k*a^w≡1^k*a^w≡a^w\ (mod\ \ \ p)$
由定义， $ord_p(a)$ 是满足 $a^r≡1\ (mod\ \ \ p)$ 的最小正指数，而 $w<ord_p(a)$ ,故有 $w==0$ 因此 $φ(p)=k*ord_p(a)$
$\therefore ord_p(a)整除φ(p)$

原根

定义：
一个数 $a$ 是一个 $p$ 是原根，则 $a^i(\ mod\ \ p)$ 的结果两两不相同，其中， $i∈[1,φ(p)],a∈[1,φ(p)]。$
如果 $a$ 与 $p$ 是互质的整数且 $p>0$ ，那么当 $a\%p$ 的阶 $ord_p(a)=φ(p)$ 时，称 $a$ 为模 $p$ 的原根。
就是在多个 $a$ 都可以满足 $a^{φ(p)}≡1\ (mod\ \ \ p)$ 其中 ${φ(p)}$ 是使得 $a$ 模 $p$ 等于 $1$ 的最小正整数就称
$eg: p=5,φ(5)=4$
$1^4\%5=1;2^4\%5=1;3^4\%5=1;4^4\%5=1$
但是其中只有 $2$ 和 $3$ 是模 $5$ 的原根.

$\because 满足1^r\%5=1的最小正整数是1，$
$满足4^r\%5=1的最小正整数是2，满足a^r≡1\ (mod\ \ \ p)的最小正整数不是φ(p)$

$\therefore 1和4不是模5的原根$

质数 $p$ 原根求法：
给出一个质数 $p,φ(p)=p-1$
将 $φ(p)$ 通过唯一分解定理可以得到： $φ(p)=P_1^{k_1}*P_2^{k_2}*...*P_n^{k_n}$ 其中 $(P_1,P_2,..,P_n)$ 都是质数
然后枚举 $a$ ,若 $a^{\frac{φ(p)}{p_i}}\neq 1(mod\ \ \ p) \ \ \ i \in(1,2,...,n)$
则 $a$ 是模 $p$ 的一个原根

原根性质：

所有的质数 $m$ 都可以找到原根，且个数是 $φ(m-1)$

不是所有的整数都有原根

若模 $m$ 可以找到原根，那么 $m$ 一定可以表示成 $\{2,4,p^n，2·p^n\}$ 这些形式的一种，其中 $p$ 是奇质数

若模 $m$ 可以找到原根，那么它能找到原根的个数一定是 $φ(φ(m))$

模 $m$ 的最小原根大小是 $O_{m_{0.25}}$ 的。所以有些东西你枚举就够了

51nod-1135 求最小原根

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e5+10;
int p[M],cnt;
void ol(ll n)//将φ(m)唯一定理分解
{
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            p[cnt++]=i;
        }
        while(n%i==0)
        {
            n/=i;
        }
    }
    if(n>1)
    {
        p[cnt++]=n;
    }
    return ;
}
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    ll base=a;
    while(n)
    {
        if(n&1)
        {
            ans=ans*base%mod;
        }
        base=base*base%mod;
        n>>=1;
    }
    return ans%mod;
}
ll query(ll n)
{
    if(n==2||n==4)
    {
        return n-1;
    }
    cnt=0,ol(n-1);
    for(int i=2;i<n;i++)//从小到大遍历a
    {
        int flag=1;
        for(int j=0;j<cnt;j++)
        {
            if(qpow(i,(n-1)/p[j],n)==1)//根据原根求法
            {
                flag=0;
                break;
            }
        }
        if(flag==1)//输出最小的原根
        {
            return i;
        }
    }
}
int main( )
{
    ll n;
    while(~scanf("%lld",&n))
    {
        printf("%lld\n",query(n));
    }
    return 0;
}

「原根」与「阶」

阶

原根

猜你喜欢

热点阅读