#include <cstdio>


int A, N;

void euclid_extins(long long &x, long long &y, int a, int b)  
{  
     if (!b)  x=1, y=0;  
     else  
     {             
         euclid_extins(x, y, b, a % b);
         long long t=x;
         x=y;
         y=t - y*(a/b);
     }
}

int main()
{
	
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
	
    long long a=0,b;
    
    scanf("%d %d", &A, &N);
    euclid_extins(a, b, A, N);

    if (a <= 0) a = N + a%N;
       
    printf("%lld\n", a);
      
    return 0;
}