#include <fstream>

using namespace std;

ifstream cin;
ofstream cout;

inline void euclid3(int a, int b, int & x, int & y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }

    int x0, y0;
    euclid3(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
}

int main()
{
    cin.open("inversmodular.in");
    cout.open("inversmodular.out");

    int A, N, x, y;
    cin >> A >> N;

    euclid3(A, N, x, y);
    if(x < 0) x += N;

    cout << x << '\n';

    cin.close();
    cout.close();

    return 0;
}