#include <fstream>

using namespace std;

void euclid(int A, int B, int& x, int& y){
    if(B == 0){
        x = 1;
        y = 0;
    }
    else{
        int _x, _y;
        euclid(B, A % B, _x, _y);
        x = _y;
        y = _x - (A / B) * _y;
    }

}

int main()
{
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
         
    int A, N, x, y;
    cin >> A >> N;

    euclid(A, N, x, y);
    if(x < 0)
        x = x + ((x / N) + 1) * N;

    cout << x;
    

    cin.close();
    cout.close();

    return 0;
}