Explanation of order and primitive root of number theory

Preface ：

I wanted to write BSGS Algorithm , however I want to play a game today I think it would be better to write the original root first , So let's focus on what is primordial root today 、 Which integers have original roots 、 Properties and solutions of primitive roots .
 

summary ：

In order to reduce the hindsight , Just a quick introduction Euler function $\phi (x)$, The main part is followed by the introduction of the integral function .(ps: The symbol in the book says $\varphi (x)$, Yes, but online $\phi (x)$, But it doesn't matter )
Euler function $\phi (x)$ The function value of is , Less than $x$ And with the $x$ The number of Coprime positive integers .
such as $\phi (6)=2$, Because of less than $6$ In the positive integer of , have only $1$ And $5$ With its mutual quality .
Easy to find , When $p$ When it's a prime number , Yes $\phi (x)=p-1$.
And Euler's Theorem ： if $gcd(a,n)=1$, be $a^{\phi (n)}\equiv 1(modp)$.
 
About these first , To the body .
 

Order of integer ：

What is step ？
set up $a$ and $n$ Is a coprime integer ,$a\ne 0,n>0$, bring $a^x\equiv 1(modn)$ The smallest positive integer established $x$, be called $a$ model $n$ The order of , The symbol is $or{d}_{n}a$.
 
For example, requirements $2$ model $7$ The order of , Let's list them one by one ,
$2^1\equiv 2(mod7),2^2\equiv 4(mod7),2^3\equiv 1(mod7)$.
Then we call $2$ model $7$ The order is $3$, Write it down as $or{d}_{7}2=3$.
 
Now let's look at the equation $a^x\equiv 1(modn)$.
So obviously according to Euler's Theorem , We can know $\phi (n)$ It's a solution to the equation , But it is not necessarily the smallest , So it's not necessarily order , And when $\phi (n)$ yes $a$ model $n$ Order time of , We call $a$ by $n$ One of the original roots , This will be introduced later .

Now let's go on .
 
A theorem ： if $gcd(a,n)=1$, be $x_0$ It's the equation $a^x\equiv 1(modn)$ The necessary and sufficient condition for a solution of is $or{d}_{n}a|x$.( among $|$ It's an integer division sign , Express $or{d}_{n}a$ to be divisible by $x$)
This necessity is well proved , since $a^{or{d}_{n}a}\equiv 1(modn)$, that $a^{k\times or{d}_{n}a}\equiv 1(modn)$ Of course, it also holds true .
Then sufficiency , Suppose there is $x1$ Not divisible $x_0$ And satisfy the equation , Make $x_1=k\times or{d}_{n}a+d$( among $d$ Not divisible $or{d}_{n}a$) Satisfy the equation , that $d$ Certain ratio $or{d}_{n}a$ Small , And meet $a^d\equiv 1(modn)$, Then it's the original root .
This proves that .

Theorem 2 ： if $gcd(a,n)=1$, be $or{d}_{n}a$ aliquot $\phi (n)$.
From the front, you can also think of , And it is obvious from theorem 1 .
At this time, it is easy to think of one $o(\sqrt{n}log)$ The way to find the order , because $n$ The order of must be $\phi (n)$ Factor of , So we can enumerate its factors , Let's see if the conditions are met .

Theorem 3 ： if $gcd(a,n)=1$, be $a^i\equiv a^j(modn)$ If and only if $i\equiv j(modor{d}_{n}a)$.
Theorem is more important , Think about it yourself .

Theorem 4 ： if $or{d}_{n}a=t$, And $u$ As a positive integer , Then there are $or{d}_n(a^u)=\frac{t}{gcd(t,u)}$ .
For example, experience ,$2^3\equiv 1(mod7)$, Then there is $8^1\equiv 1(mod7)$. That's what it is $3$ Factor of , It's much easier to understand in this way .
 
 

Primordial root ：

When $a$ model $n$ The order is $\phi (n)$, That is to say, if and only if $x$ yes $\phi (n)$ Multiple , bring $a^x\equiv 1(modn)$ establish , At this time said $a$ by $n$ The original root .
 
