#include<stdio.h>

void calculateModularInverse(int a, int b);

int main()
{
    int a, b;
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d%d", &a, &b);
    calculateModularInverse(a, b);
    return 0;
}

void calculateModularInverse(int a, int b)
{
    int x0 = 1, x1 = 0, y0 = 0, y1 = 1;
    int q, r, x, y;

    while (b != 0)
    {
        q = a / b;
        r = a % b;
        x = x0 - q * x1;
        y = y0 - q * y1;
        a = b;
        b = r;
        x0 = x1;
        x1 = x;
        y0 = y1;
        y1 = y;
    }

    while (x0 < 0)
        x0 += b;
    
    while (x0 >= b)
        x0 -= b;

    printf("%d\n", x0);
}