#include <fstream>

using namespace std;

int A,N,x,y;

void valoare(int a,int b, int &x, int &y) {
    if(b==0) {
        x=1;
        y=0;
        return;
    }
    int xa,ya;
    valoare(b,a%b,xa,ya);
    x=ya;
    y=xa-(a/b)*ya;
}

int main() {
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    f>>A>>N;
    valoare(N,A,x,y);
    if(y<0)
        y=(y+N*((0-y)/N+1))%N;
    g<<y<<"\n";
    return 0;
}