Expansion of number theory Euclid

Summary ：

First, let's look at what it looked like before evolution , That is, the well-known Euclidean algorithm , Use the division method to find gcd.

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

And expand Euclid , It expands the application of Euclidean algorithm . It's solving gcd On the basis of , Solved an additional problem —— solve General solution of binary indefinite equation , namely $ax+by=m$, among $a$,$b$,$m$ For known ,$x$,$y$ Is an unknown quantity , Demand solution $x$ and $y$ Solution .
 

Text ：

First , To meet the The necessary and sufficient conditions for the solution of the equation ：$[(a,b)|m]$.
If not satisfied , Then the equation has no solution .
ps: $(a,b)$ Express $a$ and $b$ Maximum common divisor of , and $|$ It's an integer division sign , That is to say $m$ yes $gcd(a,b)$ Multiple . I don't know how to prove this , It's easy to get , Readers think for themselves .
 
So , The original equation can be seen as ,$ax+by=t\times gcd(a,b)$.
You can find , We just need to find out $ax+by=gcd(a,b)$ Solution , Then multiply it by $t$ that will do .
 

The key is coming. ！！！

First, we ask for a set of special solutions .
 
We recursively will $a$ and $b$ Perform rolling Division , When reaching the recursive boundary ,$a=gcd(a,b),b=0$.
here equation $gcd(a,b)x+0\ast y=gcd(a,b)$ We can easily get a set of solutions ：$x=1,y=0$.
 
We From a higher level $a$ and $b$ Change to the next level $a$ and $b$ after , The solution of the equation is also from the upper layer $x$ and $y$ Into the next layer $x$ and $y$. So while we are recursively backtracking , Through the lower $x$ and $y$ To calculate the upper layer $x$ and $y$.（ The specific steps are omitted ）
therefore , We get a set of special solutions of the equation $x_0\times t$,$y_0\times t$.
therefore , We also get the general solution of the equation $x=x_{0}t+\frac{kb}{gcd(a,b)},y=y_{0}t-\frac{ka}{gcd(a,b)}$.
 

Templates ：

ll ex_gcd(ll a,ll b,ll& x,ll& y)
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;
    }
    ll g=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return g;
}

application （exgcd Inverse element ）： Portal

On inverse element , That is to say $a^{-1}$, I won't go into details here .
a In the mold p In the sense of A necessary and sufficient condition for the existence of inverse elements ：$[gcd(a,p)=1]$
 
When modulus p Prime number , You can use Fermat's small Theorem ：$a^{p-1}\equiv 1(modp)$
We demand $ax\equiv 1(modp)$, here $x$ As long as it equals $a^{p-2}$ Just fine .
 
Then when the modulus p When not prime , That's it Expand Euclid La .
Demand solution $ax\equiv 1(modp)$. In fact, it is to solve $ax+py=1$ A set of special solutions . See light suddenly , I won't talk about it later .
 

Templates （ Tuoou inverse element ）：

ll ex_gcd(ll a,ll b,ll& x,ll& y)
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;
    }
    ll ans=ex_gcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ans;
}

ll inv(ll a,ll mod)// Existence of inverse element condition ：gcd(a,mod)=1
{
    
    ll x,y;
    ll g=ex_gcd(a,mod,x,y);
    if(g!=1)return -1;
    return (x%mod+mod)%mod;
}