#include <fstream>
using namespace std;
void cmmdc( int a, int b, int &x, int &y ){
	int x0, y0;
	if( b == 0 ){
		x = 1;
		y = 0;
	}
	else{
		cmmdc( b, a % b, x0, y0 );
		x = y0;
		y = x0 - a / b * y0;
	}
}
int main(){
	int a, n, x, y;
	ifstream fin( "inversmodular.in" );
	ofstream fout( "inversmodular.out" );
	fin >> a >> n;
	cmmdc( a, n, x, y );
	if( x < 0 ){
		x += ( - ( x / n ) + 1 ) * n;
	}
	fout << x;
	return 0;
}