#include <stdio.h>

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

    int x1, y1;
    int d = euclid_extins(b, a % b, &x1, &y1);

    *x = y1;
    *y = x1 - (a / b) * y1;

    return d;
}

int invers_modular(int a, int n) {
    int x, y;
    int d = euclid_extins(a, n, &x, &y);
    if (d != 1) {
        return -1;
    } else {
        return (x % n + n) % n;
    }
}

int main() {
    int A, N;
    FILE *fin,*fout;
    fin = fopen("inversmodular.in","r");
    fout = fopen("inversmodular.out","w");
    fscanf(fin,"%d", &A);
    fscanf(fin,"%d", &N);

    if (A <= 0 || N <= A) {
        return 1;
    }

    int invers = invers_modular(A, N);
    if (invers == -1) {
        fprintf(fout,"%d %d", A, N);
    } else {
       fprintf(fout,"%d", invers);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}