#include <bits/stdc++.h>
#define n_max 100001

using namespace std;
ifstream f("inversmodular.in");
ofstream g("invermodular.out");
int n, m;

void gcd(int a, int b, int &x, int &y)
{
  if(!b)
   {
     x = 1, y = 0;
     return;
   } 
  int x0, y0;
  gcd(b, a % b, x0, y0);

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

void read()
{
  f>>n>>m;
  int x, y;
  gcd(n, m, x, y);
  while(x <= 0)
    x = m + x % m;
  g<<x;
}

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