#include <iostream>
#include <fstream>
using namespace std;

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



int invMod(int a, int n) {
    int y0 = 0, y1 = 1;
    int aux = n;
    while(a!=0){
        int r = n%a;
        int c = n/a;
        n = a;
        a = r;
        int y = y0 - c*y1;
        y0 = y1;
        y1 = y;
    }
    while(y0<0){
        y0+=aux;
    }
    return y0;
}


int main()
{
    int A,N;
    fin>>A>>N;
    fout<<invMod(A,N);
    fin.close();
    fout.close();
    return 0;
}