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

using namespace std;

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

LL a, n, x;

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

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