#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(long long a, long long 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;
  }
}

/*
* Solves the equation
* 			Ax is congruent to B (mod N),
* given A, B and N finds x.
*/
long long ModularLinearEquation(long long A, long long B, long long N)
{
  long long d, x, y;
  ExtendedEuclideanAlgorithm(A, N, d, x, y);

  if (B % d == 0)
    return (x * (B / d)) % N;
}

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

  long long A, N;
  fscanf(f, "%lld %lld", &A, &N);
  fprintf(g, "%lld", ModularLinearEquation(A, 1, N));

  fclose(f);
  fclose(g);

  return 0;
}