#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int egcd(int a, int b, int &x, int&y)
{
    if(b==0)
    {
     x=1;
     y=0;
     return a;
    }
    int d,X,Y;
   d=egcd(b,a%b,X,Y);
   x=Y; y=X-(a/b)*Y;
   return d;
}
int main()
{
    int a,b,d,x,y;
    fin>>a>>b;
    d=egcd(a,b,x,y);
    if(x<0)
    {
        x+=b;
    }
    fout<<x%b;
    return 0;

}