#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out"); 
int modinv(int a, int M){
   int aux = M;
   int y0 = 0, y1 = 1;
   while(a != 0){
        int r =  M % a;
        int c = M / a;
        M = a;
        a = r;
        int y = y0 - c * y1;
        y0 = y1;
        y1 = y;
   }
   while(y0 < 0)
       y0 += aux;
   return y0;
}
int main(){
    int a, M;
    fin >> a >> M;
    fout << modinv(a, M);
    fin.close();
    fout.close();
    return 0;
}