#include<bits/stdc++.h>

 #define pa pair<int,int>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=;

 inline ll rd(){

     ll x=;char c=getchar();ll neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<='') x=x*+c-'',c=getchar();

     return x*neg;

 }

 void exgcd(ll a,ll b,ll &x,ll &y){

     if(b==){x=,y=;return;}

     ll x1,y1;

     exgcd(b,a%b,x1,y1);

     x=y1;y=x1-a/b*y1;

 }

 int main(){

     ll a=rd(),b=rd();ll x,y;

     exgcd(a,b,x,y);

     printf("%lld\n",(x%b+b)%b);

     return ;

 }