#include <fstream>

using namespace std;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
int n,a,x0,x1,t,x,cat,rest,r;
int main()
{
    f>>a>>n;
    t=n;
    x0=1;
    x1=0;

    while(n!=0)
    {
        rest=a%n;
        cat=a/n;
        a=n;
        n=rest;
        x=x0-cat*x1;
        x0=x1;
        x1=x;
    }
    if(x0<0) x0+=t;
     g<<x0;
    return 0;
}