#include <stdio.h>
#include <stdlib.h>

//Euclid extins
void inversModular(int a, int b, int *x, int *y){

    if (b == 0)
    {
        *x = 1;
        *y = 0;
    }
    else
    {
        inversModular(b, a % b, x, y);
        int aux = *x;
        *x = *y;
        *y = aux - *y * (a/b);
    }
}

int main()
{
    int a, b;
    int x, y;
    FILE* in = fopen("inversmodular.in", "r");
    FILE* out = fopen("inversmodular.out", "w");
    fscanf(in, "%d %d", &a, &b);
    inversModular(a, b, &x, &y);
    while (x < 0)
        x += b;
    fprintf(out,"%d", x);
    fclose(in);
    fclose(out);
    return 0;
}