#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int gcd(int a, int b, long long &x, long long &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long x0, y0;
	int d = gcd(b, a % b, x0, y0);
	x = y0;
	y = x0 - y0 * (a / b);
	return d;
}
int main() {
	int A, N;
	fin >> A >> N;
	long long x, y;
	int d = gcd(A, N, x, y);
//	if(d != 1) {
//		cout << "test gresit!";
//		return 0;
//	}
	fout << (x + N) % N << '\n';
	return 0;
}