#include <bits/stdc++.h>

using namespace std;

void generatorSolution( long long a, long long b, long long &x, long long &y, long long &d)
{
    if( b == 0)
    {
        x = 1;
        y = 0;
        d = a;
        return;
    } else{
        generatorSolution(b ,a % b, x, y, d);
        long long valueX = y;
        long long valueY = x - y * ( a / b);
        x = valueX;
        y = valueY;
    }
}

int main() {
    ifstream f("inversmodular.in");
    ofstream g("inversmodular.out");
    long long a, n, d, y, x;
    f >> a >> n;
    generatorSolution(a ,n, x, y, d);
    if ( x <= 0)
    {
        x = n + x % n;
    }
    g << x;
    return 0;
}