#include <algorithm>
using namespace std;

int a,n,inv;

inline int euclid (int a,int b,int &x,int &y)
{
    int d,x0,y0;

    if (!b)
    {
        x=1; y=0;
        return a;
    }
    d=euclid (b,a%b,x0,y0);
    x=y0; y=x0-(a/b)*y0;

    return d;
}


int main ()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);
    int nr;

    scanf ("%d%d",&a,&n);
    euclid (a,n,inv,nr);
    if (inv<0)
        inv=n+inv%n;
    printf ("%d",inv);

    return 0;
}