#include <fstream>
using namespace std;

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

int a,n;

void cmmdc(int &x, int &y, int a, int b)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    int x0,y0;
    cmmdc(x0,y0,b,a%b);
    x=y0;
    y=x0-y0*(a/b);

}
int main()
{
    int inv,y;
    in>>a>>n;
    cmmdc(inv,y,a,n);

    if(inv<=0)
        inv=n+inv%n;

    out<<inv<<'\n';
    return 0;
}