#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int n, k, x, y;

void euclid(int a, int b, int &x, int &y)
{
  if(!b)
    {
      x = 1, y = 0;
      return;
    }

  int x0, y0;
  euclid(b, a % b, x0, y0);

  x = y0;
  y = x0 - (a / b) * y0;
}

void read()
{
  f>>n>>k;
  f.close();

  euclid(n, k, x, y);
  while(x <= 0)
    x = k + x % k;
  g<<x;

  g.close();
}

int main()
{
  read();
  return 0;
}