#include<bits/stdc++.h>
using namespace std;
long long a,b,x,y;
void exgcd(long long a,long long b,long long &x,long long &y){
	if(b==0){
		x=1;
		y=0;
		return ;
	}
	exgcd(b,a%b,x,y);
	long long t=x;
	x=y;
	y=t-(a/b)%y;
}
int main(){
	scanf("%lld %lld",&a,&b);
	exgcd(a,b,x,y);
	printf("%lld",(x%b+b)%b);
	return 0;
}