#include <iostream>
#include <fstream>
#include <algorithm>

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

using namespace std;

int a,b,k,l,d;

void cmmdc(int a, int b,int &d, int &k, int &l)
{
    if (b==0)
    {
        k=1;
        return;
    }
    int kp, lp;
    cmmdc (b,a%b, d, kp, lp);
    k=lp;
    l=kp-lp*(a/b);
}

int main()
{
    f >> a >> b;
    cmmdc(a,b,d,k,l);
    if (k>=0)
        g << k;
    else
    {
        while (k<0)
            k+=b;
        g << k;
    }
    return 0;
}