//http://www.infoarena.ro/problema/inversmodular
#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

#define llu unsigned long long int
llu  a,n,p,re = 1;

tuple<int,int,int> extendedEuclid(int a, int b)
{
    if (b == 0)
        return std::make_tuple(a,1,0);
    tuple<int,int,int> dxyp = extendedEuclid(b,a%b);
    int xp = get<1>(dxyp);
    int yp = get<2>(dxyp);
    int dp = get<0>(dxyp);
    return std::make_tuple(dp,yp,xp- (a/b)*yp);
}
void solvec()
{
    in >> a >> n;
    tuple<int,int,int> dxy = extendedEuclid(a,n);
    int x = get<1>(dxy);
    if (x<=0)
        x = n+x%n;
    out<<x;
}
int main()
{
    solvec();
}