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

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

int a,n;

void euclid(int a,int b,int &x,int &y) {
	
	if(b==0) {
		x=1;
		y=0;
		return;
	}
	int xx,yy;
	euclid(b,a%b,xx,yy);
	
	x=yy;
	y=xx-a/b*yy;
	
}

int main() {
	
	int x,y;
	
	in >> a >> n;
	
	euclid(a,n,x,y);
	
	if(x<0)
		x=n+x%n;
	else
		x%=n;
	
	out << x << "\n";
	
	return 0;
}