#include <bits/stdc++.h>

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

// Algorimtul lui Euclid extins
// Conditie: Sa fie a & b prime intre ele
// Cum verificam asta: utilizand functia phi()
void gcd(int& x, int a, int& y, int b){
    if(b == 0){
        x = 1, y = 1;
    }
    else{
        int x1,y1;
        gcd(x1, b, y1, a%b);
        x = y1;
        y = x1 - a / b * y1;
    }
}
// Se putea face si cu mica teorema a lui fermat insa
// C.E. era ca A sau B sa fie prim
// Pentru calcularea A^-1 = A^B-2 utilizam exponentierea
// Binara

int main()
{
    int a,b;
    int x,y;
    fin>>a>>b;
    gcd(x,a,y,b);
    int ans = 0;
    while(x < 0)
        x+=b;
    fout<<x;
    return 0;
}