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