#include<stdio.h>
#define ll long long

void gcd(ll a, ll b, ll &x, ll &y ){
	if(b==0){
		x=1; y=0; return;
	}
	ll x0, y0;
	gcd(b, a%b, x0, y0);
	x=y0;
	y=x0-a/b*y0;
}

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