#include <bits/stdc++.h>
#define LL long long

using namespace std;

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

LL a, n, x;

LL gcdExtended(LL a, LL b, LL *x, LL *y)
{
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    } 
    LL x1, y1; 
    LL gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}
  
LL modInverse(LL a, LL m)
{
    LL x, y;
    LL g = gcdExtended(a, m, &x, &y);
    if (g != 1)
        cout << "Inverse doesn't exist";
    else
    {
       
        LL res = (x%m + m) % m;
        return res;
    }
}

int main(){
	in >> a >> n;
	out << modInverse(a, n);
	return 0;
}