#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f ( "inversmodular.in" );
ofstream g  ( "inversmodular.out" );
void cmmdc(ll a,ll b,ll &x,ll &y)
{   if(!b)
    {   x=1;
        y=0;
    }
    else
    {   ll xi,yi;
        cmmdc(b,a%b,xi,yi);
        x=yi;
        y=xi-(a/b)*yi;
    }
}
int main()
{
    ll a,b;
    f>>a>>b;
    ll y,sol;
    cmmdc(a,b,sol,y);
    if(sol<=0) sol += b;

    g<<sol;
    return 0;
}