#include <cstdio>

using namespace std;

FILE *f=fopen("inversmodular.in","r");
FILE *g=fopen("inversmodular.out","w");

void euclid(long long a, long long b, long long &d, long long &x, long long &y){
    if(!b){
        d=a;
        x=1;
        y=0;
        return;
    }
    long long x1,y1;
    euclid(b,a%b,d,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
}

int main()
{
    long long a,b,d,x,y;
    fscanf(f,"%lld%lld",&a,&b);
    euclid(a,b,d,x,y);
    if(x<0)
        x=b+x%b;
    fprintf(g,"%lld",x);

}