#include <bits/stdc++.h>

using namespace std;

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

void euclidExtins(int a, int &x, int b, int &y, int d)
{
    if (b == 0)
    {
        if (d % a)
        {
            x = 0;
            y = 0;
            return;
        }
        x = d / a;
        y = 0;
        return;
    }
    int x0, y0;
    euclidExtins(b, x0, a % b, y0, d);
    x = y0;
    y = x0 - a/b * y0;
}

int main()
{
    int A, N , X, Y, D = 1;

    fin >> A >> N;

    euclidExtins(A, X, N, Y, D);

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

    fout << X;
    return 0;
}