#include <fstream>

using namespace std;

#define ll long long

int A, N;

void GCD ( ll &x, ll &y, ll a, ll b ){

    if ( !b ){

        x = 1;
        y = 0;

        return;
    }

    GCD( x, y, b, a % b );

    ll aux = x;
    x = y;
    y = aux - y * (a / b);
}


int main(){

    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");

    f >> A >> N;

    ll inv = 0, ins;

    GCD( inv, ins, A, N );

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

    g << inv << "\n";

    return 0;
}