#include <stdio.h>

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

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

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

    return d;
}

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

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

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

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