#include <fstream>
using namespace std;
#define ll long long
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int a, b;

void Euclid_Extins(ll &x, ll &y, int a, int b)
{
     if (!b)
         x = 1, y = 0;
     else
     {
         Euclid_Extins(x, y, b, a % b);
         ll aux = x;
         x = y;
         y = aux - y * (a / b);
     }
}

int main(){

    ll x = 0, y;

    Euclid_Extins(x,y,a,b);

    if(x <= 0 )
        x = b + x%b;

    out << x;

    return 0;
}