#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;

LL a, b, x, y;

LL exgcd(LL a, LL b, LL& x, LL& y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL gcd = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return gcd;
}

int main()
{
    scanf("%lld%lld", &a, &b);
    LL gcd = exgcd(a, b, x, y);
    x /= gcd;
    b /= gcd;
    printf("%lld", (x%b+b)%b);
    return 0;
}