#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

int a, n;

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

int main() {
  int x, y;
  in>>a>>n;
  gcd(x, y, a, n);
  if(x <= 0) {
    x = n + x % n;
  }
  out<<x;
  return 0;
}