#include <iostream>
#include <fstream>
#include <cstdlib>
// #define mod 666013
using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
unsigned long long i, j;

unsigned long long fast_pow(unsigned long long base, unsigned long long power)
{
    unsigned long long result = 1;
    // base %= MOD;

    while (power > 0)
    {
        if (power % 2 == 1)
        {
            result = (result * base);
        }
        base = (base * base);
        power = power / 2;
    }

    return result;
}

void euclid_extins(long long a, long long M)
{
    long long y0 = 0, y1 = 1, y, r, c;
    long long aux = M;
    while (a != 0)
    {
        r = M % a;
        c = M / a;
        M = a;
        a = r;
        y = y0 - c * y1;
        y0 = y1;
        y1 = y;
    }
    while (y0 < 0)
    {
        y0 += aux;
    }
    fout << y0;
}

int phi(long long n)
{
    long long result = n;
    for (i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0)
            {
                n /= i;
            }
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

int main()
{
    long long A, N, pow, x;
    fin >> A >> N;
    euclid_extins(A, N);

    return 0;
}