#include<stdio.h>
void cmmdc(long long&,long long&,long long,long long);
long long a,b;
int main(){
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld %lld",&a,&b);
	long long t1=0,t2;
	cmmdc(t1,t2,a,b);
	if(t1<=0)
		t1=b+t1%b;
	printf("%lld\n",t1);
	return 0;
}
void cmmdc(long long&t1,long long &t2,long long a,long long b){
	if(b==0){
		t1=1;
		t2=0;}
	else{
		long long t0;
		cmmdc(t1,t2,b,a%b);
		t0=t1;
		t1=t2;
		t2=t0-(a/b)*t2;}
}