#include <stdio.h>
#include <iostream>

std::pair<int, int> euclid(int a, int b){
  if(b==0){
    return std::make_pair(1, 0);
  }
  auto [x, y] = euclid(b, a%b);
  return std::make_pair(y, x - a / b * y);
}

int main(){
  FILE *fin = fopen("inversmodular.in", "r");
  FILE *fout = fopen("inversmodular.out", "w");
  int a, b;
  fscanf(fin, "%d%d", &a, &b);
  auto [x, y] = euclid(a, b);
  while(x<0) x+=b;
  fprintf(fout, "%d\n", x);
  fclose(fin);
  fclose(fout);
  return 0;
}