#include <bits/stdc++.h>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int64_t A,N,X,Y;
int64_t cmmdc(int64_t a,int64_t b,int64_t &u,int64_t &v)/// returneaza cmmdc(a,b) si prin int64_termediul parametrilor u si v valorile pt care au+bv=d
{
    if(b==0)
    {
        u=1;v=0;
        return a;
    }
    /// cmmdc(a,b) = cmmdc(b,a%b)
    int64_t U,V,D;
    D=cmmdc(b,a%b,U,V);
    u=V;
    v=U-(a/b)*V;
    return D;
}
int main()
{
    f>>A>>N;
    cmmdc(A,N,X,Y);
    X%=N;
    if(X<0)X+=N;
    g<<X;
    return 0;
}

//A*B=C
//
//A,B,C numere mari atunci nu vreau C ci C%M ( unde M este un numar dat )
//
//Cunosc A,B
//
//((A%M) * (B%M)) % M = C
//
//cunosc A, C vreau sa aflu B
//
//B=C/A
//
//Inversul modular al lui A  sau A^(-1) sau (1/A) modulo M
//
//X -> A*X %M = 1
//
//A*B=C | * X
//
//A*X*B = C*X
//1*B = C*X
//B=C*X !!!
//
//
//(5*5)%12 = 25%12 = 1
//
//5^(-1) = 5
//
//2*3 % 5 = 6%5 = 1
//
//1/2 = 3
//
//
//
//cmmdc(A,N) = 1
//
//(A*X+N*Y)%N=1%N
//(A*X)%N + (N*Y)%N = 1
//(A*X)%N + 0 = 1
//(A*X)%N = 1