#include <stdio.h>

int gcd (int a, int b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x0, y0;
    int d;
    d = gcd(b, a % b, x0, y0);
    x = y0;
    y = x0 - y0 * (a / b);
    return d;
}

int main () {
    int a, b;
    long long x, y;

    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%d%d", &a, &b);

    gcd(a, b, x, y);

    if (x <= 0)
        x += b;

    printf("%lld\n", x);
}