#include <stdio.h>
long long a,n,x,y;
void euclid(long long a, long long b, long long &x,long long &y)    
{    
   long long x0, y0;    
   if (b==0) {   
    x=1;    
    y=0;    
    } else {    
    euclid(b,a%b,x0,y0);    
    x=y0;    
    y=x0-(a/b)*y0;    
    }    
}    
int main()
{
    freopen ("inversmodular.in","r",stdin);
    freopen ("inversmodular.out","w",stdout);
    scanf("%ld %ld",&a,&n);
    euclid(a,n,x,y);
    if(x<0)x=n-(-x)%n;
    printf("%ld\n",x);
    return 0;
}