#include<fstream>
using namespace std;
int a, n, x, y;
void euclid(int a, int n, int &x, int &y)
{
    if(n==0)
    {
        x=1;
        y=0;
        return;
    }
    int xn=0, yn=0;
    euclid(n, a%n, xn, yn);
    x=yn;
    y=xn-yn*(a/n);
}
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int main()
{
    in>>a>>n;
    euclid(a, n, x, y);
    if(x<0)
        x=n+x%n;
    out<<x;
    return 0;
}