#include <cstdio>
using namespace std;

int a, n;
inline void euclid(int a, int b, long long &x, long long &y){
    if(b == 0){
        x = 1; y = 0;
        return ;
    }
    long long x0, y0;
    euclid(b, a % b, x0, y0);
    x = y0;
    y = x0 - y0 * (a / b);
}
int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    scanf("%d%d", &a, &n);
    long long ins, inv = 0;
    euclid(a, n, inv, ins);
    if(inv <= 0) inv = n + inv % n;
    printf("%lld\n", inv);
    return 0;
}