#include <iostream>
#include <fstream>
using namespace std;

void cmmdc(int a, int n, int &x, int &y) {
    if(!n)
        x=1,y=0;
    else {
        int x0,y0;
        cmmdc(n,a%n,x0,y0);
        x=y0;
        y=x0-y0*(a/n);
    }
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int a,n,x,y;
    fin>>a>>n;
    cmmdc(a,n,x,y);
    if(x<=0)
        x=n+x%n;
    fout<<x<<'\n';
    return 0;
}