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

void eucl(long a, long b, long& x, long& y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        long kov_a = b, kov_b = a % b , kov_x, kov_y;
        eucl(kov_a, kov_b, kov_x, kov_y);
        x = kov_y;
        y = kov_x - (a/b) * kov_y;
    }
}

int main()
{
    ifstream f("inversmodular.in");
    long a, n, x, y;
    f>>a>>n;
    eucl(a, n, x, y);
    //cout<<x;
    while (x<0)
        x+=n;
    ofstream g("inversmodular.out");
    g<<x;
}