#include <iostream>
#include <fstream>
using namespace std;

struct vec {long long x, y, u;};

vec mod(vec v1, vec v2)
{
    long long c = v1.u / v2.u;
    vec v3;

    v3.x = v1.x - c*v2.x;
    v3.y = v1.y - c*v2.y;
    v3.u = v1.u % v2.u;

    return v3;
}

vec divizor(vec v1, vec v2)
{
    vec v3;

    v1.x = v2.y = 1;
    v1.y = v2.x = 0;

    while(v2.u > 1)
    {
        v3 = mod(v1,v2);
        v1 = v2;
        v2 = v3;
    }

    return v2;
}

long long inv_mod(long long k, long long n)
{
    vec v1 = {1,0,k}, v2 = {0,1,n}, v3;
    v3 = divizor(v1, v2);
    return v3.x;
}

int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    long long k, n, inv;

    fin >> k >> n;
    inv = inv_mod(k, n);
    if(inv <= 0)
        inv = n + inv % n;
    fout << inv;

    return 0;
}