#include <bits/stdc++.h>

using namespace std;

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

void euclid(int a,int b,int &x, int &y)
{
	if(b==0)
    {
		x=1;
	    y=0;
	}
	else
	{
		euclid(b,a%b,x,y);
		int nr;
		nr=x;
		x=y;
		y=nr-y*(a/b);
	}
}
int main()
{
	int a,b,x,y;
    f>>a>>b;

	euclid(a,b,x,y);
    if(x<=0)
    {
		x=b+x%b;
    }
	g<<x;
}