#include <iostream>
#include <fstream>
using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int x, y, d=1;

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

int main()
{

    int a, b;

    in>>a>>b;

    euclide(a, b, x, y, d);

while(x<0)
{
    x+=b;
}
    out<<x;

    return 0;
}