#include <iostream>
#include <fstream>

using namespace std;

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

int main()
{

long long int y0 = 0, y1 = 1, A, N, aux, r, c, y ;
//A*y0=1(mod N); y0 exista pt ca A,N prime intre ele
//A*y0 = 1+ k*N => A*y0 + (-k)N = 1 (rezolvam ec)
fin>>A>>N;
aux = N;
while (A != 0)
{
r = N % A; //rest
c = N / A; //cat
N = A; //noul demapartit
A = r; //noul impartitor; la rest 0 am rezolvat ec
y = y0 - c * y1; //aproximam rezolvarea
y0 = y1;//siftam val y
y1 = y;
}

while (y0 < 0)
{
y0 += aux;
//pozitivam numarul, va ramane tot 1 mod N daca adunam repetat N
}
fout << y0;
    return 0;
}