#include <cstdio>

using namespace std;

int gcd( int a, int b, int &x, int &y )
{
  if( b==0 )
  {
    x=1;
    y=0;

    return a;
  }

  int d, x0, y0;

  d=gcd(b,a%b,x0,y0);

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

  return d;
}

int main()
{
  freopen( "inversmodular.in", "r", stdin );
  freopen( "inversmodular.out", "w", stdout );

  int a, b; // a*x + b*y =1

  scanf( "%d%d", &a, &b );

  int d, x, y;

  d=gcd(a,b,x,y);

  while( x<0 )
    x+=b;

  printf( "%d", x );

  return 0;
}