#include<stdio.h>
#include<assert.h>

#include<algorithm>
#include<vector>

using namespace std;

int a, n, sol, mod, ix;

void read(){
  assert(freopen("inversmodular.in", "r", stdin) != NULL);
  scanf("%d%d", &a, &n);
}

long long lg_put(int x,int pow){
  if(pow == 1)
    return x;
  x = lg_put(x,pow / 2);
  if(pow % 2 == 0)
    return ((long long)x * x) % mod;
  else
    return ((((long long)x * x) % mod )* ix) % mod;
}

int x1 = 1, y1 = 0, x2 = 0, y2 = 1;

int gcd(int x, int y){
  int aux_x, aux_y, aux;
  while(y){
    aux = x;
    aux_x = x1;
    aux_y = y1;

    x = y;
    x1 = x2;
    y1 = y2;

    x2 = aux_x - (aux / y) * x2;
    y2 = aux_y - (aux / y) * y2;
    y = aux % y;
  }

  return x;
}

int euclid(){
  int irelevant = gcd(n, a);

  return (y1 + n) % n;
}

void solve(){
  mod = n;
  ix = a;
  sol = euclid();
}

void write(){
  assert(freopen("inversmodular.out", "w", stdout) != NULL);
  printf("%d",sol);
}

int main(){
  read();
  solve();
  write();
  return 0;
}