#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll t;
ll a,b,c;
ll gcd(ll a,ll b,ll &X,ll &Y){
    if(b==0){
        X=1;
        Y=0;
        return a;
    }
    else{
        ll X0=0,Y0=0,D=0;
        D=gcd(b,a%b,X0,Y0);
        ll tz=X0;
        X=Y0;
        Y=(X0-(a/b)*Y0);
        return D;
    }
}
int32_t main() {
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");

        fin>>a>>b;
        ll x=0,y=0;
        ll w=gcd(a,b,x,y);
        //cout<<w<<" ";
        ll ans=x;
        ans=ans%b;
        while(ans<0) ans+=b;
        fout<<ans<<"\n";


    return 0;
}