#include <stdio.h>

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

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

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

    return cmmdc;
}

int main()
{
    FILE *fin = fopen("inversmodular.in", "r");
    FILE *fout = fopen("inversmodular.out", "w");

    if (fin == NULL || fout == NULL) {
        return 0;
    }

    long a, n;
    if (fscanf(fin, "%ld %ld", &a, &n) != 2) {
        fclose(fin);
        fclose(fout);
        return 0;
    }

    long x, y;
    euclid_extins(a, n, &x, &y);

    x = (x % n + n) % n;

    fprintf(fout, "%ld\n", x);

    fclose(fin);
    fclose(fout);

    return 0;
}