#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pr pair<int,int>
#define fr tmp.first
#define sc tmp.second
pr exgcd(ll a,ll b){
	if(b==0) return make_pair(1,0);
	pr tmp=exgcd(b,a%b);
	return make_pair(sc,fr+a/b*sc);
}
int main(){
	ll x,y;
	cin>>x>>y;
	pr ans=exgcd(x,y);
	int n=ans.first;
	n=(n%y+y)%y;
	cout<<n;
	return 0;
}