#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
  
void inversmodulo(int a,int b,int &d,int &x,int &y){
    if(b==0){d=a;x=1;y=0;}
    else{
        int x1,y1;
        inversmodulo(b,a%b,d,x1,y1);
        x=y1;
        y=x1-(a/b)*y1;
    }
}
int main()
{   
    int a,n,b,x,c;
    fin>>a>>n;
    inversmodulo(a,n,b,x,c);
    if(x<0) x+=n;
    fout<<x;
    return 0;
}