#include <bits/stdc++.h>


using namespace std;
const string TASK("inversmodular");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

void euclid(int& x, int& y, int a, int b)
{
    if(!b)x = 1, y = 0;
    else
    {
        int x1, y1;
        euclid(x1, y1, b, a % b);
        x = y1;
        y = x1 - y1 * (a / b);
    }
}

int main()
{
    int A, N;
    cin >> A >> N;

    int x, y;
    euclid(x, y, A, N);

    if(x < 0)x = x % N + N;

    cout << x << '\n';
    return 0;
}