#include <fstream>
#include <iostream>

using namespace std;

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

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


int main()
{

    long long a, b;
    fin>>a>>b;
    long long x, y, d;
    euclid(a,b,d,x,y);

    while(x<0)
        x+=b;

    fout<<x;



    return 0;
}