#include <iostream>
#include <fstream>
#define LL long long int
using namespace std;

LL A,B;

void gcdext(LL a, LL b,LL &x,LL &y){
    if (b==0){
        x=1;
        y=0;
        return;
    }

    LL x0,y0;
    gcdext(b,a%b,x0,y0);
    x=y0;
    y=x0-y0*(a/b);
}


int main(){
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    fin >> A >> B;
    LL x,y;
    gcdext(A,B,x,y);

    if (x<0) x=x+((-x/B)+1)*B;
    fout << x;

    return 0;
}