#include <fstream>
using namespace std;

#define LL long long

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

int A, N;

void Solve(LL &x, LL &y, int a, int n);

int main()
{
    LL x = 0, y;

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    fin >> A >> N;
    Solve(x, y, A, N);

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

    fout << x;
    fin.close();
    fout.close();
    return 0;
}
void Solve(LL &x, LL &y, int a, int n)
{
     if (!n)
         x = 1, y = 0;
     else
     {
         Solve(x, y, n, a % n);
         LL aux = x;
         x = y;
         y = aux - y * (a / n);
     }
}