#include <iostream>

using namespace std;

int d;
int cmmdc(int a,int b,int &x, int &y)
{
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }

    int x0, y0;
    d = cmmdc(b, a % b, x0, y0);

    x = y0;
    y = x0 - (a / b) * y0;
    return d;
}

int main() {

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

    int a,n,inv,ins;
    cin >> a >> n;

    cmmdc(a,n,inv,ins);

    if(inv <= 0){
        inv = n + inv % n;
    }
    cout << inv;
    return 0;
}