#include <fstream>
#define ll long long

using namespace std;

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

void gcd(int a,int b,ll &x,ll &y)
{
	if(!b) 
		x = 1 , y = 0;
	else
	{
		gcd(b,a%b,x,y);
		ll aux = x;
		x = y;
		y = aux - y*(a/b);
	}
}

int main()
{
	int N , A;
	fin>>A>>N;
	ll inv , ins;
	gcd(A,N,inv,ins);
	if(inv<=0)
		inv = N + inv%N;
	fout<<inv<<'\n';
	return 0;
}