#include <stdio.h>

void euclid(int A, int B, int *X, int *Y) {
  if (!B) {
    *X = 1, *Y = 0;
  } else {
    int X0, Y0;
    euclid(B, A % B, &X0, &Y0);

    *X = Y0;
    *Y = X0 - Y0 * (A / B);
  }
}

int main(void) {
  int A, N, X, Y;
  FILE *f = fopen("inversmodular.in", "r");

  fscanf(f, "%d %d", &A, &N);
  fclose(f);

  f = fopen("inversmodular.out", "w");

  euclid(A, N, &X, &Y);
  fprintf(f, "%d\n", X % N + N);
  fclose(f);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}