#include <bits/stdc++.h>

using namespace std;

int extgcd( int a, int b, int &x, int &y ) {
  if ( b == 0 ) {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1;
  int g = extgcd( b, a % b, x1, y1 );
  x = y1;
  y = x1 - y1 * (a % b);
  return g;
}

int invMod( int a, int n ) {
  int x, y;
  extgcd( a, n, x, y );
  return (x % n + n) % n;
}

int main() {
  FILE *fin, *fout;
  int a, n;

  fin = fopen( "inversmodular.in", "r" );
  fscanf( fin, "%d%d", &a, &n );
  fclose( fin );

  fout = fopen( "inversmodular.out", "w" );
  fprintf( fout, "%d\n", invMod( a, n ) );
  fclose( fout );

  return 0;
}