#include <iostream>
#include <fstream>
 
using namespace std;
 
pair<int, int> extended_euclid(int a, int b){
      pair<int, int> result;
   
        if (a == 1){
              result.first  = 1;
              result.second = 0;
          } else if (b == 1) {
                result.first  = 0;
                result.second = -1;
            } else {
                  int d = a / b, c = a % b;
                  pair<int, int> p = extended_euclid(b, c);
                  result.first = - p.second;
                  result.second = - (p.second * d + p.first);
              }
      return result;
}
 
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
 
int main() {
      int A, N;
      f >> A >> N;
      int result = extended_euclid(A, N).first;
   
        if (result < 0)
            result+=N;
      g << result << '\n';
   
        f.close();
      g.close();
      return 0;
}