#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
#define pr pair<int,int>
long long n,x,a;
pr ee(int a, int b){
if(b==0){
    return{1,0};
}
else{
    pr r=ee(b,a%b);
    return{r.second,r.first-(a/b)*r.second};
}
}

int im(int n, int x){
    int r=ee(x,n).first;
    if(r<0){
        r=n+r%n;
    }
    return r;
}
int main()
{
    fin>>a>>n;

    fout<<im(n,a);
    return 0;
}