#include <fstream>

using namespace std;
long long n,a,x,y;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
void Invers_Modular (long long a,long long b,long long &x,long long &y){
    if (b==0){
        x = 1;
        y = 0;
    }
    else{
        long long xa,ya;
        Invers_Modular (b,a%b,xa,ya);
        x = ya;
        y = xa- (a/b)*ya;
    }


}
int main (){

    fin>>a>>n;
    Invers_Modular(a,n,x,y);
    if (x < 0)
        x = (x+ (((-x)/n +1)*n)   )%n;
    fout<<x;



    return 0;
}