#include <iostream>
using namespace std;
typedef long long ll;
ll ext_gcd(ll a,ll b,ll &x,ll &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
ll d = ext_gcd(b,a%b,y,x);
y = y - (a/b)*x;
return d;
}
int main() {
ll a,b,x,y;
cin >> a >> b;
ext_gcd(a,b,x,y);
cout << (x%b + b)%b << endl;
}