#include <fstream>

using namespace std;

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

void EuclidE(int a,int b,int &x,int &y,int &d)
{
    if(b==0){x=1;y=0;d=a;}
    else{int x0,y0;
         EuclidE(b,a%b,x0,y0,d);
         x=y0;   y=x0-a/b*y0;
        }
}
int main(){
fin>>a>>n;
EuclidE(a,n,x,y,d)
while(y<1)y=y+n;
fout<<y;
return 0;
}