#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int a,b;
long long inv=0,xas,aux;
void euclid(long long &inv,long long &xas,int a,int b)
{
    if(b==0)
    {
        inv=1;
        xas=0;
        return;
    }
    euclid(inv,xas,b,a%b);
    aux=inv;
    inv=xas;
    xas=aux-xas*(a/b);


}
int main()
{
    in>>a>>b;
    euclid(inv,xas,a,b);
    while(inv<0)
        inv+=b;
    out<<inv<<'\n';

    in.close();
    out.close();
    return 0;
}