#include <stdio.h>
#include <stdlib.h>
#define INPUT_FILE "inversmodular.in"
#define OUTPUT_FILE "inversmodular.out"
FILE *fin = NULL;
FILE *fout = NULL;

FILE *openfile(char *filename, char *type)
{
    FILE *fin = NULL;
    if ((fin = fopen(filename, type)) == NULL)
    {
        printf("fisierul nu a putut sa fie deschis");
        exit(EXIT_FAILURE);
    }
    return fin;
}

void euclid_extins(int *x, int *y, int a, int b)
{
    if (!b)
    {
        *x = 1;
        *y = 0;
    }
    else
    {
        euclid_extins(x, y, b, a % b);
        int aux = *x;
        *x = *y;
        *y = aux - *y * (a / b);
    }
}

int main()
{
    fin = openfile(INPUT_FILE, "r");
    fout = openfile(OUTPUT_FILE, "w");
    int A, N;
    int inv = 0, ins = 0;
    fscanf(fin, "%d %d", &A, &N);
    euclid_extins(&inv, &ins, A, N);
    if (inv <= 0)
        inv = N + inv % N;
    fprintf(fout, "%d", inv);
    return 0;
}