#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
  int n;
  int a, b;

  fin >> a >> b;

  int x, y;
  euclid(a, b, x, y);

  if (x < 0)
    x += b;

  fout << x << "\n";
}