#include<fstream>
using namespace std;

int euclid(int a,int b,long long &x,long long &y)
{
   if(!b){
          x=1;
          y=0;
          return a;
          }   
   else 
   {
     long long x0,y0;
     int D = euclid(b,a%b,x0,y0);  
     x = y0;
     y = x0 - y0 * ( a / b );
     return D;   
   }
          
}

int main(){
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    int A,N; long long x,y;
    
    cin>>A>>N;
    
    euclid(A,N,x,y);
    
    if(x <= 0) x+=N;
    
    cout<<x;

 return 0;   
}