#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int64_t cmmdc(int64_t a,int64_t b,int64_t &u,int64_t &v)
{
    if(b==0){u=1;v=0;return a;}
    int64_t U,V,d;
    d=cmmdc(b,a%b,U,V);
    u=V;
    v=U-(a/b)*V;
    return d;
}

int main()
{
    int64_t a,n,x,y,d;
    f>>a>>n;
    d=cmmdc(a,n,x,y);
    x%=n;
    if(x<0)x+=n;
    g<<x;

    return 0;
}