#include <fstream>
#include <iostream>

#define ll long long

std::ifstream fin("inversmodular.in");
std::ofstream fout("inversmodular.out");

int a, n;
ll inv, ins;

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

int main(){
  fin >> a >> n;
  euclid(inv, ins, a, n);
  if (inv <= 0){
    inv = n + inv % n;
  }
  fout << inv << '\n';
  return 0;
}