#include <fstream>

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

void euclid(long long a, long long b, long long&d, long long&x, long long&y);

long long n, a, b, d, i, x, y, c;

int main()
{
  fin>>a>>b;
  euclid(a, b, d, x, y);
  if(x<0) x=((-x+n)/n)*n;
  fout<<x;
  return 0;
}

void euclid(long long a, long long b, long long&d, long long&x, long long&y)
{
  if(b==0) d=a, x=1, y=0;
  else
  {
    long long x0, y0;
    euclid(b, a%b, d, x0, y0);
    x=y0;
    y=x0-(a/b)*y0;
  }
}