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

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

void gcd (int a, int b, int &d, int &x, int &y){
	if (b==0){
		d=a;
		x=1; y=0;
	}
	else {
		int x0, y0;
		gcd (b, a%b, d, x0, y0);
		x = y0;
		y = x0 - (a/b)*y0;
	}
}

int main(){
	int d, n, x, t1, t2;
	f>>d>>n;
	gcd (d, n, t1, x, t2);
	while (x<0) x+=n;
	x%=n;
	g<<x;
}