#include <fstream>
#include <cstdlib>

using namespace std;
inline void gcd( int a, int b, int& x, int& y, int&d )
{
	if( 0 == b )
	{
		d=a;
		x=1;
		y=0;
		return;
	}
	int x0, y0;
	gcd( b, a%b, x0, y0, d );
	x=y0;
	y=x0-(a/b)*y0;
}
int main( void )
{
	int A, N, x, y, d;
	ifstream in( "inversmodular.in" );
	in>>A>>N;
	gcd( A, N, x, y, d );
	ofstream out( "inversmodular.out" );
	out<<( x >= 0 ? x : x+N )<<'\n';
	return EXIT_SUCCESS;
}