#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int x, y, a, b, n;
void read()
{
    freopen("inversmodular.in", "r", stdin);
    scanf("%d %d", &a, &n);
}
void gcd(int &x, int &y)
{
    int x0, y0, z, d;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return ;
    }
    z = a / b;
    d = a % b;
    a = b;
    b = d;
    gcd(x0, y0);
    x = y0;
    y = x0 - z * y0;
}
void write()
{
    freopen("inversmodular.out", "w", stdout);
    if (x <= 0)
        x += n;
    printf("%d", x);
}
int main()
{
    read();
    b = n;
    gcd(x, y);
    write();
    return 0;
}