#include <fstream>
#define ll long long
using namespace std ;



ll A, B ;
ll X ;

ifstream cin("inversmodular.in") ;
ofstream cout("inversmodular.out") ;

 void gcd(ll &X, ll &Y, int A, int B)
 {
     if(!B)
     {
         X = 1 ;
         Y = 0 ;
     }
     else {

        gcd(X, Y, B, A%B);
        ll var = X;
        X = Y ;
        Y = var - Y * (A / B) ;
     }

 }

int main()
{
    cin >> A >> B ;
    ll invers = 0, ins ;

    gcd(invers, ins, A, B) ;

    if(invers <= 0)
        invers = B + invers % B ;
    cout << invers << '\n' ;

    cin.close() ;
    cout.close() ;
    return 0 ;
}