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

int x, y, d;

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

int main()
{
    FILE *fin, *fout;
    int n, a;
    fin = fopen("inversmodular.in", "r");
    fscanf(fin, "%d%d", &a, &n);
    fclose(fin);
    cmmdc(n, a);
    if(y < 0){
      y = y + (y / (-n)) * n + n;
    }
    fout = fopen("inversmodular.out", "w");
    fprintf(fout, "%d", y);
    fclose(fout);
    return 0;
}