#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll a , b , x , y;
ll exgcd(ll a , ll b)
{
	if(b == 0) 
	{
		x = 1;
		y = 0;
		return a;
	}
	exgcd( b , a % b );
	ll ans = x;
	x = y;
	y = ans - a / b * y;
}


int main()
{
	cin >> a >> b;
	exgcd( a , b );
	x = ( x % b + b ) % b;
	cout << x;
	return 0;
}