/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
pair<long long,long long> euclid(long long a,long long b)
{
    if(b==0)
       return {1,0};
    else
      {
          auto P=euclid(b,a%b);
          return{P.second,P.first-P.second*(a/b)};
      }
}
long long a,b;
int main()
{
    cin>>a>>b;
    pair<long long,long long> P=euclid(a,b);
    while(P.first<=0)
        P.first=P.first+b;
    cout<<P.first;
    return 0;
}