#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int N,A;

int cmmdc(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int x1,y1,d=cmmdc(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return d;
}

int main(void){
    register int i,j,x,y;

    f>>A>>N;
    cmmdc(A,N,x,y);
    if(x<0)
        x+=(1-x/N)*N;
    g<<x%N;
    f.close();
    g.close();
    return 0;
}