#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long MOD;

long long qexp(long long a, long long b){
  long long r = 1;
  while (b){
    if (b % 2 == 1)
      r = (r * a) % MOD;
    a = (a * a) % MOD;
    b /= 2;
  }
  return r;
}

void gcd(long long &x, long long &y, int a, int b){
  if (!b){
    x = 1;
    y = 0;
  }
  else{
    gcd(x, y, b, a % b);
    long long aux = x;
    x = y;
    y = aux - y * (a / b);
  }
}

int main(){
  long long a, n;
  fin >> a >> n;
  MOD = n;
  long long inv = 0, ins;
  gcd(inv, ins, a, n);
  if (inv <= 0)
    inv = n + inv % n;
  fout << inv << "\n";
  return 0;
}