#include <stdio.h>

#define InFile "inversmodular.in"
#define OutFile "inversmodular.out"

using namespace std;

FILE *fin, *fout;

inline void inv_mod(int a, int b, long long& x, long long& y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
    }
    else
    {
        long long x0, y0;
        inv_mod(b, a % b, x0, y0);
        x = y0;
        y = x0 + (a / b) * y0;
    }
}

inline void Read(void)
{
    int a, n;
    long long inv, invb;

    fscanf(fin, "%d %d", &a, &n);

    inv_mod(a, n, inv, invb);

    if (inv < 0)
        inv += n;

    fprintf(fout, "%d", inv);
}

int main()
{
    fin = fopen(InFile, "r");
    fout = fopen(OutFile, "w");

    Read();

    fclose(fin); fclose(fout); return 0;
}