#include <stdio.h>

int extendedEuclidean(int a, int m, int* x, int* y) {
    int x1,y1,gcd;

    if (a == 0) {
        *x = 0;
        *y = 1;
        return m;
    }

    gcd = extendedEuclidean(m % a, a, &x1, &y1);
    *x = y1 - (m / a) * x1;
    *y = x1;

    return gcd;
}

int reverseModulo(int a, int m) {
    int x,y;
    int gcd = extendedEuclidean(a, m, &x, &y);
    if (x < 0) {
        x = (x % m + m) % m;
    }
    return x;
}

int main() {
    int a,m;

    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d %d",&a,&m);

    printf("%d",reverseModulo(a,m));

    return 0;
}