#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int a, n, x, y;

void cmmdc(int a, int b, int &x, int &y){
    if(b==0){x=1; y=0;return;}
    int x0=0, y0=0;
    cmmdc(b, a%b, x0, y0);
    x=y0;
    y=x0-(a/b)*y0;
}

int main(){
    f>>a>>n;
    cmmdc(n, a, x, y);
    while(y<0)
        y+=a;
    g<<y<<"\n";
    return 0;
}