//		http://infoarena.ro/problema/inversmodular
#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int x,y,m,p;

void euclid (int a,int b)
{
    if (b==0)
	{
        m=a;
        x=1;
        y=0;
    }
    else
	{
        euclid (b,a%b);
        p=x;
        x=-y;
        y=a/b*x-p;
    }
}

int main ()
{
	int n,a;
    f>>a>>n;
    euclid (a,n);
    while (x<0) x+=n;
    g<<x<<"\n";
}