#include <bits/stdc++.h>

using namespace std;

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

inline int gcd (int A, int B, long long &X, long long &Y ) {
 if (B == 0) {
  X = 1;
  Y = 0;
  return A;
 }
 int D;
 long long X0, Y0;
 D = gcd (B, A % B, X0, Y0);
 X = Y0;
 Y = X0 - (A / B) * Y0;
 return D;
}

int main() {
 long long inv = 0, ins;
 int A, N;
 fin >> A >> N;
 gcd (A, N, inv, ins);
 if (inv <= 0) inv = N + inv % N;
 fout << inv;
 fin.close ();
 fout.close ();
 return 0;
}