#include <iostream>
#include <fstream>

using namespace std;

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

void euclid(int &x,int &y,int a,int b){
    if(!b){
        x = 1;
        y = 0;
        return ;
    }
    euclid(x,y,b,a%b);
    int newx = y;
    int newy = x - y * (a/b);
    x = newx;
    y = newy;
}
int main()
{
    int x,y,a,b,d;
    in>>a>>b;
    euclid(x,y,a,b);
    x %= b;
    if(x < 0)
        x += b;
    cout<<x;
    return 0;
}