#include<iostream>
#include<fstream>

using namespace std;

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

long a,n;
long long x,y;

void cmmdc(long a,long b){
    if(!b){
        x=1;
        y=0;
    }
    else{
        int r=a%b;
        cmmdc(b,r);
        long long aux=x;
        x=y;
        y=aux-y*(a/b);
    }
}


int main(){
   fin>>a>>n;
   cmmdc(a,n);
   if(x<=0)
        x=n+x%n;
    fout<<x<<"\n";
    fin.close();
    fout.close();
    return 0;
}