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

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

int main()
{
    FILE *fin, *fout;
    int a, n, inv, aux;
    fin=fopen("inversmodular.in", "r");
    fscanf(fin, "%d%d", &a, &n);
    fclose(fin);
    euclid(a, n, &inv, &aux);
    fout=fopen("inversmodular.out", "w");
    fprintf(fout, "%d\n", inv>=0?inv:n+inv%n);
    fclose(fout);
    return 0;
}