#include <iostream>
#include <fstream>

using namespace std;

void extEuclid(long long a, long long b, long long *x, long long *y)
{
    if(!b){
        *x = 1;
        *y = 0;
    }
    else{
        long long 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);
    long long a, n, x, y;
    scanf("%lld%lld", &a, &n);

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

    printf("%ld\n", (x <= 0)? (x+x%n): x);

    return 0;
}