#include <fstream>

using namespace std;

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

long long x,y;

void euclid( long long a, long long b, long long &x,long long &y,long long &d)
{
    if(b==0) {x=1;y=0;d=a;}
    else
    {
        long long x0,y0;
        euclid(b,a%b,x0,y0,d);
        x=y0;
        y=x0-a/b*y0;
    }
}

long long a,b,c,d,i,n,k;
int main()
{
    fin>>a>>n;
    euclid(n,a,x,y,d);
    while(y<1)y+=n;
    fout<<y;

    return 0;
}