#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
typedef long long ll;
ll cmd(ll a,ll b)
{
    ll r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void euclide(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(b==0)
        d=a,x=1,y=0;
    else
    {
        ll x0=0,y0=0;
        euclide(b,a%b,d,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}
ll a,n,x,y,d;
int main()
{
    fin>>a>>n;
    euclide(a,n,d,x,y);
    if(x<0)
        x+=((-x+n)/n)*n;
    else
        x=x%n;
    fout<<x;
    return 0;
}