#include <cstdio>

using namespace std;

int a,n,k,l;

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-(x/y)*l1;
}

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

    scanf("%d %d",&a,&n);

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

    return 0;
}