#include <iostream>
#include <fstream>

using namespace std;

pair<int, int> extended_euclid(int a, int b){
	pair<int, int> result;

	if (a == 1){
		result.first  = 1;
		result.second = 0;
	} else if (b == 1) {
		result.first  = 0;
		result.second = -1;
	} else {
		int d = a / b, c = a % b;
		pair<int, int> p = extended_euclid(b, c);
		result.first = - p.second;
		result.second = - (p.second * d + p.first);
	}
	return result;
}

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

int main() {
	int A, N;
	f >> A >> N;
	int result = extended_euclid(A, N).first;

	if (result < 0)
		result+=N;
	g << result << '\n';

	f.close();
	g.close();
	return 0;
}