#include <stdio.h>

using namespace std;

FILE *fin = fopen("inversmodular.in", "r"), *fout = fopen("inversmodular.out", "w");

long long a, n, x, y, aux;

void gcd(long long a, long long b)  {
    if(b == 0LL)  {
        x = 1LL, y = 0LL;
        return;
    }
    gcd(b, a % b);
    aux = x;
    x = y;
    y = aux - y * (a / b);
}

int main()  {
    fscanf(fin, "%lld%lld", &a, &n);
    gcd(a, n);
    if(x <= 0LL)
        x = n + x % n;
    fprintf(fout, "%lld", x);
    fputc('\n', fout);
    fclose(fin);
    fclose(fout);
    return 0;
}