#include <bits/stdc++.h>

using namespace std;

int euclid_ext(int a, int b, int &x, int &y)
{
	if(!b)
	{
		x = 1;
		y = 0;
		return a;
	}
	int x1, y1, g;
	g = euclid_ext(b, a%b, x1, y1);
	x = y1;
	y = x1 - y1 * (a/b);
	return g;
}
ifstream fi("inversmodular.in");
ofstream fo("inversmodular.out");
int n, a;
int main() {
	fi >> a >> n;
	int x, y;
	euclid_ext(a, n, x, y);
	fo << x;
    return 0;
}