#include <bits/stdc++.h>

using namespace std;

void euclid(long long a, long long b, long long &x, long long &y) {
    if(!b) {
        x = 1;
        y = 0;
        return;
    }
    long long x0, y0;
    euclid(b, a%b, x0, y0); /// b * x0 + (a - [a/b]*b) * y0 = d
                            ///
    x = y0;
    y = x0 - (a/b) * y0;
}

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

    long long a,b,x,y;
    scanf("%lld%lld", &a, &b);
    euclid(a,b,x,y);
    x %= b;
    if(x < 0)
        x += b;
    printf("%lld\n", x);

    return 0;
}