#include <bits/stdc++.h>

using namespace std;
#define ll long long

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");



ll a,n,y,valoare;

 //ll fact[20000];

//void precalcul(){
 //ll i; fact[0]=1;
 //for (i

void gcd(ll &x,ll &y,ll a, ll b)
{
    if(b==0)
        x=1,y=0;
    else
    {
        gcd(x,y,b,a%b);
        ll aux=x;
        x=y;
        y=aux-y*(a/b);
    }
}
/*ll comb(ll n, ll k)
{
    ll t, inv ,y;ll valoare;
    t=fact[k]*fact[n-k]%MOD;
    gcd(inv,y,t,MOD);
    if (inv<=0)inv=MOD+inv%MOD;
    return (fact[n]*inv)%MOD;
}*/

int main()
{
    fin>>a>>n;
    ll inv;
    gcd(valoare,y,a,n);
    if(valoare<=0)
        valoare+=n;
    fout<<valoare;
    return 0;
}