#include <stdio.h>
#include <inttypes.h>

/**
 * a * xn + b * yn = d
 * b * xn-1 + (a % b) yn-1 = d
 * ...
 * d * x0 + 0 * y0 = d; x0 = 1; y0 = 0
 * 
 * a * xn + b * yn = b * xn-1 + (a % b) * yn-1
 * a * xn + b * yn = b * xn-1 + (a - b * a // b) * yn-1
 * a * (xn - yn-1) = b * (xn-1 - a // b * yn-1 - yn)
 * => one solution is:
 * xn = yn-1
 * yn = xn-1 - a // b * yn-1
 */
int gcd(int a, int b, int64_t & x, int64_t & y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64_t prev_x, prev_y;
    int result = gcd(b, a % b, prev_x, prev_y);
    x = prev_y;
    y = prev_x - a / b * prev_y;
    return result;
}


int main() {
    FILE * f;
    int a, n;

    f = fopen("inversmodular.in", "r");
    fscanf(f, "%d%d", &a, &n);
    fclose(f);

    int64_t x, y;
    gcd(a, n, x, y);
    if (x < 0) {
        x = x % n + n;
    }

    f = fopen("inversmodular.out", "w");
    fprintf(f, "%lld", x);
    fclose(f);

    return 0;
}