#include <fstream>

using namespace std;

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

void euclid_ext( int a, int b, long long &x, long long &y ) {
  long long x0, y0;
  if ( b == 0 ) {
	x = 1, y = 0;
	return;
  }
  euclid_ext( b, a % b, x0, y0 );
  x = y0;
  y = x0 - y0 * (a / b);
}

int main() {
  int a, n;
  long long x, y;
  
  fin >> a >> n;
  euclid_ext( a, n, x, y );
  x = (x % n + n) % n;
  fout << x;
  fin.close();
  fout.close();
  return 0;
}