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

using namespace std;

/*
* Greatest common divisor(gcd/cmmdc)
*/
int EuclideanAlgorithm(int a, int b)
{
  if (b == 0)
    return a;
  else
    EuclideanAlgorithm(b, a % b);
}

/*
* a * x + b * y = d, unde d = cmmdc(a, b);
* Voi extinde procedura recursiva de calculare a cmmdc pentru a include si x si y.
* Calculam x si y incepand de la "capatul recurentei". Daca b = 0, atunci a * 1 + b * 0 = a(cmmdc) evident, asa ca initial x = 1 si y = 0.
* Incercam sa calculam x, y in functie de x0, y0 obtinutit pentru b, a % b.
* Noi stim urmatoarele:
*
*   b * x0 + (a % b) * y0 = d
*   a * x + b * y = d
* Trebuie sa aflam o solutie pentru x si y. Vom nota parte intreaga din a / b cu c. => (a % b = a - b * c)
*
*   b * x0 + (a - b * c) * y0 = a * x + b * y
*   b * (x0 - c * y0 - y) = a * (x - y0)
* O solutie:
*
*   x0 - c * y0 - y = 0, De unde rezulta y = x0 - c * y0
*   x - y0 = 0, De unde rezulta x = y0
*/
void ExtendedEuclideanAlgorithm(int a, int b, long long& d, long long& x, long long& y)
{
  if (b == 0)
  {
    d = a;
    x = 1;
    y = 0;
  }
  else
  {
    long long x0, y0;
    ExtendedEuclideanAlgorithm(b, a % b, d, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
  }
}

/*
* Functia returneaza x a.i. A * x % N = 1;
* x se numeste invers modular a lui a
*/
long long InversModular(int A, int N)
{
  long long inv, ins, d;
  ExtendedEuclideanAlgorithm(A, N, d, inv, ins);
  if (inv <= 0)
    inv = N + inv % N;
  return inv;
}

int main()
{
  FILE * f = fopen("inversmodular.in", "r");
  FILE * g = fopen("inversmodular.out", "w");

  int A, N;
  fscanf(f, "%d %d", &A, &N);
  fprintf(g, "%lld", InversModular(A, N));

  fclose(f);
  fclose(g);

  return 0;
}