#include<iostream>
#include<string>

using namespace std;

void euclid(int a,int b,int &d,int &x,int &y)
{
     if(!b)
     {
          d=a;
          x=1,y=0;
          return ; 
     }
     
     euclid(b,a%b,d,x,y);
     
     int nx=y,ny=x-(a/b)*y;
     x=nx,y=ny;
}

int main()
{
    int A,N,d,x,y;
    
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    
    scanf("%d %d",&A,&N);
    
    euclid(A,N,d,x,y);
    
    while(x<0) x+=N;
    
    printf("%d",x);
    
    return 0;
}