So I know $n$ The original root $a$ after , What are the benefits , Let me give you an example .
Let's take 998244353 The original root 3, Let's take a prime number $7$ One of the original roots $3$, Then list $3$ Power module of $7$.
$3^1\equiv 3(mod7),3^2\equiv 2(mod7),3^3\equiv 6(mod7),3^4\equiv 4(mod7),3^5\equiv 5(mod7),3^6\equiv 1(mod7)$.
Then it is found that these residuals form a module $7$ The complete residue system of $1,2,3,4,5,6$, That is, for any $a$, Can be found $x_0$ bring $3^{x_0}\equiv a(mod7)$.
This is the case of prime numbers , Now let's look at the case of Kangkang non prime numbers , for $18$ One of the original roots $5$. Then list $5$ Power module of $18$.
$5^1\equiv 5(mod18),$
$5^2\equiv 7(mod18),$
$5^3\equiv 17(mod18),$
$5^4\equiv 13(mod18),$
$5^5\equiv 11(mod18),$
$5^6\equiv 1(mod18).$
$5^7\equiv 5(mod18),$
$5^8\equiv 7(mod18),$
$5^9\equiv 17(mod18),$
$5^{10}\equiv 13(mod18),$
$5^{11}\equiv 11(mod18),$
$5^{12}\equiv 1(mod18).$
$5^{13}\equiv 5(mod18),$
$5^{14}\equiv 7(mod18),$
$5^{15}\equiv 17(mod18),$
$5^{16}\equiv 13(mod18),$
$5^{17}\equiv 11(mod18),$
$5^{18}\equiv 1(mod18).$
It is easy to find that $6$ One for a group , So this one $6$ What is it? ？
It's actually $\phi (18)=6$. Then the number appears $1,5,7,11,13,17$, It is with $18$ Coprime $6$ How many .
Then the case of prime numbers above makes sense .
So we can get ,
A theorem ： if $gcd(a,n)=1$, be $a^1,a^2,\dots \dots ,a^{\phi (n)}$ Form a mold $n$ The irreducible residue system of .
If you understand it, you won't prove it .
And when $p$ When it's a prime number , We can solve the equation $x^5\equiv a(modp)$ The problem is replaced by solving $g^{5x}\equiv a(modp)$, among $g$ yes $p$ The original root , because $g$ The power of is a module $n$ The complete residue system of , So it can be used $g^x$ To replace $x$, In this way, we only ask for the of the new equation $x_0$, Then the solution of the original equation can be found .
 
next ,
Theorem 2 ： If a number $n$ It has roots , So how many different primitive roots does he have ,
The answer is $\phi (\phi (n))$ individual .
False proof ： From the previous order, theorem 4 , We can know $or{d}_n(a^u)=\frac{t}{gcd(t,u)}$, So when $a$ by $n$ The original root of , There is $or{d}_{n}a=\phi (n)$.
So we get ,$or{d}_n(a^u)=\frac{\phi (n)}{gcd(\phi (n),u)}$.
So we should make $or{d}_n(a^u)$ be equal to $\phi (n)$, It's about meeting $gcd(\phi (n),u)$, stay $1$ To $\phi (n)-1$ Naturally, there are $\phi (\phi (n))$ One that meets the conditions .

Eating out , Come back and write .

Now study which numbers have primitive roots , That is to say The existence of primitive roots .
Because I just had dinner , I'm lazy .
First prove that prime numbers have primitive roots .
Then prove that the powers of odd prime numbers have primitive roots .
Then discuss about $2$ The power of , Find out $2$ and $4$ It has primitive roots , other $2$ There is no primitive root to the power of .
And then find out $2$ The power of the odd prime number also has the original root .
Finally, prove that the rest have no original root .
therefore , Come to the conclusion ：
Theorem 3 ：$2$ and $4$, And the positive integer power of odd prime numbers $p^k$, as well as $2$ Multiply by the positive integer power of odd prime number $2p^k$ They all have primitive roots .
 
 
Last , Study how to find $p$ The original root . Portal
First give a solution to violence .（ There is no second ）
First judge whether there is an original root .
$2$ The original root of is $1$,$3$ The original root of is 2,$4$ The original root of is $3$ Direct special judgment .
Then we enumerate violence $[2,p-1]$, Then judge whether it is $p$ The original root , When enumerating, of course, it is necessary to ensure mutual quality with modules .
As for judging $i$ Is it right? $p$ The original root , Just see if it exists $x_0$ Than $\phi (p)$ Small , And meet $i^{x_0}\equiv 1(modp)$.
But we're not going to enumerate one by one $x_0$, Because we know that its order satisfies the equation , And the multiple of order also satisfies the equation . So we just need to $\phi (p)$ The qualitative factor is decomposed into $p_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}$.
Then enumerate each prime factor , Judge whether it exists $i^{\frac{\phi (p)}{p_j}}\equiv 1(modp)$. If exist , Description order ratio $\phi (p)$ Small , Is not the original root ; conversely , Is the original root .

Do wonders vigorously , Worthy of great efforts .
Finally, post the code ：

#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;// There is no original root. Return -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;
}