#include <iostream>
#include <fstream>

using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

void invModular(long long &inv, long long &ins, int a, int b)
{
    if(!b)
        inv = 1, ins = 0;
    else {
        invModular(inv, ins, b, a % b);
        int aux = inv;
        inv = ins;
        ins = aux - ins * (a / b);
    }
}

int a, n;

int main()
{
    f>>a>>n;
    long long ins = 0, inv = 0;

    invModular(ins, inv, a, n);

    if(inv < 0)
        inv = n + inv % n;


    g<<inv;
}