#include <iostream>
#include <fstream> 

using namespace std;

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

int gcdExtended(int a, int n, int &x, int &y)
{
	if(a == 0)
	{
		x = 0;
		y = 1;
		return n;
	}
	int x1, y1;
	int gcd = gcdExtended(n % a, a, x1, y1); 
	x = y1 - x1 * (n / a);
	y = x1;
	return gcd;
}

int modInv(int a, int n)
{
	int x, y;
	int gcd = gcdExtended(a, n, x, y);

	if(gcd != 1)
		return -1;
	else 
		return (1ll * x + n) % n;
}

int main()
{
	int  a, n;
	fin >> a >> n;

	fout << modInv(a, n) << '\n';
	return 0;
}