#include <bits/stdc++.h>
using namespace std;

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

int a, n;
int cmmdc_ext(int, int, int&, int&);
int invers_modular(int, int);

int main() {
	f >> a >> n;
	g << invers_modular(a, n);

	return 0;
}

int cmmdc_ext(int a, int b, int& x, int& y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	int d, x1, y1;
	d = cmmdc_ext(b, a % b, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
	return d;
}

int invers_modular(int a, int n) {
	if (__gcd(a, n) > 1) return 0;
	int x, y, d;
	d = cmmdc_ext(a, n, x, y);
	x %= n;
	if (x < 0) x += n;
	return x;
}