#include <iostream>
#include <fstream>

using namespace std;

void extEuclid(int a, int b, int *x, int *y)
{
    if(!b){
        *x = 1;
        *y = 0;
    }
    else{
        int x0;
        extEuclid(b, a%b, *&x, *&y);
        x0 = *x;
        *x = *y;
        *y = x0 - (a/b) * (*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 <= 0)? (n+x%n):x%n);

    return 0;
}