#include<bits/stdc++.h>
using namespace std;
int a,b,x,y;
inline int ex_gcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	int res=ex_gcd(b,a%b,x,y);
	int oo=x;
	x=y;
	y=oo-(a/b)*y;
	return res;
}
int main(){
	scanf("%d%d",&a,&b);
		ex_gcd(a,b,x,y);
	while(x<0)x+=b;//x可能小于0 如3,10；开始算出的是-3,1
	printf("%d\n",x);
}