#include <bits/stdc++.h>
#define ll long long

using namespace std;

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

inline void gcd(ll a, ll b, ll &x, ll &y)
{
     if (!b)
        x = 1, y = 0;
     else
     {
         ll x0, y0;
         gcd(b, a % b, x0, y0);
         x = y0;
         y = x0 - (a / b) * y0;
     }
}

int main()
{
    ll a, n, inv, y;
    in >> a >> n;
    gcd(a, n, inv, y);
    if (inv < 0)
        inv = n + inv % n;
    out << inv;
    return 0;
}