#include <cstdio>

int euclid(long long a, long long b, long long &x, long long &y){

  if(!b)
    x = 1, y = 0;
  else {
    euclid(b, a%b, &x, &y);
    long long aux = x;
    x = y;
    y = aux - y*(a/b);
  }
}

int main(){

  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);


  long long A, N, x, y;
  scanf("%lld %lld", &A, &N);

  euclid(A, N, x, y);

  if(x <= 0)
    x = N+x%N;

  printf("%lld\n", x);

  return 0;

}