#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
ifstream fin("mod.in");
ofstream fout("mod.out");
long long gcd(long long a,long long b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	long long ans=gcd(b,a%b,x,y);
	long long temp;
	temp=x,x=y,y=temp-a/b*y;
	return ans;
}
long long highgcd(long long a,long long m)
{
	long long x,y;
	long long gcdd=gcd(a,m,x,y);
	if(1%gcdd!=0)
		return -1;
	x*=1/gcdd;
	m=abs(int(m));
	long long ans=x%m;
	if(ans<=0)
		ans+=m;
	return ans;
}
int main()
{
	long long a,b,ans;
	fin>>a>>b;
	ans=highgcd(a,b);
	fout<<ans<<endl;
	return 0;
}//trl signed