/// SEE Algoritmul lui euclid extins
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long euclid(long long a, long long b, long long& x, long long& y) {

    if(b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long xa, ya;
    int d = euclid(b, a % b, xa, ya);

    x = ya;
    y = xa - (a / b) * ya;

    return d;
}

/// a * x + b * y = 1 (modulo M)
/// In cazul nostru b este M
/// deci ecuatia devine a * x + M * y = 1 (modulo M)
/// M * y (modulo mod) este 0
/// deci putem spune ca x este inversul modular lui a

int main() {

    long long a, b;
    f >> a >> b;

    long long x, y;
    euclid(a, b, x, y);

    g << (x + b) % b;

    return 0;
}