#include<fstream>
#include<iostream>
using namespace std;


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

// Sets x1 and x2 such that:
// a * x1 + b * x2 = 1.
void euclid(int a, int b, int&x1, int &x2) {
	int r = a%b;
	int c = a/b;

	if (r == 1) { 
		// We know that a = b * c + 1;
		x1 = 1;
		x2 = -c;
	} else {
		int x1t, x2t;	

		// Following euclid's algorithm, we know that we'll find
		// x1t, x2t such that b*x1t + r*x2t = 1.
		euclid(b, r, x1t, x2t);

		// Here we know that a = b * c + r
		// Therefore, b*x1t + (a-b*c) *x2t = 1

		x1 = x2t;
		x2 = x1t - c*x2t;
	}
}

int main() {
	int a, n;
	in>>a>>n;
	
	int x1, x2;
	euclid(n, a, x1, x2);

	// Here we know that n * x1 + a * x2 = 1;
	// So a * x2 = 1 mod n 
	if (x2 < 0) {
		x2 = n + (x2%n); 
	}
	out<<x2;
}