#include <stdio.h>

int a, n;

void euclid(int a, int b, int* x, int* y){
    if(b == 0){
        *x = 1;
        *y = 0;
        return;
    }

    int x0, y0;
    euclid(b, a % b, &x0, &y0);
    *x = y0;
    *y = x0 - (a / b) * y0;
}

int invmod(int a, int n){
    int x, y;
    euclid(a, n, &x, &y);
    return x;
}

int main(){
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d%d", &a, &n);
    printf("%d\n", invmod(a, n));
    return 0;
}