/*
Invers modular.
*/

#include <stdio.h>
#include <stdlib.h>

int a, n;
int invers;

void euclid_extins (int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return;
    }
    int x0, y0;
    euclid_extins(b, a % b, &x0, &y0);
    *x = y0;
    *y = x0 - (a / b) * y0;
}

void invers_modular () {
    invers = 0;
    int x;
    euclid_extins(a, n, &invers, &x);
    if (invers < 0)
        invers += (invers / n + 1) * n;
}

int main () {
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    scanf("%d %d", &a, &n);
    invers_modular();
    printf("%d\n", invers);
    return 0;
}