# include <algorithm>
using namespace std ;

int A, N;

void verf ( int &a, int b ) {
    if ( a < 0 ) {
        a += b;
    }
}

void euclid ( int A, int B, int &X, int &Y ) {
    if ( !B ) {
        X = 1, Y = 0;
    } else {
        euclid ( B, A % B, X, Y ) ;
        swap ( X, Y ), Y -= X * ( A / B ) ;
    }
}

int main() {
    int inv = 0, ins;

    freopen ( "inversmodular.in", "r", stdin ) ;
    freopen ( "inversmodular.out", "w", stdout ) ;

    scanf ( "%d %d", &A, &N ) ;

    euclid ( A, N, inv, ins ) ;

    verf ( inv, N ) ;

    printf ( "%d", inv ) ;

    return 0;
}