#include <fstream>

using namespace std;

FILE* f=freopen("inversmodular.in","r",stdin);
FILE* o=freopen("inversmodular.out","w",stdout);

long a,n;

void Euclid(long a, long b, long *x, long *y)
{
    if(!b)
    {
        *x=1;
        *y=0;
    }
    else
    {
        long x0,y0;
        Euclid(b,a%b,&x0,&y0);
        *y=x0-a/b*y0;
        *x=y0;
    }
}

int main()
{
    scanf("%ld%ld",&a,&n);

    long x,y; x=y=0;

    Euclid(a,n,&x,&y);

    while(x<0) x+=n;

    printf("%ld",x);

    return 0;
}