#include <stdio.h>

int euclid_gcd(int a, int b)
{
    if (!b)
    {
        return a;
    }
    return euclid_gcd(b, a % b);
}

void euclid_extins(int a, int b, int *x, int *y)
{
    int r0 = a, r1 = b, x0 = 1, x1 = 0, y0 = 0, y1 = 1;

    while (r1)
    {
        int q = r0 / r1, aux;
        aux = r1;
        r1 = r0 - q * r1;
        r0 = aux;

        aux = x1;
        x1 = x0 - q * x1;
        x0 = aux;

        aux = y1;
        y1 = y0 - q * y1;
        y0 = aux;
    }
    *x = x0;
    *y = y0;
}

int main()
{
    FILE *fin = fopen("inversmodular.in", "rb");
    FILE *fout = fopen("inversmodular.out", "wb");
    int a, b, x, y;

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

    euclid_extins(a, b, &x, &y);

    while (x < 0)
    {
        x += b;
    }
    fprintf(fout, "%d\n", x);
    fclose(fin);
    fclose(fout);
    return 0;
}