#include <bits/stdc++.h>
#define lll long long
#define pii pair<int,int>
#define pll pair<lll,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define inf (1<<30)
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<' '<<(x)<<'\n',aaa

using namespace std;

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

void gcda ( int a, int b, pii &xy )
{
  if ( b == 0 ) { xy = {1, 0}; return; }
  gcda (b, a%b, xy);
  xy = {xy.se, xy.fi - (a/b)*xy.se};
}

int main ()
{
  int a, n; fin >> a >> n;
  pii xy;
  gcda (a, n, xy);
  if (xy.fi < 0) xy.fi += ((-xy.fi)/n+1)*n;
  fout << xy.fi % n;
  fin.close (); fout.close ();
  return 0;
}