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

FILE *fin = NULL;
FILE *fout = NULL;

int n, a;

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(void)
{
    int inv = 0, ins = 0;
    if((fin = fopen("inversmodular.in", "r")) == NULL)
    {
        exit(-1);
    }
    fscanf(fin, "%d %d", &a, &n);
    fclose(fin);
    euclid_extins(&inv, &ins, n, a);
    while(ins < 0)
    {
        ins = ins + n;
    }
    if((fout = fopen("inversmodular.out", "w")) == NULL)
    {
        exit(-1);
    }
    fprintf(fout, "%d", ins);
    fclose(fout);
    return 0;
}