#include <bits/stdc++.h>

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

void usain_bolt()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
}

void ext_euclid(long long a, long long b, long long &x0, long long &y0)
{
    if(b == 0) {
        x0 = 1;
        y0 = 0;
        return ;
    }
    long long x1, y1;
    ext_euclid(b, a % b, x1, y1);
    x0 = y1;
    y0 = x1 - a / b * y1;
    return ;
}

int main()
{
    usain_bolt();

    int a, b;

    fin >> a >> b;
    long long x0, y0;
    ext_euclid(a, b, x0, y0);
    x0 = (x0 + b) % b;
    fout << x0 << "\n";
    return 0;
}