#include <iostream>
#include <fstream>

using namespace std;

int extEuclid(int a, int b, int *x, int *y)
{
    int x0 = 1, x1 = 0, y0 = 0, y1 = 1;

    while(1){
        int q = a / b;
        int r = a % b;
        if(!r){
            return b;
        }
        a = b;
        b = r;
        *x = x0 - q*x1;
        *y = y0 - q*y1;
        x0 = x1;
        x1 = *x;
        y0 = y1;
        y1 = *y;
    }
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a, n, x, y;
    scanf("%d%d", &a, &n);

    extEuclid(a, n, &x, &y);

    printf("%d\n", x % n);

    return 0;
}