#include <bits/stdc++.h>

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

void euclid(int A, int B, int &X, int &Y)
{
    if (B == 0)
    {
        X = 1;
        Y = 0;
        return;
    }
    int prevX, prevY;
    euclid(B, A % B, prevX, prevY);
    X = prevY;
    Y = prevX - (A / B) * prevY;
}

int main()
{
    int N, A, X, Y;
    fin >> A >> N;
    euclid(A, N, X, Y);
    if (X < 0)
        X = N + X % N;
    fout << X << "\n";
    return 0;
}