#include <fstream>

using namespace std;
long long a,n,x,y;

long long cmmdc (long long a, long long b, long long &x, long long &y) {
    if (b==0) {
        ///a*x+0*y=a
        ///x=1
        ///y=orice
        x=1;
        y=0;
        return a;
    }
    else {
        long long d=cmmdc(b,a%b,x,y);
        long long xa=x;
        long long ya=y;
        long long c=a/b;
        ///b*xa+a&b*ya=d
        ///b*xa+(a-b*c)*ya=d;
        ///a*x+b*y=d
        ///b*xa+(a-b*c)*ya=a*x+b*y
        ///b*xa+a*ya-b*c*ya=a*x+b*y
        ///b(xa-c*ya-y)=a(x-ya)
        ///o solutie este sa egalam parantezele cu 0
        ///x-ya=0
        ///x=ya

        ///xa-c*ya-y=0
        ///y=xa-c*ya
        x=ya;
        y=xa-c*ya;
        return d;
    }
}

int main() {
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    fin>>a>>n;
    long long d=cmmdc(a,n,x,y);
    ///a*x+n*y=1
    ///(n*y)%n=0, deci in calcul cu module reuzlta
    ///a*x=1
    ///Deci x=inversul modular al lui a
    if (x<=0) fout<<(n+x%n)%n;
    else fout<<x;
    return 0;
}