#include<bits/stdc++.h>
#define ll long long
using namespace std;
void Exgcd(ll a,ll b,ll &d, ll &x,ll &y)
{
if(!b)
{
d=a;
x=;
y=;
}
else
{
Exgcd(b,a%b,d,x,y);
int t=x;x=y;y=t-a/b*y;
}
}
int main()
{
ll a,b,d,x,y;
scanf("%lld%lld",&a,&b);
Exgcd(a,b,d,x,y);
printf("%lld",(x%b+b)%b);
return ;
}