using namespace std;
#include <fstream>
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int x, y;

int euler(int, int) ;

int main()
{
    int a, n, r;
    fin >> a >> n;
    r = euler(a, n);
    if(r != 1) fout << "-1\n";
    else
    {
        if(x >= 0) x = x % n;
        else
        {
            x = n + x % n;
            if(x == n) x = 0;
        }
        fout << x << '\n';
    }
    return 0;
}

int euler(int a, int b)
{
    if(b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    int aux, rez = euler(b, a % b);
    aux = x;
    x = y;
    y = aux - a / b * y;
    return rez;
}