#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");

void euclid_extins(long long a, long long b, long long &x, long long &y)
{
    if(b==0)
    {
        x=1;
        y=0;
    }
    else
    {
        long long x1, y1;
        euclid_extins(b, a%b, x1, y1);
        x=y1;
        y=x1-(a/b)*y1;
    }
}

int main()
{
    long long a, b;
    cin>>a>>b;
    
    long long x, y;
    euclid_extins(a, b, x, y);
    
    while(x<0)
        x+=b;
    
    cout<<x;
    return 0;
}