#include <fstream>

using namespace std;

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

int A, N, x, y;

void Modular_Reverse(int &x, int &y, int a, int b)
{
    if (b==0)
      x=1, y=0;
    else
    {
        Modular_Reverse(x, y, b, a % b);
        int aux=x;
        x=y;
        y=aux-y*(a / b);
    }
}

int main()
{
    fin >> A >> N;
    Modular_Reverse(x, y, A, N);
    if (x<0)
      x=N+(x % N);
    fout << x << '\n';
    fin.close();
    fout.close();
    return 0;
}