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