# include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long x,y;
int n,k;
void inversModular(int a,int b,long long&x,long long&y){
    if (!b)
         x=1,y=0;
     else
     {
         inversModular(b,a%b,x, y);
         long long aux=x;
         x=y;
         y=aux-y*(a/b);
     }
}
int main () {
    f>>n>>k;
    inversModular(n,k,x,y);
    if (x<=0)
       x=k+x%k;
    g<<x<<"\n";
    return 0;
}