#include<stdio.h>
#include<fstream>

using namespace std;

long long int a, n, c, d, x, y;

void euclid(long long int a, long long int b, long long int &d, long long int &x, long long int &y)
{
    if(!b)
       d = a, x = 1, y = 0;
    else
    {
        long long int x0, y0;

        euclid(b, a%b, d, x0, y0);

        x = y0;
        y = x0 - (a / b) * y0;
    }
}

int main()
{
    ifstream f("inversmodular.in");

    f >> a >> n;

    f.close();

    d = 1;

    euclid (a, n, d, x, y);

    while(x <= 0)
        x += n, x %= n;

    FILE *g = fopen("inversmodular.out", "w");

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

    fclose(g);

    return 0;
}