#include <bits/stdc++.h>
using namespace std;
 
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

void gcd(long long a, long long b, long long &x, long long &y) {
	if(b == 0) {
		x = 1;
		y = 0;
	} else {
		gcd(b, a % b, x, y);
		long long aux = x;
		x = y;
		y = aux - y * (a / b);
	}
}

int main() {

	long long a, n; in >> a >> n;

	long long inv = 0, temp;

	gcd(a, n, inv, temp);

	if(inv <= 0)
		inv = n + (inv % n);

	out << inv << '\n';

    in.close(); out.close();
 
    return 0;
}