#include<stdio.h>

#define INPUT "inversmodular.in"
#define OUTPUT "inversmodular.out"
#define LL long long

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long A, N;

void solve(LL &__X, LL &__Y, long __A, long __B)
{
  LL temp;

  if(!__B)
  {
    __X = 1;
    __Y = 0;
  }
  else
  {
    solve(__X, __Y, __B, __A % __B);

    temp = __X;
    __X = __Y;
    __Y = temp - __Y * (__A / __B);
  }
}

int main()
{
  LL inv = 0, temp;

  fscanf(fin, "%ld %ld", &A, &N);

  solve(inv, temp, A, N);

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

  fprintf(fout, "%Ld\n", inv);

  fclose(fin);
  fclose(fout);

  return 0;
}