#include <iostream>

#include <cstdio>

using namespace std;

FILE *f, *g;

int a, n, d, x, y;

void euclid(int a, int b, int &x, int &y, int &d)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        d = a;
        return;
    }

    int q = a / b, xx, yy;
    euclid(b, a % b, xx, yy, d);
    x = yy;
    y = xx - yy * q;
}

void readFile()
{
    f = fopen("inversmodular.in", "r");

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

    fclose(f);
}

void solve()
{
    euclid(a, n, x, y, d);

    if(x < 0)
    {
        if(-x < n)
            x += n;

        else
            if(-x >= n)
                x += (((-x) / n) + (((-x) % n) != 0)) * n;
    }
}

void printFile()
{
    g = fopen("inversmodular.out", "w");

    fprintf(g, "%d\n", x);

    fclose(g);
}


int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}