#include <fstream>
#define ll long long

using namespace std;

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

int a,n;

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

int main(void)
{
    ll inv=0,ins;
    cin>>a>>n;
    cmmdc(inv,ins,a,n);
    if(inv<=0)
        inv=n+inv%n;
    cout<<inv;
}