#include <iostream>
#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

typedef long long ll;

void euclid_extins(ll a,ll b,ll &x,ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return;
    }
    euclid_extins(b, a % b, x, y);
    ll xnou = y;
    ll ynou = x - y * (a / b);
    x = xnou,y = ynou;
}

int main()
{
    ll n,a;
    in>>a>>n;
    if(__gcd(a,n) == 1){
        ll x,y;
        euclid_extins(a,n,x,y);

        x = (x % n + n) % n;
        out<<x;
    }else
        out<<-1;
    return 0;
}