#include <fstream>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");
long long X,Y;
int A,N;
void euclid(long long &x,long long &y,int a,int n)
{
     if(!n)
     {
         x=1;
         y=0;
     }
     else
     {
         euclid(x,y,n,a%n);
         long long aux=x;
         x=y;
         y=aux-y*(a/n);
     }
}

int main()
{
    fin>>A>>N;
    euclid(X,Y, A, N);
    while(X<=0)
       X=X%N+N;

    fout<<X;
    return 0;
}