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

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

int main ()
{
	int a,n;
	long long x,y;
	ifstream f("inversmodular.in");
	ofstream g("inversmodular.out");
	f>>a>>n;
	f.close();
	gcd(a,n,x,y);
	while(x<=0) 
		x=0LL+x+x%n;
	g<<x;
	g.close();
	return 0;
}