#include <bits/stdc++.h>

using namespace std;

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

void solve(int,int);
void euclidextins(int,int,int&,int&);

int n;
int a,b,c;

int main()
{
  fin>>a>>b;
  solve(a,b);
 return 0;
}

void euclidextins(int a1,int b1,int& d1,int& x1,int& y1)
{
 int yaux,xaux;
 if (b1==0)
 {
  x1=1;
  y1=0;
  d1=a1;
 }
 else
 {
  euclidextins(b1,a1%b1,d1,x1,y1);
  yaux=y1;
  xaux=x1;
  x1=yaux;
  y1=xaux-(a1/b1)*yaux;
 }
}

void solve(int a1,int b1)
{
 int d1,x1,y1;
 euclidextins(a1,b1,d1,x1,y1);
 while (x1<0)
  x1+=b1;
 fout<<x1;
}