#include <fstream>

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

void euclid_extins(long long a, long long b,long long &d, long long&x, long long &y)
{
    if(b==0)
        {
            d=a;x=1;y=0;
        }
    else
    {
        long long d1,x1,y1;
        euclid_extins(b,a%b,d1,x1,y1);
        d=d1;x=y1;y=x1-(a/b)*y1;
    }

}

int main()
{
    long long a,n,d,x,y;
    fin>>a>>n;
    euclid_extins(a,n,d,x,y);
    if(x<0) x=n-x;
    fout<<x;
    return 0;
}