#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>

#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

#include <algorithm>
#include <functional>
#include <utility>

#include <cstring>
#include <ctime>
#include <cstdlib>

#define LL long long
#define pb push_back
#define mp make_pair

using namespace std;

void euclid(int a, int b, int &x, int &y, int &d) {
	if (b == 0) {
		x = 1;
		y = 0;
		d = a;
		return;
	}
	int x0, y0;
	euclid(b, a % b, x0, y0, d);

	x = y0;
	y = x0 - y0 * (a / b);
}

int inv(int a, int n) {
	int x, y, d;
	euclid(a, n, x, y, d);

	return (x >= 0 ? x : (x + (-(x / n) + (x % n != 0)) * n));
}
int main() {
	ifstream cin("inversmodular.in");
	ofstream cout("inversmodular.out");

	int a, n;
	cin >> a >> n;

	cout << inv(a, n) << '\n';

	return 0;
}