# include <fstream>

using namespace std;

void euclid( long long a, long long b, long long& x, long long& y ) {
    if ( b == 0 ) {
        x = 1;
        y = 0;
    } else {
        long long x0, y0;
        euclid( b, a % b, x0, y0 );

        x = y0;
        y = x0 - a / b * y0;
    }
}

int main() {
    long long a, n;
    ifstream( "inversmodular.in" ) >> a >> n;

    long long x, y;
    euclid( a, n, x, y );
    ofstream( "inversmodular.out" ) << ( x >= 0 ? x % n : n + x % n );

    return 0;
}