#include <stdio.h>

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

    int xp, yp;
    Euclid(b, a % b, &xp, &yp);

    *x = yp;
    *y = xp - (a / b) * yp;
}

int InversModular(int a, int b)
{
    int x, y;
    Euclid(a, b, &x, &y);
    while (x < 0)
        x += b;
    return x;
}

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

    int a, b;
    fscanf(fin, "%d%d", &a, &b);

    fprintf(fout, "%d\n", InversModular(a, b));
    return 0;
}