#include <cstdio>
#define infile "inversmodular.in"
#define outfile "inversmodular.out"

int A, N, X, Y;

void Euclid(int A, int B, int &X, int &Y)
{
    int X0,Y0;

    if(!B)
    {
        X = 1;
        Y = 0;
        return;
    }

    Euclid(B, A % B, X0, Y0);
    Y = X0 - ( A / B ) * Y0;
    X = Y0;
}

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

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

    Euclid(A, N, X, Y);
    for(; X<0; X += N) ;

    printf("%d\n", X);

    fclose(stdin);
    fclose(stdout);
    return 0;
}