#include <cstdio>

using namespace std;

int a,b,n,k,l,c;

void cmmdc(int x,int y,int &k,int &l)
{
    if(y==0)
    {
        k=1;
        l=0;
        return;
    }
    int k1,l1;
    cmmdc(y,x%y,k1,l1);
    k=l1;
    l=k1-l1*(x/y);

}

int main()
{

   freopen("inversmodular.in","r",stdin);
   freopen("inversmodular.out","w",stdout);

    scanf("%d %d",&a,&n);
    cmmdc(a,n,k,l);
    if(k<0)
    {
        while(k<0)
            k+=n;
    }
    printf("%d",k);

    return 0;
}